GraphAce: Secure Two-Party Graph Analysis Achieving Communication Efficiency

GraphAce: Secure Two-Party Graph Analysis Achieving Communication Efficiency

Speakers: Jiping Yu

Conference: USENIX Security

YouTube: https://www.youtube.com/watch?v=lCGYfC53JIA

Overview

In an increasingly data-driven world, the ability to analyze vast datasets is paramount for extracting insights, detecting anomalies, and making informed decisions. However, a significant challenge arises when these datasets, particularly complex graph structures, are distributed across multiple entities, each holding sensitive information that cannot be directly shared due to privacy concerns, regulatory compliance, or proprietary interests. The talk "GraphAce: Secure Two-Party Graph Analysis Achieving Communication Efficiency" by Jiping Yu from China University, a collaborative effort with Kuni Xiaoi, Xiaoi Juan Hong, and Wuang Chen, addresses this critical problem head-on.

GraphAce introduces a groundbreaking framework for secure two-party graph analysis that allows two distinct parties to collaboratively analyze a combined graph without revealing their individual subgraphs or any intermediate data. This innovation is particularly relevant for scenarios like financial fraud detection, where multiple banks might need to identify intricate fraud patterns across their combined transaction data without exposing individual customer details or transaction records to each other. The core contribution lies in GraphAce's ability to achieve end-to-end secure analysis with unprecedented communication efficiency, fundamentally reshaping the landscape of privacy-preserving data collaboration.

The significance of GraphAce stems from its ability to overcome long-standing limitations in secure multi-party computation (SMC) for graph workloads. Prior solutions often required additional non-colluding helper parties, were not end-to-end, or suffered from prohibitive communication overhead, especially for large-scale graphs. GraphAce's novel design completely eliminates communication proportional to the number of edges, achieving linear communication complexity with respect to the number of vertices, making it orders of magnitude more practical for real-world applications.

Background

▶ Watch: Introduction and need for secure graph analysis (0:00)

Graph analysis involves iterative workloads performed on a static graph where the graph topology remains immutable, but vertex attributes can change across iterations. A common example is financial fraud detection: if a card is marked high-risk, the risk propagates through transactions to connected accounts or cards. However, in reality, such financial graphs are often fragmented. Each bank, for instance, only possesses a subgraph of the global financial network. Analyzing these subgraphs individually yields suboptimal results; for example, a fraudulent pattern might only be detectable when the full graph, combining data from multiple banks, is analyzed.

The direct exchange of subgraphs between parties is frequently prohibited by stringent data privacy regulations (like GDPR or HIPAA) or proprietary concerns, as transactional records or customer relationships are considered highly sensitive. This necessitates secure graph analysis, a paradigm that guarantees two key properties: correctness, ensuring each party learns only the analysis results pertaining to its own data, and security, meaning parties learn absolutely nothing beyond these final results, especially about the other party's graph inputs or any intermediate computational values.

Previous research has explored secure graph analysis, each with its own trade-offs:

1. GraphSC: Published a decade ago, GraphSC was a pioneering secure analysis framework, achieving sub-quadratic complexity. It leveraged Garbled Circuits and techniques like Batonic sorting and scanner protocols to convert graph analysis workloads into secure circuits. However, its reliance on sorting introduced a substantial log-squared factor in complexity, leading to significant overhead for large graphs. It operated in a two-party setting.

1. IRAX: Building upon GraphSC, IRAX optimized the sorting bottleneck by introducing a three-party permutation protocol based on secret sharing. While this improved sorting, the parallel scanning process still incurred an additional logarithmic factor in communication. Crucially, IRAX assumed an honest majority in a three-party setting, meaning no two parties would collude, which adds a practical deployment constraint.

1. Gravity: Concurrent with GraphAce, Gravity introduced a communication-free pre-sum over secure sharing, effectively eliminating the parallel scanning bottleneck's logarithmic factor. It primarily relied on a secure permutation with linear complexity. However, Gravity also operated under an honest majority assumption, requiring a two-party setup with an additional non-colluding helper party.

A critical observation highlighted by the GraphAce team was that these prior studies were not end-to-end frameworks. They typically assumed the graph data was already in a garbled or secret-shared format among the participating parties. They did not address the initial conversion of local subgraphs into this secure distributed format, nor did they detail how the final, secure results would be distributed back to the respective parties. This left a significant gap in practical applicability. GraphAce aimed to address this by providing an end-to-end solution for secure two-party graph analysis, without requiring any additional non-colluding parties, and with significantly reduced communication overhead, specifically by eliminating any communication dependency on the number of edges (E).

Key Findings

▶ Watch: GraphAce's goals: end-to-end, two-party, efficient (5:05)

GraphAce makes several pivotal contributions to the field of secure multi-party computation for graph analysis:

• End-to-End Secure Analysis: It provides a comprehensive framework that handles the entire lifecycle of secure graph analysis, from the initial input of local subgraphs by two independent parties to the final distribution of analysis results, ensuring security throughout.
• Two-Party Setting Without Helpers: GraphAce achieves robust security against semi-honest adversaries in a pure two-party setting, eliminating the need for any additional non-colluding helper parties that are often required by other solutions (e.g., IRAX, Gravity), simplifying deployment and trust assumptions.
• Unprecedented Communication Efficiency: The system completely eliminates communication costs dependent on the number of edges (E) in the graph. Instead, it achieves a groundbreaking O(V) communication complexity per iteration, where V is the total number of vertices. This is a significant improvement over previous methods that incurred logarithmic or quadratic factors related to edges.
• Novel Security Primitives Integration: GraphAce successfully integrates a mix of homomorphic encryption and secret sharing to protect weight privacy, combined with a novel hash table data structure to ensure obliviousness, effectively hiding the actual vertex sets and intermediate computations.
• Superior Performance: Experimental evaluations demonstrate that GraphAce offers vastly superior performance compared to the prior state-of-the-art two-party solution, GraphSC. It achieves hundreds to tens of thousands of times communication savings and thousands of times speedup, especially for large-scale graphs and challenging network conditions.
• Proven Security: The system's security is formally proven using a simulation-based method against static semi-honest adversaries, guaranteeing that nothing beyond the final analysis results is learned by either party.

Technical Deep Dive

▶ Watch: Key insight: mimicking distributed plain text analysis (6:55)

The core problem formulation for GraphAce involves two parties, B (Party 0) and B (Party 1), each inputting their own local vertex set and edge set, including associated weights. Public information includes the specification of the graph analysis application, typically following a Gather-Apply-Scatter (GAS) model, and an approximate scale of the total number of vertices (O(log V)). The security goal is simulation-based security against semi-honest parties, ensuring no party learns anything beyond the final analysis results.

GraphAce's design is underpinned by a crucial insight: secure two-party graph analysis can be conceptualized as a secure implementation of distributed plaintext graph analysis over two machines. Most distributed plaintext systems achieve communication efficiency by avoiding per-edge communication. This inspired the GraphAce team to first design a highly efficient insecure plaintext solution and then systematically address its security vulnerabilities without reintroducing edge-dependent communication.

Consider an example algorithm where each vertex sums the weights from its incoming edges from the previous iteration. In an insecure, distributed plaintext setting, this would involve two steps:

1. Local Steps: Each party computes the sum of incoming edge weights for vertices within its own subgraph. For a vertex Y, Party 0 might sum R+Z, while Party 1 computes J.
2. Cross-Party Steps: Parties exchange these locally computed sums for shared vertices. For vertex Y, Party 0 sends its (R+Z) sum to Party 1, and Party 1 sends its J sum to Party 0. Both parties then sum these received values with their local sums to obtain the final new weight for Y.

This plaintext approach results in a constant number of communications per vertex, independent of its degree, leading to an overall O(V) communication per iteration. This efficiency is the target GraphAce aims to secure.

However, this insecure method presents two major security problems:

1. Weight Privacy: All intermediate values (the local sums) are exchanged in plaintext, directly revealing sensitive information about the other party's subgraph and vertex attributes.
2. Obliviousness: By sending local sums for specific vertices, a party implicitly reveals the set of vertices it possesses, compromising the privacy of its vertex set.

GraphAce addresses these problems using a sophisticated combination of cryptographic primitives and a novel data structure:

Protecting Weights with Mixed Primitives

To secure weight privacy, GraphAce employs a carefully chosen mix of homomorphic encryption (HE) and secret sharing (SS).

• Homomorphic Encryption (HE): Used for local computations. Specifically, a value X is encrypted by the other party's private key (denoted as X_HP) and stored at the current party. This ensures that the storing party cannot directly decrypt the underlying value, maintaining privacy. For example, Party 0 might hold encrypted values (X_HP) that only Party 1 can decrypt, and vice-versa.
• Secret Sharing (SS): Enables secure cross-party conversions. When values need to be combined or exchanged across parties, SS allows for operations on shares without revealing the underlying plaintext. In the example, SS enables the conversion of a homomorphic ciphertext from one party's domain to the other party's domain, facilitating the cross-party sum without exposing the values.

The mix of HE and SS is crucial:

• Using only secret sharing would lead to per-edge communication because SS operations typically require interaction for every arithmetic operation, making local computation inefficient.
• Using only homomorphic encryption would make cross-party operations (like summing values from different parties) impossible without revealing values or requiring complex multi-key HE schemes.

By leveraging this mix, GraphAce ensures that local and cross-party steps operate on ciphertexts and shares, achieving O(V) communication per iteration for weight privacy while maintaining security.

Achieving Obliviousness with a Secure Hash Table

To address obliviousness, GraphAce introduces a novel data structure called a hash table. The goal is to hide the actual vertex sets and ensure that operations are performed on a fixed-size, "oblivious" structure rather than revealing which vertices are actually present.

The mechanism works as follows:

1. Random Unique Position Assignment: A secure two-party protocol is designed to assign a random, unique position to each vertex. Crucially, if a vertex belongs to the intersection set (i.e., known by both parties), it receives the same random position from both parties. For example, vertex Y might be assigned position 2 by both Party 0 and Party 1.
2. Position-Based Referencing: All subsequent operations within the graph analysis process reference vertices by these assigned positions, not by their original names or identifiers.
3. Exhaustive Cross-Step Operations: The cross-party step then operates exhaustively over all possible positions within the defined range, irrespective of whether an actual vertex occupies that position. This effectively hides the true vertex set, as the communication pattern is identical whether a position is "active" or not.

This approach guarantees obliviousness and maintains O(V) communication per iteration, provided the range of assigned positions is also O(V).

Secure Position Assignment Protocol

The secure protocol for assigning these unique, random positions is a critical component. It involves:

1. Each party preparing arrays containing their vertex identifiers and adding random paddings to obscure the actual number of vertices.
2. Using secret sharing-based protocols to securely merge these two sorted arrays. This merge operation is performed without revealing the contents of the arrays to either party.
3. Generating a random array.
4. The merged array is then "reverted" for this random array, a process that ensures randomness and uniqueness.
5. Finally, even-indexed elements of the resulting array are revealed to Party B. Through this process, parties learn the assigned positions for their vertices but nothing else about the other party's vertex set.

This protocol is proven to satisfy the required correctness and randomness properties and is efficient, requiring O(V) time to build.

Full Workflow and Security Proof

The entire GraphAce system follows a six-step workflow, with steps 4 and 5 repeated for each iteration of the graph analysis application. (Detailed breakdown is available in the full paper).

The security of GraphAce is formally proven using a simulation-based method against static semi-honest adversaries. This rigorous proof demonstrates that any message transmitted over the network is either a ciphertext (indecipherable to the receiving party without the private key) or an independent random number from a non-distributable source. This guarantees that neither party learns any information beyond the final, agreed-upon analysis results.

Demo / Proof of Concept

▶ Watch: Insecure analysis and identified security problems (7:45)

While the talk did not feature a live, interactive demo, the speakers presented extensive experimental results serving as a strong proof of concept for GraphAce's efficiency and practicality. These evaluations were conducted against GraphSC, identified as the only existing two-party solution without an additional non-colluding helper party.

The experimental setup involved:

• Graphs: Five diverse graphs, ranging in scale from hundreds of vertices to 100 million edges, representing various real-world graph structures.
• Applications: Five different graph analysis applications were tested. The first three (e.g., PageRank) could be implemented using partially homomorphic encryption (PHE), which offers better performance. The latter two required the more computationally intensive full homomorphic encryption (FHE).
• Computational Resources: Each party was simulated with 40 CPU cores.
• Network Settings: Three different simulated network settings were used to evaluate performance under varying latencies and bandwidths, including intercontinental network conditions.

The results highlighted GraphAce's significant advantages:

1. Communication Efficiency: GraphAce consistently demonstrated superior communication efficiency, especially with larger graphs, due to its linear O(V) complexity compared to GraphSC's log factors.

• For applications implementable with PHE, GraphAce achieved over 10,000 times communication savings.
• Even for applications requiring FHE, GraphAce still managed hundreds of times communication savings.

1. Speedup: GraphAce also delivered substantial speedups, particularly on larger graphs and in scenarios with more demanding network conditions (higher latency, lower bandwidth).

• Speedups ranged from over 1,000 times to more than 10,000 times.
• A striking example cited was the PageRank algorithm on the largest graph under an intercontinental network setting: GraphSC would require over 4.5 years to complete, whereas GraphAce finished the task in just 2.1 hours.
• As expected, applications leveraging PHE generally exhibited better speedups than those requiring FHE.

1. Consistency: The evaluations showed that GraphAce consistently outperformed GraphSC across various graphs, even when graphs had the same total number of vertices plus edges (V+E) but differing ratios of edges to vertices (E/V). This demonstrated the robustness of GraphAce's design across different graph densities.

The team also confirmed that their system's artifacts were submitted for independent evaluation and successfully earned all three badges (Functional, Available, Reusable), underscoring the reproducibility and practical implementation of their work.

Defensive Implications

▶ Watch: Protecting weights with mixed homomorphic encryption and secret sharing (9:30)

GraphAce represents a significant step forward in the practical application of Secure Multi-Party Computation (SMC) for graph-based workloads. For cybersecurity defenders and organizations dealing with sensitive data, the implications are substantial, though primarily strategic and architectural rather than immediate tactical actions.

Firstly, GraphAce directly addresses the challenge of data silos and privacy regulations that often hinder collaborative threat intelligence, fraud detection, and anomaly analysis. Financial institutions, healthcare providers, or critical infrastructure operators, who possess valuable but sensitive graph data (e.g., transaction networks, patient referral graphs, supply chain dependencies), can now envision collaborating to uncover complex patterns that span their individual datasets. This can lead to more robust fraud detection, earlier identification of emerging threats, or improved disease outbreak prediction without compromising individual privacy or regulatory compliance (e.g., GDPR, HIPAA).

Defenders should recognize that adopting solutions built on principles like GraphAce could enable "privacy-preserving intelligence sharing." Instead of relying on anonymized or aggregated data (which often loses valuable detail), organizations could process raw, sensitive graph data securely in collaboration, deriving richer insights. This shifts the defensive paradigm from "don't share sensitive data" to "securely process sensitive data together."

From an architectural perspective, organizations should start evaluating the feasibility and benefits of integrating SMC frameworks into their data analysis pipelines. While GraphAce is a research prototype, its demonstrated efficiency suggests that privacy-preserving graph analysis is becoming increasingly viable for real-world scales. This means investing in expertise in cryptographic primitives like homomorphic encryption and secret sharing, and understanding how they can be applied to existing analytical workloads.

Finally, while GraphAce focuses on a two-party setting, the underlying principles of securing distributed computations while maintaining efficiency are broadly applicable. Defenders should keep an eye on the maturation of such technologies, as they promise to unlock new frontiers in collaborative security analysis without sacrificing the fundamental right to privacy. It empowers organizations to leverage collective intelligence from disparate, sensitive datasets, strengthening overall defensive posture against sophisticated adversaries.

Key Takeaways

• End-to-End Secure Two-Party Analysis: GraphAce provides a complete framework for two parties to analyze a combined graph securely, without requiring any additional non-colluding helper parties.
• Unprecedented Communication Efficiency: It achieves groundbreaking O(V) communication complexity per iteration by completely eliminating communication dependent on the number of edges (E), making large-scale secure graph analysis practical.
• Novel Cryptographic Integration: GraphAce employs a unique blend of homomorphic encryption for local computations and secret sharing for cross-party conversions, ensuring both weight privacy and obliviousness.
• Secure Hash Table for Obliviousness: A novel secure hash table mechanism assigns random, unique positions to vertices, allowing operations to proceed obliviously over all possible positions, hiding the actual vertex sets.
• Orders of Magnitude Performance Improvement: Experimental results demonstrate GraphAce's superior performance, achieving hundreds to tens of thousands of times communication savings and thousands of times speedup compared to prior state-of-the-art solutions like GraphSC.
• Advancing Practical SMC: This work significantly pushes the boundaries of practical Secure Multi-Party Computation for graph workloads, opening new avenues for privacy-preserving data collaboration in sensitive domains.

About the Speaker(s)

Jiping Yu (JP) is a researcher from China University, who presented the work "GraphAce: Secure Two-Party Graph Analysis Achieving Communication Efficiency" at USENIX Security. The project is a collaborative effort, with contributions from Kuni Xiaoi, Xiaoi Juan Hong, and Wuang Chen from various universities and research institutions.