skip to main content
10.1145/3302424.3303982acmconferencesArticle/Chapter ViewAbstractPublication PageseurosysConference Proceedingsconference-collections
research-article
Public Access

Conclave: secure multi-party computation on big data

Published: 25 March 2019 Publication History

Abstract

Secure Multi-Party Computation (MPC) allows mutually distrusting parties to run joint computations without revealing private data. Current MPC algorithms scale poorly with data size, which makes MPC on "big data" prohibitively slow and inhibits its practical use.
Many relational analytics queries can maintain MPC's end-to-end security guarantee without using cryptographic MPC techniques for all operations. Conclave is a query compiler that accelerates such queries by transforming them into a combination of data-parallel, local cleartext processing and small MPC steps. When parties trust others with specific subsets of the data, Conclave applies new hybrid MPC-cleartext protocols to run additional steps outside of MPC and improve scalability further.
Our Conclave prototype generates code for cleartext processing in Python and Spark, and for secure MPC using the Sharemind and Obliv-C frameworks. Conclave scales to data sets between three and six orders of magnitude larger than state-of-the-art MPC frameworks support on their own. Thanks to its hybrid protocols and additional optimizations, Conclave also substantially outperforms SMCQL, the most similar existing system.

References

[1]
Toshinori Araki, Jun Furukawa, Yehuda Lindell, Ariel Nof, and Kazuma Ohara. "High-Throughput Semi-Honest Secure Three-Party Computation with an Honest Majority". In: Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security (CCS). Vienna, Austria, Oct. 2016, pp. 805--817.
[2]
Toshinori Araki, Assi Barak, Jun Furukawa, Tamar Lichter, Yehuda Lindell, Ariel Nof, Kazuma Ohara, et al. "Optimized Honest-Majority MPC for Malicious Adversaries -- Breaking the 1 Billion-Gate Per Second Barrier". In: Proceedings of the 38th IEEE Symposium on Security and Privacy (SP). May 2017, pp. 843--862.
[3]
Johes Bater, Gregory Elliott, Craig Eggen, Satyender Goel, Abel Kho, and Jennie Rogers. "SMCQL: Secure Querying for Federated Databases". In: Proceedings of the VLDB Endowment 10.6 (Feb. 2017), pp. 673--684.
[4]
Donald Beaver. "Efficient Multiparty Protocols Using Circuit Randomization". In: Proceedings of the 11th Annual International Cryptology Conference (CRYPTO). Santa Barbara, California, USA, Aug. 1991, pp. 420--432.
[5]
Donald Beaver. "Precomputing Oblivious Transfer". In: Proceedings of the 15th Annual International Cryptology Conference (CRYPTO). Santa Barbara, California, USA, Aug. 1995, pp. 97--109.
[6]
Michael Ben-Or, Shafi Goldwasser, and Avi Wigderson. "Completeness Theorems for Non-Cryptographic Fault-Tolerant Distributed Computation (Extended Abstract)". In: Proceedings of the 20th Annual ACM Symposium on Theory of Computing (TC). Chicago, Illinois, USA, May 1988, pp. 1--10.
[7]
Azer Bestavros, Andrei Lapets, and Mayank Varia. "User-centric distributed solutions for privacy-preserving analytics". In: Communications of the ACM 60.2 (2017), pp. 37--39.
[8]
Dimitrios Bisias, Mark Flood, Andrew W. Lo, and Stavros Valavanis. "A Survey of Systemic Risk Analytics". In: Annual Review of Financial Economics 4.1 (2012), pp. 255--296. eprint:
[9]
Andrea Bittau, Ulfar Erlingsson, Petros Maniatis, Ilya Mironov, Ananth Raghunathan, David Lie, Mitch Rudominer, et al. "Prochlo: Strong privacy for analytics in the crowd". In: Proceedings of the 26th Symposium on Operating Systems Principles (SOSP). Shanghai, China, 2017, pp. 441--459.
[10]
Dan Bogdanov, Marko Jõemets, Sander Siim, and Meril Vaht. "How the Estonian Tax and Customs Board Evaluated a Tax Fraud Detection System Based on Secure Multi-party Computation". In: Proceedings of the 19th International Conference on Financial Cryptography and Data Security. San Juan, Puerto Rico, Jan. 2015, pp. 227--234.
[11]
Dan Bogdanov, Liina Kamm, Baldur Kubo, Reimo Rebane, Ville Sokk, and Riivo Talviste. "Students and Taxes: a Privacy-Preserving Study Using Secure Computation". In: Proceedings on Privacy Enhancing Technologies (PoPETS) 2016.3 (2016), pp. 117--135.
[12]
Dan Bogdanov, Sven Laur, and Jan Willemson. "Sharemind: A Framework for Fast Privacy-Preserving Computations". In: Proceedings of the 13th European Symposium on Research in Computer Security. Ed. by Sushil Jajodia and Javier Lopez. Vol. 5283. Lecture Notes in Computer Science. Springer Berlin/Heidelberg, 2008, pp. 192--206.
[13]
Peter Bogetoft, Dan Lund Christensen, Ivan Damgård, Martin Geisler, Thomas Jakobsen, Mikkel Krøigaard, Janus Dam Nielsen, et al. "Financial Cryptography and Data Security". In: ed. by Roger Dingledine and Philippe Golle. Berlin, Heidelberg: Springer-Verlag, 2009. Chap. Secure Multiparty Computation Goes Live, pp. 325--343.
[14]
Christoph Bösch, Pieter H. Hartel, Willem Jonker, and Andreas Peter. "A Survey of Provably Secure Searchable Encryption". In: ACM Computing Surveys 47.2 (2014), 18:1--18:51.
[15]
Elette Boyle, Kai-Min Chung, and Rafael Pass. "Large-Scale Secure Computation: Multi-party Computation for (Parallel) RAM Programs". In: Proceedings of the 35th Annual International Cryptology Conference (CRYPTO). Santa Barbara, California, USA, Aug. 2015, pp. 742--762.
[16]
Ronnie Chaiken, Bob Jenkins, Per-Åke Larson, Bill Ramsey, Darren Shakib, Simon Weaver, and Jingren Zhou. "SCOPE: Easy and Efficient Parallel Processing of Massive Data Sets". In: Proceedings of the VLDB Endowment 1.2 (Aug. 2008), pp. 1265--1276.
[17]
Nishanth Chandran, Wutichai Chongchitmate, Juan A. Garay, Shafi Goldwasser, Rafail Ostrovsky, and Vassilis Zikas. "The Hidden Graph Model: Communication Locality and Optimal Resiliency with Adaptive Faults". In: Proceedings of the 2015 Conference on Innovations in Theoretical Computer Science (ITCS). Rehovot, Israel, Jan. 2015, pp. 153--162.
[18]
Varsha Dani, Valerie King, Mahnush Movahedi, and Jared Saia. "Quorums Quicken Queries: Efficient Asynchronous Secure Multiparty Computation". In: Proceedings of the 15th International Conference on Distributed Computing and Networking (ICDCN). Coimbatore, India, Jan. 2014, pp. 242--256.
[19]
Varsha Dani, Valerie King, Mahnush Movahedi, Jared Saia, and Mahdi Zamani. "Secure multi-party computation in large networks". In: Distributed Computing 30.3 (2017), pp. 193--229.
[20]
Jack Doerner, David Evans, and Abhi Shelat. "Secure Stable Matching at Scale". In: Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security. 2016, pp. 1602--1613.
[21]
Cynthia Dwork. "Differential Privacy: A Survey of Results". In: Proceedings of the 5th International Conference on Theory and Applications of Models of Computation. Xi'an, China, 2008, pp. 1--19.
[22]
Sky Faber, Stanislaw Jarecki, Hugo Krawczyk, Quan Nguyen, Marcel-Catalin Rosu, and Michael Steiner. "Rich Queries on Encrypted Data: Beyond Exact Matches". In: Proceedings of the 20th European Symposium on Research in Computer Security (ESORICS). Vienna, Austria, Sept. 2015, pp. 123--145.
[23]
Benjamin Fuller, Mayank Varia, Arkady Yerukhimovich, Emily Shen, Ariel Hamlin, Vijay Gadepally, Richard Shay, et al. "SoK: Cryptographically Protected Database Search". In: Proceedings of the 2017 IEEE Symposium on Security and Privacy (SP). San Jose, California, USA, May 2017, pp. 172--191.
[24]
Jun Furukawa, Yehuda Lindell, Ariel Nof, and Or Weinstein. "High-Throughput Secure Three-Party Computation for Malicious Adversaries and an Honest Majority". In: Proceedings of the 36th Annual International Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT). Paris, France, Apr. 2017, pp. 225--255.
[25]
Adrià Gascón, Phillipp Schoppmann, Borja Balle, Mariana Raykova, Jack Doerner, Samee Zahur, and David Evans. "Privacy Preserving Distributed Linear Regression on High-Dimensional Data". In: Proceedings on Privacy Enhancing Technologies (PoPETs). Oct. 2017, pp. 345--364.
[26]
Ionel Gog, Malte Schwarzkopf, Natacha Crooks, Matthew P. Grosvenor, Allen Clement, and Steven Hand. "Musketeer: all for one, one for all in data processing systems". In: Proceedings of the 10th ACM European Conference on Computer Systems (EuroSys). Bordeaux, France, Apr. 2015.
[27]
Oded Goldreich. The Foundations of Cryptography -- Volume 1, Basic Techniques. Cambridge University Press, 2004.
[28]
Oded Goldreich, Silvio Micali, and Avi Wigderson. "How to Play any Mental Game or A Completeness Theorem for Protocols with Honest Majority". In: Proceedings of the 19th Annual ACM Symposium on Theory of Computing (TC). New York City, New York, USA, 1987, pp. 218--229.
[29]
Ariel Hamlin, Nabil Schear, Emily Shen, Mayank Varia, Sophia Yakoubov, and Arkady Yerukhimovich. "Cryptography for Big Data Security". In: Big Data: Storage, Sharing, and Security. Ed. by Fei Hu. Taylor & Francis LLC, CRC Press, 2016.
[30]
Xi He, Ashwin Machanavajjhala, Cheryl J. Flynn, and Divesh Srivastava. "Scaling Private Record Linkage using Output Constrained Differential Privacy". In: CoRR abs/1702.00535 (2017). arXiv: 1702.00535.
[31]
Albert O. Hirschman. "The Paternity of an Index". In: The American Economic Review 54.5 (1964), pp. 761--762.
[32]
Mihaela Ion, Ben Kreuter, Erhan Nergiz, Sarvar Patel, Shobhit Saxena, Karn Seth, David Shanahan, et al. "Private Intersection-Sum Protocol with Applications to Attributing Aggregate Ad Conversions". In: IACR Cryptology ePrint Archive (July 2017). IACR: 2017/ 738.
[33]
Mohammad Islam, Angelo K. Huang, Mohamed Battisha, Michelle Chiang, Santhosh Srinivasan, Craig Peters, Andreas Neumann, et al. "Oozie: Towards a Scalable Workflow Management System for Hadoop". In: Proceedings of the 1st ACM SIGMOD Workshop on Scalable Workflow Execution Engines and Technologies (SWEET). Scottsdale, Arizona, USA, 2012, 4:1--4:10.
[34]
Roman Jagomägis. "SecreC: a privacy-aware programming language with applications in data mining". In: Master's thesis, University of Tartu (2010).
[35]
Noah M. Johnson, Joseph P. Near, and Dawn Song. "Practical Differential Privacy for SQL Queries Using Elastic Sensitivity". In: CoRR abs/1706.09479 (2017). arXiv: 1706.09479.
[36]
Kristján Valur Jónsson, Gunnar Kreitz, and Misbah Uddin. "Secure multi-party sorting and applications". In: Proceedings of the 9th International Conference on Applied Cryptography and Network Security (ACNS). Nerja (Malaga), Spain, June 2011.
[37]
Seny Kamara and Tarik Moataz. SQL on Structurally-Encrypted Databases. 2016. IACR: 2016/453.
[38]
Seny Kamara, Payman Mohassel, and Mariana Raykova. "Outsourcing Multi-Party Computation". In: IACR Cryptology ePrint Archive 2011 (2011), p. 272. IACR: 2011/272.
[39]
Seny Kamara, Payman Mohassel, Mariana Raykova, and Saeed Sadeghian. "Scaling private set intersection to billion-element sets". In: International Conference on Financial Cryptography and Data Security. Springer. 2014, pp. 195--215.
[40]
Seny Kamara, Payman Mohassel, and Ben Riva. "Salus: a system for server-aided secure function evaluation". In: Proceedings of the 2012 ACM Conference on Computer and Communications Security. 2012, pp. 797--808.
[41]
Florian Kerschbaum. "Expression Rewriting for Optimizing Secure Computation". In: Proceedings of the 3rd ACM Conference on Data and Application Security and Privacy (CODASPY). San Antonio, Texas, USA, 2013, pp. 49--58.
[42]
Peeter Laud. "Parallel Oblivious Array Access for Secure Multiparty Computation and Privacy-Preserving Minimum Spanning Trees". In: Proceedings on Privacy Enhancing Technologies (PoPETS) 2015.2 (2015), pp. 188--205.
[43]
Yehuda Lindell and Benny Pinkas. "Secure multiparty computation for privacy-preserving data mining". In: Journal of Privacy and Confidentiality 1.1 (2009), p. 5.
[44]
Chang Liu, Xiao Shaun Wang, Kartik Nayak, Yan Huang, and Elaine Shi. "ObliVM: A Programming Framework for Secure Computation". In: Proceedings of the 2015 IEEE Symposium on Security and Privacy (SP). San Jose, California, USA, May 2015, pp. 359--376.
[45]
Erik Meijer, Brian Beckman, and Gavin Bierman. "LINQ: Reconciling Object, Relations and XML in the .NET Framework". In: Proceedings of the 2006 ACM SIGMOD International Conference on Management of Data (SIGMOD). Chicago, Illinois, USA, 2006, pp. 706--706.
[46]
Arjun Narayan and Andreas Haeberlen. "DJoin: Differentially Private Join Queries over Distributed Databases". In: Proceedings of the 10th USENIX Conference on Operating Systems Design and Implementation (OSDI). Hollywood, California, USA, Oct. 2012, pp. 149--162.
[47]
Kartik Nayak, Xiao Shaun Wang, Stratis Ioannidis, Udi Weinsberg, Nina Taft, and Elaine Shi. "GraphSC: Parallel Secure Computation Made Easy". In: Proceedings of the 2015 IEEE Symposium on Security and Privacy (SP). San Jose, California, USA, May 2015, pp. 377--394.
[48]
New York City Taxi & Limousine Commission. Taxi-cab Factbook. 2014. URL: http://www.nyc.gov/html/tlc/downloads/pdf/2014_taxicab_fact_book.pdf.
[49]
Christopher Olston, Benjamin Reed, Utkarsh Srivastava, Ravi Kumar, and Andrew Tomkins. "Pig Latin: A Not-So-Foreign Language for Data Processing". In: Proceedings of SIGMOD. 2008, pp. 1099--1110.
[50]
Antonis Papadimitriou, Arjun Narayan, and Andreas Haeberlen. "DStress: Efficient Differentially Private Computations on Distributed Data". In: Proceedings of the 12th European Conference on Computer Systems (EuroSys). Belgrade, Serbia, 2017, pp. 560--574.
[51]
Vasilis Pappas, Fernando Krell, Binh Vo, Vladimir Kolesnikov, Tal Malkin, Seung Geol Choi, Wesley George, et al. "Blind Seer: A Scalable Private DBMS". In: 2014 IEEE Symposium on Security and Privacy (SP). Berkeley, California, USA, May 2014, pp. 359--374.
[52]
Tal Rabin and Michael Ben-Or. "Verifiable Secret Sharing and Multiparty Protocols with Honest Majority (Extended Abstract)". In: Proceedings of the 21st Annual ACM Symposium on Theory of Computing (TC). Seattle, Washington, USA, May 1989, pp. 73--85.
[53]
Aseem Rastogi, Matthew A. Hammer, and Michael Hicks. "Wysteria: A Programming Language for Generic, Mixed-Mode Multiparty Computations". In: Proceedings of the 2014 IEEE Symposium on Security and Privacy. Washington, DC, USA, 2014, pp. 655--670.
[54]
Todd W. Schneider. NYC taxi trip data. https://github.com/toddwschneider/nyc-taxi-data. Accessed 03/08/2016.
[55]
Adi Shamir. "How to share a secret". In: Communications of the ACM 22.11 (1979), pp. 612--613.
[56]
Ashish Thusoo, Joydeep Sen Sarma, Namit Jain, Zheng Shao, Prasad Chakka, Suresh Anthony, Hao Liu, et al. "Hive -- A Warehousing Solution over a Map-Reduce Framework". In: Proceedings of the VLDB Endowment 2.2 (2009), pp. 1626--1629.
[57]
U.S. Census Bureau. "Table 1188 -- Credit Cards-Holders, Number, Spending, Debt, and Projections". In: Statistical Abstract of the United States: 2012. 131st ed. Aug. 2011. Chap. 25: Banking, Finance, and Insurance.
[58]
U.S. Department of Justice and U.S. Federal Trade Commission. Horizontal Merger Guidelines. Available at https://www.justice.gov/atr/horizontal-merger-guidelines-08192010. Aug. 2010.
[59]
U.S. Office of the Comptroller of the Currency. URL: https://www.occ.treas.gov/.
[60]
U.S. Social Security Administration. Social Security FAQs. Q20. URL: https://www.ssa.gov/history/hfaq.html.
[61]
Nikolaj Volgushev, Malte Schwarzkopf, Ben Getchell, Mayank Varia, Andrei Lapets, and Azer Bestavros. Conclave: secure multiparty computation on big data (Extended Technical Report). Mar. 2019. arXiv: 1902. 06288 {cs.CR}.
[62]
Andrew C. Yao. "Protocols for Secure Computations". In: Proceedings of the 23rd Annual Symposium on Foundations of Computer Science (AFCS). Washington, DC, USA, 1982, pp. 160--164.
[63]
Yuan Yu, Michael Isard, Dennis Fetterly, Mihai Budiu, Úlfar Erlingsson, Pradeep Kumar Gunda, and Jon Currey. "DryadLINQ: A System for General-Purpose Distributed Data-Parallel Computing Using a High-Level Language". In: Proceedings of the 8th USENIX Symposium on Operating Systems Design and Implementation (OSDI). San Diego, California, USA, Dec. 2008.
[64]
Matei Zaharia, Mosharaf Chowdhury, Tathagata Das, Ankur Dave, Justin Ma, Murphy McCauley, Michael J. Franklin, et al. "Resilient Distributed Datasets: A Fault-tolerant Abstraction for In-memory Cluster Computing". In: Proceedings of the 9th USENIX Conference on Networked Systems Design and Implementation (NSDI). San Jose, California, USA, Apr. 2012, pp. 15--28.
[65]
Samee Zahur and David Evans. Obliv-C: A Language for Extensible Data-Oblivious Computation. http://eprint.iacr.org/2015/1153. 2015. IACR: 2015/1153.
[66]
Wenting Zheng, Ankur Dave, Jethro G. Beekman, Raluca Ada Popa, Joseph E. Gonzalez, and Ion Stoica. "Opaque: An Oblivious and Encrypted Distributed Analytics Platform". In: Proceedings of the 14th USENIX Symposium on Networked Systems Design and Implementation (NSDI). Boston, Massachusetts, USA, 2017, pp. 283--298.

Cited By

View all
  • (2024)Secure Multiparty Computation Using Secure Virtual MachinesElectronics10.3390/electronics1305099113:5(991)Online publication date: 5-Mar-2024
  • (2024)SecretFlow-SCQL: A Secure Collaborative Query PlatformProceedings of the VLDB Endowment10.14778/3685800.368582117:12(3987-4000)Online publication date: 1-Aug-2024
  • (2024)GEN-RWD Sandbox: bridging the gap between hospital data privacy and external research insights with distributed analyticsBMC Medical Informatics and Decision Making10.1186/s12911-024-02549-524:1Online publication date: 17-Jun-2024
  • Show More Cited By

Recommendations

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences
EuroSys '19: Proceedings of the Fourteenth EuroSys Conference 2019
March 2019
714 pages
ISBN:9781450362818
DOI:10.1145/3302424
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 25 March 2019

Permissions

Request permissions for this article.

Check for updates

Qualifiers

  • Research-article
  • Research
  • Refereed limited

Funding Sources

Conference

EuroSys '19
Sponsor:
EuroSys '19: Fourteenth EuroSys Conference 2019
March 25 - 28, 2019
Dresden, Germany

Acceptance Rates

Overall Acceptance Rate 241 of 1,308 submissions, 18%

Upcoming Conference

EuroSys '25
Twentieth European Conference on Computer Systems
March 30 - April 3, 2025
Rotterdam , Netherlands

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)641
  • Downloads (Last 6 weeks)98
Reflects downloads up to 05 Nov 2024

Other Metrics

Citations

Cited By

View all
  • (2024)Secure Multiparty Computation Using Secure Virtual MachinesElectronics10.3390/electronics1305099113:5(991)Online publication date: 5-Mar-2024
  • (2024)SecretFlow-SCQL: A Secure Collaborative Query PlatformProceedings of the VLDB Endowment10.14778/3685800.368582117:12(3987-4000)Online publication date: 1-Aug-2024
  • (2024)GEN-RWD Sandbox: bridging the gap between hospital data privacy and external research insights with distributed analyticsBMC Medical Informatics and Decision Making10.1186/s12911-024-02549-524:1Online publication date: 17-Jun-2024
  • (2024)An Experimental Study on Federated Equi-JoinsIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2024.337502836:9(4443-4457)Online publication date: Sep-2024
  • (2024)Towards Practical Oblivious Join ProcessingIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2023.331003836:4(1829-1842)Online publication date: Apr-2024
  • (2024)Distributed Differential Privacy via Shuffling Versus Aggregation: A Curious StudyIEEE Transactions on Information Forensics and Security10.1109/TIFS.2024.335147419(2501-2516)Online publication date: 2024
  • (2024) Prism: Pr ivacy-Preserving and Ver i fiable S et Computation Over M ulti-Owner Secret Shared Outsourced Databases IEEE Transactions on Dependable and Secure Computing10.1109/TDSC.2023.327935621:3(1355-1371)Online publication date: May-2024
  • (2024)Practical Multi-Source Multi-Client Searchable Encryption With Forward Privacy: Refined Security Notion and New ConstructionsIEEE Transactions on Dependable and Secure Computing10.1109/TDSC.2023.324563821:1(63-77)Online publication date: Jan-2024
  • (2024)Synq: Public Policy Analytics Over Encrypted Data2024 IEEE Symposium on Security and Privacy (SP)10.1109/SP54263.2024.00085(146-165)Online publication date: 19-May-2024
  • (2024)FedCTQ: A Federated-Based Framework for Accurate and Efficient Contact Tracing Query2024 IEEE 40th International Conference on Data Engineering (ICDE)10.1109/ICDE60146.2024.00352(4628-4642)Online publication date: 13-May-2024
  • Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Get Access

Login options

Media

Figures

Other

Tables

Share

Share

Share this Publication link

Share on social media