Constant-Round YOSO MPC Without Setup
Authors
Sebastian Kolby, Divya Ravi, Sophia Yakoubov
Sebastian Kolby
Aarhus University, Aarhus, Denmark
sk at cs dot au dot dk
sk at cs dot au dot dk
Divya Ravi
University of Amsterdam, Amsterdam, Netherlands
d dot ravi at uva dot nl
d dot ravi at uva dot nl
Sophia Yakoubov
Aarhus University, Aarhus, Denmark
sophia dot yakoubov at cs dot au dot dk
sophia dot yakoubov at cs dot au dot dk
Abstract
YOSO MPC (Gentry et al., Crypto 2021) is a new MPC framework where each participant can speak at most once. This models an adaptive adversary’s ability to watch the network and corrupt or destroy parties it deems significant based on their communication. By using private channels to anonymous receivers (e.g. by encrypting to a public key whose owner is unknown), the communication complexity of YOSO MPC can scale sublinearly with the total number N of available parties, even when the adversary’s corruption threshold is linear in N (e.g. just under N/2). It was previously an open problem whether YOSO MPC can achieve guaranteed output delivery in a constant number of rounds without relying on trusted setup. In this work, we show that this can indeed be accomplished. We demonstrate three different approaches: the first two (which we call YaOSO and YOSO-GLS) use two and three rounds of communication, respectively. Our third approach (which we call YOSO-LHSS) uses O(d) rounds, where d is the multiplicative depth of the circuit being evaluated; however, it can be used to bootstrap any constant-round YOSO protocol that requires setup, by generating that setup within YOSO-LHSS. Though YOSO-LHSS requires more rounds than our first two approaches, it may be more practical, since the zero knowledge proofs it employs are more efficient to instantiate. As a contribution of independent interest, we introduce a verifiable state propagation UC functionality, which allows parties to send private message which are verifiably derived in the “correct” way (according to the protocol in question) to anonymous receivers. This is a natural functionality to build YOSO protocols on top of.
References
[ACGJ18]
Prabhanjan Ananth, Arka Rai Choudhuri, Aarushi Goel, and Abhishek Jain. Round-Optimal Secure Multiparty Computation with Honest Majority. In Hovav Shacham and Alexandra Boldyreva, editors, Advances in Cryptology – CRYPTO 2018, Part II, volume 10992 of Lecture Notes in Computer Science, pages 395–424. August 2018. Springer, Cham. DOI: 10.1007/978-3-319-96881-0_14
[AHKP22a]
Anasuya Acharya, Carmit Hazay, Vladimir Kolesnikov, and Manoj Prabhakaran. SCALES - MPC with Small Clients and Larger Ephemeral Servers. In Eike Kiltz and Vinod Vaikuntanathan, editors, TCC 2022: 20th Theory of Cryptography Conference, Part II, volume 13748 of Lecture Notes in Computer Science, pages 502–531. November 2022. Springer, Cham. DOI: 10.1007/978-3-031-22365-5_18
[AHKP22b]
Anasuya Acharya, Carmit Hazay, Vladimir Kolesnikov, and Manoj Prabhakaran. SCALES - MPC with Small Clients and Larger Ephemeral Servers. November 7–10, 2022.
[AJL+12]
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 David Pointcheval and Thomas Johansson, editors, Advances in Cryptology – EUROCRYPT 2012, volume 7237 of Lecture Notes in Computer Science, pages 483–501. April 2012. Springer, Berlin, Heidelberg. DOI: 10.1007/978-3-642-29011-4_29
[BCP03]
Emmanuel Bresson, Dario Catalano, and David Pointcheval. A Simple Public-Key Cryptosystem with a Double Trapdoor Decryption Mechanism and Its Applications. In Chi-Sung Laih, editor, Advances in Cryptology – ASIACRYPT 2003, volume 2894 of Lecture Notes in Computer Science, pages 37–54. 2003. Springer, Berlin, Heidelberg. DOI: 10.1007/978-3-540-40061-5_3
[BDO23]
Lennart Braun, Ivan Damgård, and Claudio Orlandi. Secure Multiparty Computation from Threshold Encryption Based on Class Groups. August 20–24, 2023.
[BGG+20]
Fabrice Benhamouda, Craig Gentry, Sergey Gorbunov, Shai Halevi, Hugo Krawczyk, Chengyu Lin, Tal Rabin, and Leonid Reyzin. Can a Public Blockchain Keep a Secret?. In Rafael Pass and Krzysztof Pietrzak, editors, TCC 2020: 18th Theory of Cryptography Conference, Part I, volume 12550 of Lecture Notes in Computer Science, pages 260–290. November 2020. Springer, Cham. DOI: 10.1007/978-3-030-64375-1_10
[BHR12a]
Mihir Bellare, Viet Tung Hoang, and Phillip Rogaway. Adaptively Secure Garbling with Applications to One-Time Programs and Secure Outsourcing. In Xiaoyun Wang and Kazue Sako, editors, Advances in Cryptology – ASIACRYPT 2012, volume 7658 of Lecture Notes in Computer Science, pages 134–153. December 2012. Springer, Berlin, Heidelberg. DOI: 10.1007/978-3-642-34961-4_10
[BHR12b]
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: 19th Conference on Computer and Communications Security, pages 784–796. October 2012. ACM Press. DOI: 10.1145/2382196.2382279
[BL18]
Fabrice Benhamouda and Huijia Lin. k-Round Multiparty Computation from k-Round Oblivious Transfer via Garbled Interactive Circuits. In Jesper Buus Nielsen and Vincent Rijmen, editors, Advances in Cryptology – EUROCRYPT 2018, Part II, volume 10821 of Lecture Notes in Computer Science, pages 500–532. 2018. Springer, Cham. DOI: 10.1007/978-3-319-78375-8_17
[Can01]
Ran Canetti. Universally Composable Security: A New Paradigm for Cryptographic Protocols. In 42nd Annual Symposium on Foundations of Computer Science, pages 136–145. October 2001. IEEE Computer Society Press. DOI: 10.1109/SFCS.2001.959888
[CCD88]
David Chaum, Claude Crépeau, and Ivan Damgård. Multiparty Unconditionally Secure Protocols (Abstract) (Informal Contribution). In Carl Pomerance, editor, Advances in Cryptology – CRYPTO'87, volume 293 of Lecture Notes in Computer Science, pages 462. August 1988. Springer, Berlin, Heidelberg. DOI: 10.1007/3-540-48184-2_43
[CDK+22]
Matteo Campanelli, Bernardo David, Hamidreza Khoshakhlagh, Anders Konring, and Jesper Buus Nielsen. Encryption to the Future - A Paradigm for Sending Secret Messages to Future (Anonymous) Committees. In Shweta Agrawal and Dongdai Lin, editors, Advances in Cryptology – ASIACRYPT 2022, Part III, volume 13793 of Lecture Notes in Computer Science, pages 151–180, Taipei, Taiwan. December 5–9, 2022. Springer, Cham, Switzerland. DOI: 10.1007/978-3-031-22969-5_6
[CDN01]
Ronald Cramer, Ivan Damgård, and Jesper Buus Nielsen. Multiparty Computation from Threshold Homomorphic Encryption. In Birgit Pfitzmann, editor, Advances in Cryptology – EUROCRYPT 2001, volume 2045 of Lecture Notes in Computer Science, pages 280–299. May 2001. Springer, Berlin, Heidelberg. DOI: 10.1007/3-540-44987-6_18
[CGG+21]
Arka Rai Choudhuri, Aarushi Goel, Matthew Green, Abhishek Jain, and Gabriel Kaptchuk. Fluid MPC: Secure Multiparty Computation with Dynamic Participants. In Tal Malkin and Chris Peikert, editors, Advances in Cryptology – CRYPTO 2021, Part II, volume 12826 of Lecture Notes in Computer Science, pages 94–123, Virtual Event. August 2021. Springer, Cham. DOI: 10.1007/978-3-030-84245-1_4
[CGZ20]
Ran Cohen, Juan A. Garay, and Vassilis Zikas. Broadcast-Optimal Two-Round MPC. In Anne Canteaut and Yuval Ishai, editors, Advances in Cryptology – EUROCRYPT 2020, Part II, volume 12106 of Lecture Notes in Computer Science, pages 828–858. May 2020. Springer, Cham. DOI: 10.1007/978-3-030-45724-2_28
[CKR+23]
Ran Canetti, Sebastian Kolby, Divya Ravi, Eduardo Soria-Vazquez, and Sophia Yakoubov. Taming Adaptivity in YOSO Protocols: The Modular Way. In Guy N. Rothblum and Hoeteck Wee, editors, TCC 2023: 21st Theory of Cryptography Conference, Part II, volume 14370 of Lecture Notes in Computer Science, pages 33–62. 2023. Springer, Cham. DOI: 10.1007/978-3-031-48618-0_2
[CL15a]
Guilhem Castagnos and Fabien Laguillaumie. Linearly Homomorphic Encryption from DDH. Cryptology ePrint Archive, Report 2015/047. 2015.
[CL15b]
Guilhem Castagnos and Fabien Laguillaumie. Linearly Homomorphic Encryption from $\mathsf{DDH}$. In Kaisa Nyberg, editor, Topics in Cryptology – CT-RSA 2015, volume 9048 of Lecture Notes in Computer Science, pages 487–505. April 2015. Springer, Cham. DOI: 10.1007/978-3-319-16715-2_26
[DDG+23]
Bernardo David, Giovanni Deligios, Aarushi Goel, Yuval Ishai, Anders Konring, Eyal Kushilevitz, Chen-Da Liu-Zhang, and Varun Narayanan. Perfect MPC over Layered Graphs. In Helena Handschuh and Anna Lysyanskaya, editors, Advances in Cryptology – CRYPTO 2023, Part I, volume 14081 of Lecture Notes in Computer Science, pages 360–392. August 2023. Springer, Cham. DOI: 10.1007/978-3-031-38557-5_12
[DJ03]
Ivan Damgård and Mads Jurik. A Length-Flexible Threshold Cryptosystem with Applications. In Reihaneh Safavi-Naini and Jennifer Seberry, editors, ACISP 03: 8th Australasian Conference on Information Security and Privacy, volume 2727 of Lecture Notes in Computer Science, pages 350–364. July 2003. Springer, Berlin, Heidelberg. DOI: 10.1007/3-540-45067-X_30
[DMR+21]
Ivan Damgård, Bernardo Magri, Divya Ravi, Luisa Siniscalchi, and Sophia Yakoubov. Broadcast-Optimal Two Round MPC with an Honest Majority. In Tal Malkin and Chris Peikert, editors, Advances in Cryptology – CRYPTO 2021, Part II, volume 12826 of Lecture Notes in Computer Science, pages 155–184, Virtual Event. August 2021. Springer, Cham. DOI: 10.1007/978-3-030-84245-1_6
[EFR21]
Andreas Erwig, Sebastian Faust, and Siavash Riahi. Large-Scale Non-Interactive Threshold Cryptosystems Through Anonymity. Cryptology ePrint Archive, Report 2021/1290. 2021.
[GHK+21]
Craig Gentry, Shai Halevi, Hugo Krawczyk, Bernardo Magri, Jesper Buus Nielsen, Tal Rabin, and Sophia Yakoubov. YOSO: You Only Speak Once - Secure MPC with Stateless Ephemeral Roles. In Tal Malkin and Chris Peikert, editors, Advances in Cryptology – CRYPTO 2021, Part II, volume 12826 of Lecture Notes in Computer Science, pages 64–93, Virtual Event. August 2021. Springer, Cham. DOI: 10.1007/978-3-030-84245-1_3
[GHM+21]
Craig Gentry, Shai Halevi, Bernardo Magri, Jesper Buus Nielsen, and Sophia Yakoubov. Random-Index PIR and Applications. In Kobbi Nissim and Brent Waters, editors, TCC 2021: 19th Theory of Cryptography Conference, Part III, volume 13044 of Lecture Notes in Computer Science, pages 32–61. November 2021. Springer, Cham. DOI: 10.1007/978-3-030-90456-2_2
[GLS15]
S. Dov Gordon, Feng-Hao Liu, and Elaine Shi. Constant-Round MPC with Fairness and Guarantee of Output Delivery. In Rosario Gennaro and Matthew J. B. Robshaw, editors, Advances in Cryptology – CRYPTO 2015, Part II, volume 9216 of Lecture Notes in Computer Science, pages 63–82. August 2015. Springer, Berlin, Heidelberg. DOI: 10.1007/978-3-662-48000-7_4
[GMPS21]
Vipul Goyal, Elisaweta Masserova, Bryan Parno, and Yifan Song. Blockchains Enable Non-interactive MPC. In Kobbi Nissim and Brent Waters, editors, TCC 2021: 19th Theory of Cryptography Conference, Part II, volume 13043 of Lecture Notes in Computer Science, pages 162–193. November 2021. Springer, Cham. DOI: 10.1007/978-3-030-90453-1_6
[GMW87]
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 Annual ACM Symposium on Theory of Computing, pages 218–229. May 1987. ACM Press. DOI: 10.1145/28395.28420
[GO07]
Jens Groth and Rafail Ostrovsky. Cryptography in the Multi-string Model. In Alfred Menezes, editor, Advances in Cryptology – CRYPTO 2007, volume 4622 of Lecture Notes in Computer Science, pages 323–341. August 2007. Springer, Berlin, Heidelberg. DOI: 10.1007/978-3-540-74143-5_18
[GO14]
Jens Groth and Rafail Ostrovsky. Cryptography in the Multi-string Model. Journal of Cryptology, 27(3):506–543, July 2014. DOI: 10.1007/s00145-013-9152-y
[GS18]
Sanjam Garg and Akshayaram Srinivasan. Two-Round Multiparty Secure Computation from Minimal Assumptions. In Jesper Buus Nielsen and Vincent Rijmen, editors, Advances in Cryptology – EUROCRYPT 2018, Part II, volume 10821 of Lecture Notes in Computer Science, pages 468–499. 2018. Springer, Cham. DOI: 10.1007/978-3-319-78375-8_16
[GSW13]
Craig Gentry, Amit Sahai, and Brent Waters. Homomorphic Encryption from Learning with Errors: Conceptually-Simpler, Asymptotically-Faster, Attribute-Based. In Ran Canetti and Juan A. Garay, editors, Advances in Cryptology – CRYPTO 2013, Part I, volume 8042 of Lecture Notes in Computer Science, pages 75–92. August 2013. Springer, Berlin, Heidelberg. DOI: 10.1007/978-3-642-40041-4_5
[HLP11]
Shai Halevi, Yehuda Lindell, and Benny Pinkas. Secure Computation on the Web: Computing without Simultaneous Interaction. In Phillip Rogaway, editor, Advances in Cryptology – CRYPTO 2011, volume 6841 of Lecture Notes in Computer Science, pages 132–150. August 2011. Springer, Berlin, Heidelberg. DOI: 10.1007/978-3-642-22792-9_8
[LJA+18]
Andrei Lapets, Frederick Jansen, Kinan Dak Albab, Rawane Issa, Lucy Qin, Mayank Varia, and Azer Bestavros. Accessible Privacy-Preserving Web-Based Data Analysis for Assessing and Addressing Economic Inequalities. In Proceedings of the 1st ACM SIGCAS Conference on Computing and Sustainable Societies, New York, NY, USA. 2018. Association for Computing Machinery. DOI: 10.1145/3209811.3212701
[Pai99]
Pascal Paillier. Public-Key Cryptosystems Based on Composite Degree Residuosity Classes. In Jacques Stern, editor, Advances in Cryptology – EUROCRYPT'99, volume 1592 of Lecture Notes in Computer Science, pages 223–238. May 1999. Springer, Berlin, Heidelberg. DOI: 10.1007/3-540-48910-X_16
[Reg05]
Oded Regev. On lattices, learning with errors, random linear codes, and cryptography. In Harold N. Gabow and Ronald Fagin, editors, 37th Annual ACM Symposium on Theory of Computing, pages 84–93. May 2005. ACM Press. DOI: 10.1145/1060590.1060603
[Sha79]
Adi Shamir. How to Share a Secret. Communications of the Association for Computing Machinery, 22(11):612–613, November 1979. DOI: 10.1145/359168.359176
[sod19]
SODA: Scalable Oblivious Data Analytics. https://soda-project.eu/. 2019.
[VCAZ+18]
Meilof Veeningen, Supriyo Chatterjea, Horváth Anna Zsófia, Gerald Spindler, Eric Boersma, Peter van der Spek, Onno van der Galiën, Job Gutteling, Wessel Kraaij, and Thijs Veugen. Enabling Analytics on Sensitive Medical Data with Secure Multi-Party Computation. Stud Health Technol Inform, 2018.
[Yao82]
Andrew Chi-Chih Yao. Protocols for Secure Computations (Extended Abstract). In 23rd Annual Symposium on Foundations of Computer Science, pages 160–164. November 1982. IEEE Computer Society Press. DOI: 10.1109/SFCS.1982.38
[Yao86]
Andrew Chi-Chih Yao. How to Generate and Exchange Secrets (Extended Abstract). In 27th Annual Symposium on Foundations of Computer Science, pages 162–167. October 1986. IEEE Computer Society Press. DOI: 10.1109/SFCS.1986.25
PDF
History
Submitted: 2024-07-08
Accepted: 2024-09-02
Published: 2024-10-07
Accepted: 2024-09-02
Published: 2024-10-07
How to cite
Sebastian Kolby, Divya Ravi, and Sophia Yakoubov, Constant-Round YOSO MPC Without Setup. IACR Communications in Cryptology, vol. 1, no. 3, Oct 07, 2024, doi: 10.62056/ae5w4fe-3.
License
Copyright is held by the author(s)
This work is licensed under a Creative Commons Attribution (CC BY) license.