Abstract
Secure Multi-Party Computation (MPC) allows multiple parties to compute functions over private data without revealing individual inputs. However, MPC has traditionally struggled with scalability and ease of use, particularly for "Big Data" applications. GraphSC is a framework that bridges this gap by bringing the efficiency of parallel graph processing (similar to GraphLab or Pregel) to the MPC domain. By designing novel parallel oblivious algorithms based on a Scatter-Gather-Apply abstraction, GraphSC enables complex data mining tasks on millions of records with only a small logarithmic overhead compared to non-secure versions.
Introduction
While theoretically powerful, MPC has historically been a domain reserved for cryptography experts. It is notoriously slow, difficult to program, and fails to scale to modern data volumes. A core challenge in secure computation is obliviousness: in a secure environment, even the pattern of memory access can leak sensitive information (e.g., revealing social graph connections). Standard solutions like Oblivious RAM (ORAM) often introduce massive computational overhead, and most existing frameworks are sequential, failing to leverage cloud-scale parallelism.
GraphSC aims to solve these issues by providing a familiar, parallel programming paradigm that is secure and oblivious by design. It allows developers to express algorithms using graph-parallel primitives while the underlying system handles the complexities of maintaining obliviousness across a distributed cluster.
Methods
Programming Model
GraphSC adopts the Scatter-Gather-Apply (SGA) abstraction used in popular graph-parallel frameworks. Developers write code using three primary primitives:
- Scatter: Vertices propagate data to their incident edges.
- Gather: Vertices aggregate data from their neighbors.
- Apply: Vertices update their own internal state based on the aggregated values.
Oblivious Graph Representation and Execution
To hide the graph structure, GraphSC represents the graph as a flat list of "tuples" containing vertices and edges. The system uses Oblivious Sorting (O-Sort) to reorder these tuples so that related data—such as an edge and its source vertex—are physically adjacent in memory.
Once sorted, the system performs Scatter and Gather operations using parallel oblivious algorithms. For the Gather phase, GraphSC utilizes a log-depth circuit to perform a "parallel prefix sum" style aggregation across the sorted list. This approach ensures that the "trace" of memory accesses is identical regardless of the actual graph structure, effectively neutralizing side-channel leaks.
Backend Implementation
The system is built atop ObliVM-GC, a Java-based framework that compiles programs into Garbled Circuits (Yao’s GC) for two-party secure computation. By limiting the programming model to SGA primitives, the authors optimized obliviousness specifically for graph patterns, resulting in an overhead of only $O(\log |V|)$, which is significantly more efficient than generic Oblivious Parallel RAM (OPRAM).
Evaluation and Key Results
The authors evaluated GraphSC using several classic algorithms, including PageRank and Matrix Factorization (MF). The primary benchmark for scalability was the MovieLens 1M dataset, containing 1 million ratings from approximately 6,000 users across 3,900 movies.
- Massive Scale: GraphSC performed Matrix Factorization on 1 million ratings in 13 hours using a 7-machine cluster (128 processors). This represents a significant leap over previous state-of-the-art secure MF implementations, which could only handle 16,000 ratings in 3 hours.
- Linear Scalability: The framework demonstrates nearly linear speedup as more processors are added. This proves that the bottleneck in secure computation can be shifted from sequential cryptographic logic to parallelizable circuit evaluation.
- Accuracy: Using 24-bit fixed-point arithmetic, the secure version of PageRank achieved an average relative error of only $10^{-5}$ compared to a cleartext implementation.
- Efficiency: The "total work" (logic gate count) grows slowly as processors are added, confirming the theoretical logarithmic overhead predicted by the authors.
Discussion and Future Work
GraphSC demonstrates that restricted abstractions can lead to massive efficiency gains in secure computation. By using sorting as a privacy shield, the framework decouples logical graph structures from physical memory layouts, allowing for high-performance parallel execution.
However, several areas for improvement remain. The current implementation assumes a semi-honest security model; moving to a "malicious" model would require more intensive cryptographic protocols. Additionally, the authors noted that the Java-based implementation suffered from garbage collection pauses. Future iterations using C-based implementations with AES-NI hardware acceleration could potentially provide an additional 20x speedup. Finally, while GraphSC excels at static graphs, supporting dynamic graphs where edges are frequently added or removed remains a subject for future research.
Summary updated