GraphSC: Parallel Secure Computation Made Easy

Kartik Nayak, Xiao Shaun Wang, Stratis Ioannidis, Udi Weinsberg, Nina Taft, Elaine Shi

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.
The Scatter-Gather-Apply programming primitives used in GraphSC.

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.

The oblivious execution flow using O-Sort to align vertex and edge data for parallel processing.

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

Abstract

We propose introducing modern parallel programming paradigms to secure computation, enabling their secure execution on large datasets. To address this challenge, we present Graph SC, a framework that (i) provides a programming paradigm that allows non-cryptography experts to write secure code, (ii) brings parallelism to such secure implementations, and (iii) meets the need for obliviousness, thereby not leaking any private information. Using Graph SC, developers can efficiently implement an oblivious version of graph-based algorithms (including sophisticated data mining and machine learning algorithms) that execute in parallel with minimal communication overhead. Importantly, our secure version of graph-based algorithms incurs a small logarithmic overhead in comparison with the non-secure parallel version. We build Graph SC and demonstrate, using several algorithms as examples, that secure computation can be brought into the realm of practicality for big data analysis. Our secure matrix factorization implementation can process 1 million ratings in 13 hours, which is a multiple order-of-magnitude improvement over the only other existing attempt, which requires 3 hours to process 16K ratings.
BibTeX
@inproceedings{nayak2015graphsc,
  author = {Kartik Nayak and Xiao Shaun Wang and Stratis Ioannidis and Udi Weinsberg and Nina Taft and Elaine Shi},
  title = {{GraphSC: Parallel Secure Computation Made Easy}},
  booktitle = {IEEE Symposium on Security and Privacy},
  year = {2015},
  doi = {10.1109/sp.2015.30},
}
Figure