GraphAce: Secure Two-Party Graph Analysis Achieving Communication Efficiency

Graph analysis has achieved success in challenging tasks such as importance measures, fraud detection, and anti-money laundering. For a deep understanding of various complex systems in real life, a whole graph may involve data and connections from multiple sources. Secure multi-party computation is suitable for this scenario, which allows untrusted parties to compute collectively without revealing their individual data. However, a significant challenge is the high communication overhead, especially during intricate computations of large-scale input, and existing secure graph analysis frameworks incur a lower bound of Omega(|V|+|E|) communication per iteration, where V and E denote vertices and edges, respectively.

This paper proposes GraphAce, an efficient secure two-party graph analysis framework, which adopts a distinct technical roadmap from existing solutions. We identify and address the security challenges when utilizing local graph data of parties, with the mixed primitives system of homomorphic encryption and secret sharing, and a novel ChaosTable data structure that protects privacy during cross-party computation. Consequently, GraphAce eliminates any network traffic related to the edges. For each iteration, it achieves low complexities of Theta(|V|) communication, breaking the Omega(|V|+|E|) lower bound of previous secure solutions, and Theta(|V|+|E|) computation, which is the same as insecure methods.

Evaluations show that GraphAce exceeds previous methods by up to tens of thousands of times in speed and saves up to 99.99% communication, depending on the application and the network. This is the first secure two-party graph analysis framework capable of processing over 1 million vertices and 132 million edges in a reasonable time, which is 128x larger than previous reports, to the best of our knowledge.