Constant-Round YOSO MPC Without Setup

Sebastian Kolby; Divya Ravi; Sophia Yakoubov

doi:10.62056/ae5w4fe-3

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

Divya Ravi

University of Amsterdam, Amsterdam, Netherlands
d dot ravi at uva dot nl

Sophia Yakoubov

Aarhus University, Aarhus, Denmark
sophia dot yakoubov at cs dot au dot dk

Keywords: YOSO MPC Constant-round Guaranteed output delivery

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

Google Scholar ePrint

[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

Google Scholar ePrint

[AHKP22b]

Anasuya Acharya, Carmit Hazay, Vladimir Kolesnikov, and Manoj Prabhakaran. SCALES - MPC with Small Clients and Larger Ephemeral Servers. November 7–10, 2022.

Google Scholar ePrint

[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

Google Scholar ePrint

[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

Google Scholar ePrint

[BDO23]

Lennart Braun, Ivan Damgård, and Claudio Orlandi. Secure Multiparty Computation from Threshold Encryption Based on Class Groups. August 20–24, 2023.

Google Scholar ePrint

[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

Google Scholar ePrint

[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

Google Scholar ePrint

[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

Google Scholar ePrint

[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

Google Scholar ePrint

[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

Google Scholar ePrint

[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

Google Scholar ePrint

[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

Google Scholar ePrint

[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

Google Scholar ePrint

[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

Google Scholar ePrint

[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

Google Scholar ePrint

[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

Google Scholar ePrint

[CL15a]

Guilhem Castagnos and Fabien Laguillaumie. Linearly Homomorphic Encryption from DDH. Cryptology ePrint Archive, Report 2015/047. 2015.

Google Scholar ePrint

[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

Google Scholar ePrint

[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

Google Scholar ePrint

[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

Google Scholar ePrint

[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

Google Scholar ePrint

[EFR21]

Andreas Erwig, Sebastian Faust, and Siavash Riahi. Large-Scale Non-Interactive Threshold Cryptosystems Through Anonymity. Cryptology ePrint Archive, Report 2021/1290. 2021.

Google Scholar ePrint

[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

Google Scholar ePrint

[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

Google Scholar ePrint

[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

Google Scholar ePrint

[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

Google Scholar ePrint

[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

Google Scholar ePrint

[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

Google Scholar ePrint

[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

Google Scholar ePrint

[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

Google Scholar ePrint

[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

Google Scholar ePrint

[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

Google Scholar ePrint

[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

Google Scholar ePrint

[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

Google Scholar ePrint

[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

Google Scholar ePrint

[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

Google Scholar ePrint

[sod19]

SODA: Scalable Oblivious Data Analytics. https://soda-project.eu/. 2019.

Google Scholar ePrint

[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.

Google Scholar ePrint

[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

Google Scholar ePrint

[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

Google Scholar ePrint

PDF Open access

DOI: https://doi.org/10.62056/ae5w4fe-3

History

Submitted: 2024-07-08
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.

@article{CiC-1-3-30,
    author = "Kolby, Sebastian and Ravi, Divya and Yakoubov, Sophia",
    journal = "{IACR} {C}ommunications in {C}ryptology",
    publisher = "{I}nternational {A}ssociation for {C}ryptologic {R}esearch",
    title = "Constant-Round {YOSO} {MPC} Without Setup",
    volume = "1",
    number = "3",
    date = "2024-10-07",
    year = "2024",
    issn = "3006-5496",
    doi = "10.62056/ae5w4fe-3"
}

TY - JOUR
AU - Kolby, Sebastian
AU - Ravi, Divya
AU - Yakoubov, Sophia
PY  - 2024
TI  - Constant-Round YOSO MPC Without Setup
JF  - IACR Communications in Cryptology
JA  - CIC
VL  - 1
IS  - 3
DO  - 10.62056/ae5w4fe-3
UR  - https://doi.org/10.62056/ae5w4fe-3
AB  - <p>    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. </p>
ER  -

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.