GraphSC: Parallel secure computation made easy

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

Research output: Chapter in Book/Report/Conference proceedingConference contribution

50 Scopus citations

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.

Original languageEnglish (US)
Title of host publicationProceedings - 2015 IEEE Symposium on Security and Privacy, SP 2015
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages377-394
Number of pages18
ISBN (Electronic)9781467369497
DOIs
Publication statusPublished - Jul 17 2015
Event36th IEEE Symposium on Security and Privacy, SP 2015 - San Jose, United States
Duration: May 18 2015May 20 2015

Publication series

NameProceedings - IEEE Symposium on Security and Privacy
Volume2015-July
ISSN (Print)1081-6011

Other

Other36th IEEE Symposium on Security and Privacy, SP 2015
CountryUnited States
CitySan Jose
Period5/18/155/20/15

    Fingerprint

Keywords

  • graph algorithms
  • oblivious algorithms
  • parallel algorithms
  • secure computation

ASJC Scopus subject areas

  • Safety, Risk, Reliability and Quality
  • Software
  • Computer Networks and Communications

Cite this

Nayak, K., Wang, X., Ioannidis, S., Weinsberg, U., Taft, N., & Shi, E. (2015). GraphSC: Parallel secure computation made easy. In Proceedings - 2015 IEEE Symposium on Security and Privacy, SP 2015 (pp. 377-394). [7163037] (Proceedings - IEEE Symposium on Security and Privacy; Vol. 2015-July). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/SP.2015.30