Document Open Access Logo

MPC with Low Bottleneck-Complexity: Information-Theoretic Security and More

Authors Hannah Keller , Claudio Orlandi , Anat Paskin-Cherniavsky, Divya Ravi

PDF
Thumbnail PDF

File

LIPIcs.ITC.2023.11.pdf
  • Filesize: 0.94 MB
  • 22 pages

Document Identifiers

Author Details

Hannah Keller
  • Aarhus University, Denmark
Claudio Orlandi
  • Aarhus University, Denmark
Anat Paskin-Cherniavsky
  • Ariel University, Israel
Divya Ravi
  • Aarhus University, Denmark

Funding

  • Keller, Hannah: European Research Council (ERC) under the European Unions’s Horizon 2020 research and innovation programme under grant agreement No 803096 (SPEC).
  • Orlandi, Claudio: Concordium Blockhain Research Center, Aarhus University, Denmark; the Carlsberg Foundation under the Semper Ardens Research Project CF18-112 (BCM); the European Research Council (ERC) under the European Unions’s Horizon 2020 research and innovation programme under grant agreement No 803096 (SPEC).
  • Ravi, Divya: European Research Council (ERC) under the European Unions’s Horizon 2020 research and innovation programme under grant agreement No 803096 (SPEC).

Cite As Get BibTex

Hannah Keller, Claudio Orlandi, Anat Paskin-Cherniavsky, and Divya Ravi. MPC with Low Bottleneck-Complexity: Information-Theoretic Security and More. In 4th Conference on Information-Theoretic Cryptography (ITC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 267, pp. 11:1-11:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023) https://doi.org/10.4230/LIPIcs.ITC.2023.11

Abstract

The bottleneck-complexity (BC) of secure multiparty computation (MPC) protocols is a measure of the maximum number of bits which are sent and received by any party in protocol. As the name suggests, the goal of studying BC-efficient protocols is to increase overall efficiency by making sure that the workload in the protocol is somehow "amortized" by the protocol participants.
Orlandi et al. [Orlandi et al., 2022] initiated the study of BC-efficient protocols from simple assumptions in the correlated randomness model and for semi-honest adversaries. In this work, we extend the study of [Orlandi et al., 2022] in two primary directions: (a) to a larger and more general class of functions and (b) to the information-theoretic setting. 
In particular, we offer semi-honest secure protocols for the useful function classes of abelian programs, "read-k" non-abelian programs, and "read-k" generalized formulas. 
Our constructions use a novel abstraction, called incremental function secret-sharing (IFSS), that can be instantiated with unconditional security or from one-way functions (with different efficiency trade-offs).

Subject Classification

ACM Subject Classification
  • Theory of computation → Cryptographic protocols
Keywords
  • Secure Multiparty Computation
  • Bottleneck Complexity
  • Information-theoretic

Metrics

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

Related Versions

References

  1. Prabhanjan Ananth, Saikrishna Badrinarayanan, Aayush Jain, Nathan Manohar, and Amit Sahai. From FE combiners to secure MPC and back. In Dennis Hofheinz and Alon Rosen, editors, TCC 2019, Part I, volume 11891 of LNCS, pages 199-228. Springer, Heidelberg, December 2019. URL: https://doi.org/10.1007/978-3-030-36030-6_9.
  2. David A. Mix Barrington. Bounded-width polynomial-size branching programs recognize exactly those languages in nc(1). In Juris Hartmanis, editor, Proceedings of the 18th Annual ACM Symposium on Theory of Computing, May 28-30, 1986, Berkeley, California, USA, pages 1-5. ACM, 1986. URL: https://doi.org/10.1145/12130.12131.
  3. David Arno Barrington. Width-3 permutation branching programs. Laboratory for Computer Science, Massachusetts Institute of Technology, 1985. Google Scholar
  4. Amos Beimel, Ariel Gabizon, Yuval Ishai, Eyal Kushilevitz, Sigurd Meldgaard, and Anat Paskin-Cherniavsky. Non-interactive secure multiparty computation. In Juan A. Garay and Rosario Gennaro, editors, CRYPTO 2014, Part II, volume 8617 of LNCS, pages 387-404. Springer, Heidelberg, August 2014. URL: https://doi.org/10.1007/978-3-662-44381-1_22.
  5. Mihir Bellare, Viet Tung Hoang, and Phillip Rogaway. Foundations of garbled circuits. In Ting Yu, George Danezis, and Virgil D. Gligor, editors, ACM CCS 2012, pages 784-796. ACM Press, October 2012. URL: https://doi.org/10.1145/2382196.2382279.
  6. Michael Ben-Or, Shafi Goldwasser, and Avi Wigderson. Completeness theorems for non-cryptographic fault-tolerant distributed computation (extended abstract). In 20th ACM STOC, pages 1-10. ACM Press, May 1988. URL: https://doi.org/10.1145/62212.62213.
  7. Elette Boyle, Niv Gilboa, and Yuval Ishai. Function secret sharing: Improvements and extensions. In Edgar R. Weippl, Stefan Katzenbeisser, Christopher Kruegel, Andrew C. Myers, and Shai Halevi, editors, ACM CCS 2016, pages 1292-1303. ACM Press, October 2016. URL: https://doi.org/10.1145/2976749.2978429.
  8. Elette Boyle, Shafi Goldwasser, and Stefano Tessaro. Communication locality in secure multi-party computation - how to run sublinear algorithms in a distributed setting. In Amit Sahai, editor, TCC 2013, volume 7785 of LNCS, pages 356-376. Springer, Heidelberg, March 2013. URL: https://doi.org/10.1007/978-3-642-36594-2_21.
  9. Elette Boyle, Abhishek Jain, Manoj Prabhakaran, and Ching-Hua Yu. The bottleneck complexity of secure multiparty computation. In Ioannis Chatzigiannakis, Christos Kaklamanis, Dániel Marx, and Donald Sannella, editors, ICALP 2018, volume 107 of LIPIcs, pages 24:1-24:16. Schloss Dagstuhl, July 2018. URL: https://doi.org/10.4230/LIPIcs.ICALP.2018.24.
  10. Ran Canetti. Security and composition of multiparty cryptographic protocols. Journal of Cryptology, 13(1):143-202, January 2000. URL: https://doi.org/10.1007/s001459910006.
  11. David Chaum, Claude Crépeau, and Ivan Damgård. Multiparty unconditionally secure protocols (extended abstract). In 20th ACM STOC, pages 11-19. ACM Press, May 1988. URL: https://doi.org/10.1145/62212.62214.
  12. Geoffroy Couteau. A note on the communication complexity of multiparty computation in the correlated randomness model. In Yuval Ishai and Vincent Rijmen, editors, EUROCRYPT 2019, Part II, volume 11477 of LNCS, pages 473-503. Springer, Heidelberg, May 2019. URL: https://doi.org/10.1007/978-3-030-17656-3_17.
  13. Ivan Damgård and Yuval Ishai. Scalable secure multiparty computation. In Cynthia Dwork, editor, CRYPTO 2006, volume 4117 of LNCS, pages 501-520. Springer, Heidelberg, August 2006. URL: https://doi.org/10.1007/11818175_30.
  14. Ivan Damgård, Yuval Ishai, Mikkel Krøigaard, Jesper Buus Nielsen, and Adam Smith. Scalable multiparty computation with nearly optimal work and resilience. In David Wagner, editor, CRYPTO 2008, volume 5157 of LNCS, pages 241-261. Springer, Heidelberg, August 2008. URL: https://doi.org/10.1007/978-3-540-85174-5_14.
  15. Ivan Damgård, Jesper Buus Nielsen, Antigoni Polychroniadou, and Michael Raskin. On the communication required for unconditionally secure multiplication. In Matthew Robshaw and Jonathan Katz, editors, CRYPTO 2016, Part II, volume 9815 of LNCS, pages 459-488. Springer, Heidelberg, August 2016. URL: https://doi.org/10.1007/978-3-662-53008-5_16.
  16. Reo Eriguchi, Kazuma Ohara, Shota Yamada, and Koji Nuida. Non-interactive secure multiparty computation for symmetric functions, revisited: More efficient constructions and extensions. In Tal Malkin and Chris Peikert, editors, CRYPTO, 2021. Google Scholar
  17. Rex Fernando, Yuval Gelles, Ilan Komargodski, and Elaine Shi. Maliciously secure massively parallel computation for all-but-one corruptions. In CRYPTO 2022, 2022. Google Scholar
  18. Rex Fernando, Ilan Komargodski, Yanyi Liu, and Elaine Shi. Secure massively parallel computation for dishonest majority. In Rafael Pass and Krzysztof Pietrzak, editors, TCC 2020, Part II, volume 12551 of LNCS, pages 379-409. Springer, Heidelberg, November 2020. URL: https://doi.org/10.1007/978-3-030-64378-2_14.
  19. Oded Goldreich, Silvio Micali, and Avi Wigderson. How to play any mental game or A completeness theorem for protocols with honest majority. In Alfred Aho, editor, 19th ACM STOC, pages 218-229. ACM Press, May 1987. URL: https://doi.org/10.1145/28395.28420.
  20. S. Dov Gordon, Tal Malkin, Mike Rosulek, and Hoeteck Wee. Multi-party computation of polynomials and branching programs without simultaneous interaction. In Thomas Johansson and Phong Q. Nguyen, editors, EUROCRYPT 2013, volume 7881 of LNCS, pages 575-591. Springer, Heidelberg, May 2013. URL: https://doi.org/10.1007/978-3-642-38348-9_34.
  21. Shai Halevi, Yuval Ishai, Abhishek Jain, Eyal Kushilevitz, and Tal Rabin. Secure multiparty computation with general interaction patterns. In Madhu Sudan, editor, ITCS 2016, pages 157-168. ACM, January 2016. URL: https://doi.org/10.1145/2840728.2840760.
  22. Shai Halevi, Yuval Ishai, Eyal Kushilevitz, and Tal Rabin. Best possible information-theoretic MPC. In Amos Beimel and Stefan Dziembowski, editors, TCC 2018, Part II, volume 11240 of LNCS, pages 255-281. Springer, Heidelberg, November 2018. URL: https://doi.org/10.1007/978-3-030-03810-6_10.
  23. Shai Halevi, Yehuda Lindell, and Benny Pinkas. Secure computation on the web: Computing without simultaneous interaction. In Phillip Rogaway, editor, CRYPTO 2011, volume 6841 of LNCS, pages 132-150. Springer, Heidelberg, August 2011. URL: https://doi.org/10.1007/978-3-642-22792-9_8.
  24. Yuval Ishai, Eyal Kushilevitz, Sigurd Meldgaard, Claudio Orlandi, and Anat Paskin-Cherniavsky. On the power of correlated randomness in secure computation. In Amit Sahai, editor, TCC 2013, volume 7785 of LNCS, pages 600-620. Springer, Heidelberg, March 2013. URL: https://doi.org/10.1007/978-3-642-36594-2_34.
  25. Yuval Ishai, Manika Mittal, and Rafail Ostrovsky. On the message complexity of secure multiparty computation. In Michel Abdalla and Ricardo Dahab, editors, PKC 2018, Part I, volume 10769 of LNCS, pages 698-711. Springer, Heidelberg, March 2018. URL: https://doi.org/10.1007/978-3-319-76578-5_24.
  26. Hannah Keller, Claudio Orlandi, Anat Paskin-Cherniavsky, and Divya Ravi. Mpc with low bottleneck-complexity: Information-theoretic security and more. Cryptology ePrint Archive, Paper 2023/683, 2023. URL: https://eprint.iacr.org/2023/683.
  27. Moni Naor and Kobbi Nissim. Communication preserving protocols for secure function evaluation. In 33rd ACM STOC, pages 590-599. ACM Press, July 2001. URL: https://doi.org/10.1145/380752.380855.
  28. Claudio Orlandi, Divya Ravi, and Peter Scholl. On the bottleneck complexity of mpc with correlated randomness. International Conference on Practice and Theory of Public-Key Cryptography, 2022. Google Scholar
  29. Willy Quach, Hoeteck Wee, and Daniel Wichs. Laconic function evaluation and applications. In Mikkel Thorup, editor, 59th FOCS, pages 859-870. IEEE Computer Society Press, October 2018. URL: https://doi.org/10.1109/FOCS.2018.00086.
  30. Andrew Chi-Chih Yao. Protocols for secure computations (extended abstract). In 23rd FOCS, pages 160-164. IEEE Computer Society Press, November 1982. URL: https://doi.org/10.1109/SFCS.1982.38.
  31. Andrew Chi-Chih Yao. How to generate and exchange secrets (extended abstract). In 27th FOCS, pages 162-167. IEEE Computer Society Press, October 1986. URL: https://doi.org/10.1109/SFCS.1986.25.
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