GraphSC: Parallel Secure Computation Made Easy

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

193 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Computational Theory and Mathematics, Computer Vision and Pattern Recognition

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Theory and Mathematics

In Computer Vision and Pattern Recognition

Citations in the corpus

Secure Evaluation of Quantized Neural Networks (2019, methodology): “This approach yields an improvement of a factor of 4–8 with respect to previous solutions to the arithmetic issue like embedding the computations in a large enough field to avoid overflows (as done in Cryptonets [22]) or using a garbled circuit to perform fixedpoint [21] or floating-point [42] multi”
QUOTIENT: Two-Party Secure Neural Network Training and Prediction (2019, methodology): “This framework has been used in several previous works [14, 29, 41–44].”
Privacy-Preserving Distributed Linear Regression on High-Dimensional Data (2017, methodology): “Popular applications used for the empirical evaluation of practical MPC systems include graph algorithms [5, 32, 42, 51, 57], data structure algorithms [42, 51], string matching and distance algorithms [36, 37, 66] and AES [3, 36, 37, 66].”
Observing and Preventing Leakage in MapReduce (2015, background): “[19] propose a programming model for secure parallel processing of data represented as a graph using oblivious sorting and garbled circuits.”
Secure Linear Regression on Vertically Partitioned Datasets (2016, methodology): “Popular applications used for the empirical evaluation of implemented systems include graph algorithms [6, 18, 24, 29, 34, 45], data structure algorithms [24,29,42], string matching and distance algorithms [20,21,39] and AES [4,20,21,39].”
Oblivious Multi-Party Machine Learning on Trusted Processors (2016, methodology): “, Nursery in [13], MovieLens in [47, 48]) or because they are one of the”
UnLynx: A Decentralized System for Privacy-Conscious Data Sharing (2017, background): “based on secret sharing (SS) [3, 14, 26, 49] or secure multiparty computation (SMPC) [11, 28, 33, 40, 42, 50] have intrinsic limitations in terms of control over data and scalability.”
SecureML: A System for Scalable Privacy-Preserving Machine Learning (2017, unknown): “or floating-point [35] multiplication on decimal numbers.”
Secure Function Evaluation Using an FPGA Overlay Architecture (2017, methodology): “Nevertheless, this approach to parallelization leaves much to be desired: for example, in [27], even under parallelization over 128 cores, executing a typical data-mining algorithm like Matrix Factorization through SFE is of the order of 10(5) slower compared to (parallel) execution in the clear.”
DStress: Efficient Differentially Private Computations on Distributed Data (2017, background): “Recently, work on two-party secure computation (2PC) has started considering graph computations as well [55, 56].”
Opaque: An Oblivious and Encrypted Distributed Analytics Platform (2017, methodology): “3×106x slowdown, and GraphSC [27] a slowdown of 2× 105x to 5× 105x.”
M2R: Enabling Stronger Privacy in MapReduce Computation (2015, result): “GraphSC offers a similar security guarantee to that of M 2 R for specialized graph-processing tasks [42].”
Towards Federated Graph Learning for Collaborative Financial Crimes Detection (2019, methodology): “GraphSC [Nayak et al., 2015] is one of such secure graph computation frameworks, and we have started to implement some graph features such as temporal cycle features.”