Document Open Access Logo

The Bottleneck Complexity of Secure Multiparty Computation

Authors Elette Boyle, Abhishek Jain, Manoj Prabhakaran, Ching-Hua Yu

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2018.24.pdf
  • Filesize: 0.51 MB
  • 16 pages

Document Identifiers

Author Details

Elette Boyle
  • IDC Herzliya
Abhishek Jain
  • Johns Hopkins University
Manoj Prabhakaran
  • Indian Institute of Technology Bombay
Ching-Hua Yu
  • University of Illinois at Urbana-Champaign

Cite As Get BibTex

Elette Boyle, Abhishek Jain, Manoj Prabhakaran, and Ching-Hua Yu. The Bottleneck Complexity of Secure Multiparty Computation. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 24:1-24:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.ICALP.2018.24

Abstract

In this work, we initiate the study of bottleneck complexity as a new communication efficiency measure for secure multiparty computation (MPC). Roughly, the bottleneck complexity of an MPC protocol is defined as the maximum communication complexity required by any party within the protocol execution.
We observe that even without security, bottleneck communication complexity is an interesting measure of communication complexity for (distributed) functions and propose it as a fundamental area to explore. While achieving O(n) bottleneck complexity (where n is the number of parties) is straightforward, we show that: (1) achieving sublinear bottleneck complexity is not always possible, even when no security is required. (2) On the other hand, several useful classes of functions do have o(n) bottleneck complexity, when no security is required.
Our main positive result is a compiler that transforms any (possibly insecure) efficient protocol with fixed communication-pattern for computing any functionality into a secure MPC protocol while preserving the bottleneck complexity of the underlying protocol (up to security parameter overhead). Given our compiler, an efficient protocol for any function f with sublinear bottleneck complexity can be transformed into an MPC protocol for f with the same bottleneck complexity.
Along the way, we build cryptographic primitives - incremental fully-homomorphic encryption, succinct non-interactive arguments of knowledge with ID-based simulation-extractability property and verifiable protocol execution - that may be of independent interest.

Subject Classification

ACM Subject Classification
  • Theory of computation → Cryptographic protocols
  • Theory of computation → Communication complexity
Keywords
  • distributed protocols
  • secure computation
  • communication complexity

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Gilad Asharov, Abhishek Jain, Adriana López-Alt, Eran Tromer, Vinod Vaikuntanathan, and Daniel Wichs. Multiparty computation with low communication, computation and interaction via threshold fhe. In EUROCRYPT, pages 483-501, 2012. Google Scholar
  2. Nir Bitansky, Ran Canetti, Alessandro Chiesa, and Eran Tromer. From extractable collision resistance to succinct non-interactive arguments of knowledge, and back again. In Innovations in Theoretical Computer Science 2012, Cambridge, MA, USA, January 8-10, 2012, pages 326-349, 2012. Google Scholar
  3. Nir Bitansky, Ran Canetti, Alessandro Chiesa, and Eran Tromer. Recursive composition and bootstrapping for SNARKS and proof-carrying data. In Symposium on Theory of Computing Conference, STOC'13, Palo Alto, CA, USA, June 1-4, 2013, pages 111-120, 2013. Google Scholar
  4. Elette Boyle, Kai-Min Chung, and Rafael Pass. Large-scale secure computation: Multi-party computation for (parallel) RAM programs. In Advances in Cryptology - CRYPTO 2015 - 35th Annual Cryptology Conference, Santa Barbara, CA, USA, August 16-20, 2015, Proceedings, Part II, pages 742-762, 2015. Google Scholar
  5. Elette Boyle, Shafi Goldwasser, and Stefano Tessaro. Communication locality in secure multi-party computation: how to run sublinear algorithms in a distributed setting. In Proceeding TCC'13 Proceedings of the 10th theory of cryptography conference on Theory of Cryptography, pages 356-376, 2013. Google Scholar
  6. Zvika Brakerski and Renen Perlman. Lattice-based fully dynamic multi-key FHE with short ciphertexts. In Advances in Cryptology - CRYPTO 2016 - 36th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 14-18, 2016, Proceedings, Part I, pages 190-213, 2016. Google Scholar
  7. Nicolas Braud-Santoni, Rachid Guerraoui, and Florian Huc. Fast byzantine agreement. In ACM Symposium on Principles of Distributed Computing, PODC '13, Montreal, QC, Canada, July 22-24, 2013, pages 57-64, 2013. Google Scholar
  8. Alessandro Chiesa and Eran Tromer. Proof-carrying data and hearsay arguments from signature cards. In Innovations in Computer Science - ICS 2010, Tsinghua University, Beijing, China, January 5-7, 2010. Proceedings, pages 310-331, 2010. Google Scholar
  9. Michael Clear and Ciaran McGoldrick. Multi-identity and multi-key leveled FHE from learning with errors. In Advances in Cryptology - CRYPTO 2015 - 35th Annual Cryptology Conference, Santa Barbara, CA, USA, August 16-20, 2015, Proceedings, Part II, pages 630-656, 2015. Google Scholar
  10. Ivan Damgård, Sebastian Faust, and Carmit Hazay. Secure two-party computation with low communication. In Theory of Cryptography - 9th Theory of Cryptography Conference, TCC 2012, Taormina, Sicily, Italy, March 19-21, 2012. Proceedings, pages 54-74, 2012. Google Scholar
  11. Ivan Damgård and Yuval Ishai. Scalable secure multiparty computation. In Advances in Cryptology - CRYPTO 2006, 26th Annual International Cryptology Conference, Santa Barbara, California, USA, August 20-24, 2006, Proceedings, pages 501-520, 2006. Google Scholar
  12. Ivan Damgård, Yuval Ishai, Mikkel Krøigaard, Jesper Buus Nielsen, and Adam D. Smith. Scalable multiparty computation with nearly optimal work and resilience. In Advances in Cryptology - CRYPTO 2008, 28th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 17-21, 2008. Proceedings, pages 241-261, 2008. Google Scholar
  13. Ivan Damgård, Jesper Buus Nielsen, Antigoni Polychroniadou, and Michael Raskin. On the communication required for unconditionally secure multiplication. In Crypto'16, pages 459-488, 2016. Google Scholar
  14. Varsha Dani, Valerie King, Mahnush Movahedi, and Jared Saia. Quorums quicken queries: Efficient asynchronous secure multiparty computation. In Distributed Computing and Networking - 15th International Conference, ICDCN 2014, Coimbatore, India, January 4-7, 2014. Proceedings, pages 242-256, 2014. Google Scholar
  15. Yevgeniy Dodis, Shai Halevi, Ron D. Rothblum, and Daniel Wichs. Spooky encryption and its applications. In Advances in Cryptology - CRYPTO 2016 - 36th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 14-18, 2016, Proceedings, Part III, pages 93-122, 2016. Google Scholar
  16. Dario Fiore and Anca Nitulescu. On the (in)security of snarks in the presence of oracles. In Theory of Cryptography - 14th International Conference, TCC 2016-B, Beijing, China, October 31 - November 3, 2016, Proceedings, Part I, pages 108-138, 2016. Google Scholar
  17. Christina Garman, Matthew Green, and Ian Miers. Accountable privacy for decentralized anonymous payments. In Financial Cryptography and Data Security - 20th International Conference, FC 2016, Christ Church, Barbados, February 22-26, 2016, Revised Selected Papers, pages 81-98, 2016. Google Scholar
  18. Minos N. Garofalakis, Johannes Gehrke, and Rajeev Rastogi, editors. Data Stream Management - Processing High-Speed Data Streams. Data-Centric Systems and Applications. Springer, 2016. URL: http://dx.doi.org/10.1007/978-3-540-28608-0.
  19. Craig Gentry, Amit Sahai, and Brent Waters. Homomorphic encryption from learning with errors: Conceptually-simpler, asymptotically-faster, attribute-based. In Crypto'13, pages 75-92, 2013. Google Scholar
  20. Oded Goldreich, Silvio Micali, and Avi Wigderson. How to play any mental game. In STOC, 1987. Google Scholar
  21. Jens Groth and Mary Maller. Snarky signatures: Minimal signatures of knowledge from simulation-extractable snarks. In Advances in Cryptology - CRYPTO 2017 - 37th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 20-24, 2017, Proceedings, Part II, pages 581-612, 2017. Google Scholar
  22. Divya Gupta and Amit Sahai. On constant-round concurrent zero-knowledge from a knowledge assumption. In Progress in Cryptology - INDOCRYPT 2014 - 15th International Conference on Cryptology in India, New Delhi, India, December 14-17, 2014, Proceedings, pages 71-88, 2014. Google Scholar
  23. Ahmed E. Kosba, Zhichao Zhao, Andrew Miller, Yi Qian, T.-H. Hubert Chan, Charalampos Papamanthou, Rafael Pass, Abhi Shelat, and Elaine Shi. How to use snarks in universally composable protocols. IACR Cryptology ePrint Archive, 2015:1093, 2015. URL: http://eprint.iacr.org/2015/1093.
  24. Eyal Kushilevitz and Noam Nisan. Communication complexity. Cambridge University Press, 1997. Google Scholar
  25. Adriana López-Alt, Eran Tromer, and Vinod Vaikuntanathan. On-the-fly multiparty computation on the cloud via multikey fully homomorphic encryption. In Proceedings of the 44th Symposium on Theory of Computing Conference, STOC 2012, New York, NY, USA, May 19 - 22, 2012, pages 1219-1234, 2012. Google Scholar
  26. Andrew McGregor. Graph stream algorithms: a survey. SIGMOD Record, 43:9-20, 2014. Google Scholar
  27. Pratyay Mukherjee and Daniel Wichs. Two round multiparty computation via multi-key FHE. In Advances in Cryptology - EUROCRYPT 2016 - 35th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Vienna, Austria, May 8-12, 2016, Proceedings, Part II, pages 735-763, 2016. Google Scholar
  28. Moni Naor and Kobbi Nissim. Communication preserving protocols for secure function evaluation. In Proceedings on 33rd Annual ACM Symposium on Theory of Computing (STOC), pages 590-599, 2001. Google Scholar
  29. Chris Peikert and Sina Shiehian. Multi-key FHE from lwe, revisited. In Theory of Cryptography - 14th International Conference, TCC 2016-B, Beijing, China, October 31 - November 3, 2016, Proceedings, Part II, pages 217-238, 2016. Google Scholar
  30. Amit Sahai. Non-malleable non-interactive zero knowledge and adaptive chosen-ciphertext security. In 40th Annual Symposium on Foundations of Computer Science, FOCS '99, 17-18 October, 1999, New York, NY, USA, pages 543-553, 1999. Google Scholar
  31. Alfredo De Santis, Giovanni Di Crescenzo, Rafail Ostrovsky, Giuseppe Persiano, and Amit Sahai. Robust non-interactive zero knowledge. In Advances in Cryptology - CRYPTO 2001, 21st Annual International Cryptology Conference, Santa Barbara, California, USA, August 19-23, 2001, Proceedings, pages 566-598, 2001. Google Scholar
  32. Andrew Chi-Chih Yao. Protocols for secure computations (extended abstract). In 23rd Annual Symposium on Foundations of Computer Science, Chicago, Illinois, USA, 3-5 November 1982, pages 160-164, 1982. Google Scholar
  33. Mahdi Zamani, Mahnush Movahedi, and Jared Saia. Millions of millionaires: Multiparty computation in large networks. IACR Cryptology ePrint Archive, 2014:149, 2014. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact