GraphSC: Parallel Secure Computation Made Easy
Venue
IEEE Symposium on Security and Privacy, IEEE (2015)
Publication Year
2015
Authors
Kartik Nayak, Xiao S. Wang, Stratis Ioannidis, Udi Weinsberg, Nina Taft, Elaine Shi
BibTeX
Abstract
We propose introducing modern parallel programming paradigms to secure computation,
enabling their secure execution on large datasets. To address this challenge, we
present GraphSC, 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 needs for obliviousness, thereby not
leaking any private information. Using GraphSC, 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 GraphSC 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.
