GraphSC: Parallel Secure Computation Made Easy
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.
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.
Research Areas
