Document Open Access Logo

Static vs. Adaptive Security in Perfect MPC: A Separation and the Adaptive Security of BGW

Authors Gilad Asharov , Ran Cohen , Oren Shochat

PDF
Thumbnail PDF

File

LIPIcs.ITC.2022.15.pdf
  • Filesize: 0.73 MB
  • 16 pages

Document Identifiers

Author Details

Gilad Asharov
  • Department of Computer Science, Bar-Ilan University, Ramat-Gan, Israel
Ran Cohen
  • Efi Arazi School of Computer Science, Reichman University, Herzliya, Israel
Oren Shochat
  • Department of Computer Science, Bar-Ilan University, Ramat-Gan Israel

Funding

  • Asharov, Gilad: Sponsored by the Israel Science Foundation (grant No. 2439/20), by JPM Faculty Research Award, by the BIU Center for Research in Applied Cryptography and Cyber Security in conjunction with the Israel National Cyber Bureau in the Prime Minister’s Office, and by the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie grant agreement No. 891234.
  • Cohen, Ran: Research partially supported by NSF grant no. 2055568.
  • Shochat, Oren: Sponsored by the Israel Science Foundation (grant No. 2439/20).

Cite As Get BibTex

Gilad Asharov, Ran Cohen, and Oren Shochat. Static vs. Adaptive Security in Perfect MPC: A Separation and the Adaptive Security of BGW. In 3rd Conference on Information-Theoretic Cryptography (ITC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 230, pp. 15:1-15:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022) https://doi.org/10.4230/LIPIcs.ITC.2022.15

Abstract

Adaptive security is a highly desirable property in the design of secure protocols. It tolerates adversaries that corrupt parties as the protocol proceeds, as opposed to static security where the adversary corrupts the parties at the onset of the execution. The well-accepted folklore is that static and adaptive securities are equivalent for perfectly secure protocols. Indeed, this folklore is backed up with a transformation by Canetti et al. (EUROCRYPT'01), showing that any perfectly secure protocol that is statically secure and satisfies some basic requirements is also adaptively secure. Yet, the transformation results in an adaptively secure protocol with inefficient simulation (i.e., where the simulator might run in super-polynomial time even if the adversary runs just in polynomial time). Inefficient simulation is problematic when using the protocol as a sub-routine in the computational setting.
Our main question is whether an alternative efficient transformation from static to adaptive security exists. We show an inherent difficulty in achieving this goal generically. In contrast to the folklore, we present a protocol that is perfectly secure with efficient static simulation (therefore also adaptively secure with inefficient simulation), but for which efficient adaptive simulation does not exist (assuming the existence of one-way permutations).
In addition, we prove that the seminal protocol of Ben-Or, Goldwasser and Wigderson (STOC'88) is secure against adaptive, semi-honest corruptions with efficient simulation. Previously, adaptive security of the protocol, as is, was only known either for a restricted class of circuits, or for all circuits but with inefficient simulation.

Subject Classification

ACM Subject Classification
  • Security and privacy → Information-theoretic techniques
Keywords
  • secure multiparty computation
  • perfect security
  • adaptive security
  • BGW protocol

Metrics

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

Related Versions

References

  1. Gilad Asharov and Yehuda Lindell. A full proof of the BGW protocol for perfectly-secure multiparty computation. IACR Cryptol. ePrint Arch., 2011. URL: http://eprint.iacr.org/2011/136.
  2. Gilad Asharov and Yehuda Lindell. A full proof of the BGW protocol for perfectly secure multiparty computation. Journal of Cryptology, 30(1):58-151, 2017. Google Scholar
  3. Michael Backes, Jörn Müller-Quade, and Dominique Unruh. On the necessity of rewinding in secure multiparty computation. In Proceedings of the Fourth Theory of Cryptography Conference, TCC 2007, pages 157-173, 2007. Google Scholar
  4. Donald Beaver and Stuart Haber. Cryptographic protocols provably secure against dynamic adversaries. In Advances in Cryptology - EUROCRYPT 1992, pages 307-323, 1992. Google Scholar
  5. 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 (STOC), pages 1-10, 1988. Google Scholar
  6. Elette Boyle, Ran Cohen, Deepesh Data, and Pavel Hubáček. Must the communication graph of MPC protocols be an expander? In Advances in Cryptology - CRYPTO 2018, part III, pages 243-272, 2018. Google Scholar
  7. Ran Canetti. Security and composition of multiparty cryptographic protocols. Journal of Cryptology, 13(1):143-202, 2000. Google Scholar
  8. Ran Canetti. Universally Composable Security: A New Paradigm for Cryptographic Protocols. In Proceedings of the 42nd Annual Symposium on Foundations of Computer Science (FOCS), pages 136-145, 2001. Google Scholar
  9. Ran Canetti, Ivan Damgård, Stefan Dziembowski, Yuval Ishai, and Tal Malkin. Adaptive versus non-adaptive security of multi-party protocols. Journal of Cryptology, 17(3):153-207, 2004. Google Scholar
  10. Ran Canetti, Uriel Feige, Oded Goldreich, and Moni Naor. Adaptively secure multi-party computation. In Proceedings of the 28th Annual ACM Symposium on Theory of Computing (STOC), pages 639-648, 1996. Google Scholar
  11. David Chaum, Claude Crépeau, and Ivan Damgård. Multiparty unconditionally secure protocols (extended abstract). In Proceedings of the 20th Annual ACM Symposium on Theory of Computing (STOC), pages 11-19, 1988. Google Scholar
  12. Ran Cohen, Juan A. Garay, and Vassilis Zikas. Completeness theorems for adaptively secure broadcast. IACR Cryptol. ePrint Arch., 2021. URL: http://eprint.iacr.org/2021/775.
  13. Ran Cohen, Abhi Shelat, and Daniel Wichs. Adaptively secure MPC with sublinear communication complexity. In Advances in Cryptology - CRYPTO 2019, part II, pages 30-60, 2019. Google Scholar
  14. Ronald Cramer, Ivan Damgård, Stefan Dziembowski, Martin Hirt, and Tal Rabin. Efficient multiparty computations secure against an adaptive adversary. In Advances in Cryptology - EUROCRYPT 1999, pages 311-326, 1999. Google Scholar
  15. Ivan Damgård and Jesper Buus Nielsen. Adaptive versus static security in the UC model. In Proceedings of the 8th International Conference on Provable Security (ProvSec), Lecture Notes in Computer Science, pages 10-28, 2014. Google Scholar
  16. Yevgeniy Dodis and Silvio Micali. Parallel reducibility for information-theoretically secure computation. In Advances in Cryptology - CRYPTO 2000, pages 74-92, 2000. Google Scholar
  17. Juan A. Garay, Yuval Ishai, Rafail Ostrovsky, and Vassilis Zikas. The price of low communication in secure multi-party computation. In Advances in Cryptology - CRYPTO 2017, part I, pages 420-446, 2017. Google Scholar
  18. Sanjam Garg and Amit Sahai. Adaptively secure multi-party computation with dishonest majority. In Advances in Cryptology - CRYPTO 2012, pages 105-123, 2012. Google Scholar
  19. Oded Goldreich. Foundations of Cryptography - VOLUME 2: Basic Applications. Cambridge University Press, 2004. Google Scholar
  20. 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 (STOC), pages 218-229, 1987. Google Scholar
  21. Martin Hirt, Chen-Da Liu-Zhang, and Ueli Maurer. Adaptive security of multi-party protocols, revisited. In Proceedings of the 19th Theory of Cryptography Conference, TCC 2021, part I, pages 686-716, 2021. Google Scholar
  22. Martin Hirt and Vassilis Zikas. Adaptively secure broadcast. In Advances in Cryptology - EUROCRYPT 2010, pages 466-485, 2010. Google Scholar
  23. Jonathan Katz, Aishwarya Thiruvengadam, and Hong-Sheng Zhou. Feasibility and infeasibility of adaptively secure fully homomorphic encryption. In Proceedings of the 16th International Conference on the Theory and Practice of Public-Key Cryptography (PKC), pages 14-31, 2013. Google Scholar
  24. Eyal Kushilevitz, Yehuda Lindell, and Tal Rabin. Information-theoretically secure protocols and security under composition. SIAM Journal on Computing, 39(5):2090-2112, 2010. Google Scholar
  25. Ralf Küsters, Max Tuengerthal, and Daniel Rausch. The IITM model: A simple and expressive model for universal composability. Journal of Cryptology, 33(4):1461-1584, 2020. Google Scholar
  26. Huijia Lin, Tianren Liu, and Hoeteck Wee. Information-theoretic 2-round MPC without round collapsing: Adaptive security, and more. In Proceedings of the 18th Theory of Cryptography Conference, TCC 2020, part II, pages 502-531, 2020. Google Scholar
  27. Yehuda Lindell and Hila Zarosim. Adaptive zero-knowledge proofs and adaptively secure oblivious transfer. Journal of Cryptology, 24(4):761-799, 2011. Google Scholar
  28. Silvio Micali and Phillip Rogaway. Secure computation (abstract). In Advances in Cryptology - CRYPTO 1991, pages 392-404, 1991. Google Scholar
  29. Jesper Buus Nielsen. Separating random oracle proofs from complexity theoretic proofs: The non-committing encryption case. In Advances in Cryptology - CRYPTO 2002, pages 111-126, 2002. Google Scholar
  30. Tal Rabin and Michael Ben-Or. Verifiable secret sharing and multiparty protocols with honest majority (extended abstract). In Proceedings of the 30th Annual Symposium on Foundations of Computer Science (FOCS), pages 73-85, 1989. Google Scholar
  31. Andrew Chi-Chih Yao. Protocols for secure computations (extended abstract). In Proceedings of the 23rd Annual Symposium on Foundations of Computer Science (FOCS), pages 160-164, 1982. 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