{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,7]],"date-time":"2025-12-07T13:10:34Z","timestamp":1765113034996,"version":"3.41.2"},"reference-count":41,"publisher":"International Association for Cryptologic Research","license":[{"start":{"date-parts":[[2024,7,8]],"date-time":"2024-07-08T00:00:00Z","timestamp":1720396800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["IACR CiC"],"accepted":{"date-parts":[[2024,9,2]]},"abstract":"<jats: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\u2019s 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\u2019s 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 \u201ccorrect\u201d way (according to the protocol in question) to anonymous\u00a0receivers. This is a natural functionality to build YOSO protocols on top of. <\/jats:p>","DOI":"10.62056\/ae5w4fe-3","type":"journal-article","created":{"date-parts":[[2024,10,7]],"date-time":"2024-10-07T15:13:33Z","timestamp":1728314013000},"update-policy":"https:\/\/doi.org\/10.62056\/adfjwm02dj","source":"Crossref","is-referenced-by-count":2,"title":["Constant-Round YOSO MPC Without Setup"],"prefix":"10.62056","author":[{"ORCID":"https:\/\/orcid.org\/0009-0005-3228-7194","authenticated-orcid":false,"given":"Sebastian","family":"Kolby","sequence":"first","affiliation":[{"id":[{"id":"https:\/\/ror.org\/01aj84f44","id-type":"ROR","asserted-by":"publisher"}],"name":"Aarhus University","place":["\u00c5bogade 34, Aarhus, 8200, Denmark"]}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6423-8331","authenticated-orcid":false,"given":"Divya","family":"Ravi","sequence":"additional","affiliation":[{"id":[{"id":"https:\/\/ror.org\/04dkp9463","id-type":"ROR","asserted-by":"publisher"}],"name":"University of Amsterdam","place":["Science Park 900, Amsterdam, 1098 XH, Netherlands"]}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7958-8537","authenticated-orcid":false,"given":"Sophia","family":"Yakoubov","sequence":"additional","affiliation":[{"id":[{"id":"https:\/\/ror.org\/01aj84f44","id-type":"ROR","asserted-by":"publisher"}],"name":"Aarhus University","place":["\u00c5bogade 34, Aarhus, 8200, Denmark"]}]}],"member":"48349","published-online":{"date-parts":[[2024,10,7]]},"reference":[{"key":"ref1:C:ChaCreDam87","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"462","DOI":"10.1007\/3-540-48184-2_43","article-title":"Multiparty Unconditionally Secure Protocols (Abstract)\n  (Informal Contribution)","volume":"293","author":"David Chaum","year":"1988"},{"key":"ref2:STOC:GolMicWig87","doi-asserted-by":"publisher","first-page":"218","DOI":"10.1145\/28395.28420","article-title":"How to Play any Mental Game or A Completeness Theorem for\n  Protocols with Honest Majority","author":"Oded Goldreich","year":"1987"},{"key":"ref3:FOCS:Yao86","doi-asserted-by":"publisher","first-page":"162","DOI":"10.1109\/SFCS.1986.25","article-title":"How to Generate and Exchange Secrets (Extended Abstract)","author":"Andrew Chi-Chih Yao","year":"1986"},{"key":"ref4:medicalmpc","article-title":"Enabling Analytics on Sensitive Medical Data with Secure\n  Multi-Party Computation","author":"Meilof Veeningen","year":"2018","journal-title":"Stud Health Technol Inform"},{"volume-title":"SODA: Scalable Oblivious Data Analytics","year":"2019","key":"ref5:soda"},{"key":"ref6:wagegap","series-title":"COMPASS '18","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.1145\/3209811.3212701","article-title":"Accessible Privacy-Preserving Web-Based Data Analysis for\n  Assessing and Addressing Economic Inequalities","author":"Andrei Lapets","year":"2018","ISBN":"https:\/\/id.crossref.org\/isbn\/9781450358163"},{"key":"ref7:C:GHKMNRY21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"64","DOI":"10.1007\/978-3-030-84245-1_3","article-title":"YOSO: You Only Speak Once - Secure MPC with Stateless\n  Ephemeral Roles","volume":"12826","author":"Craig Gentry","year":"2021"},{"key":"ref8:TCC:BGGHKLRR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"260","DOI":"10.1007\/978-3-030-64375-1_10","article-title":"Can a Public Blockchain Keep a Secret?","volume":"12550","author":"Fabrice Benhamouda","year":"2020"},{"key":"ref9:TCC:GHMNY21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"32","DOI":"10.1007\/978-3-030-90456-2_2","article-title":"Random-Index PIR and Applications","volume":"13044","author":"Craig Gentry","year":"2021"},{"key":"ref10:CampanelliDKKN22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"151","DOI":"10.1007\/978-3-031-22969-5_6","article-title":"Encryption to the Future - A Paradigm for Sending Secret\n  Messages to Future (Anonymous) Committees","volume":"13793","author":"Matteo Campanelli","year":"2022"},{"key":"ref11:C:CGGJK21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"94","DOI":"10.1007\/978-3-030-84245-1_4","article-title":"Fluid MPC: Secure Multiparty Computation with Dynamic\n  Participants","volume":"12826","author":"Arka Rai Choudhuri","year":"2021"},{"key":"ref12:EC:CraDamNie01","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"280","DOI":"10.1007\/3-540-44987-6_18","article-title":"Multiparty Computation from Threshold Homomorphic\n  Encryption","volume":"2045","author":"Ronald Cramer","year":"2001"},{"key":"ref13:EPRINT:BDO","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"613","DOI":"10.1007\/978-3-031-38557-5_20","volume-title":"Advances in Cryptology \u2013 CRYPTO\u00a02023, Part\u00a0I","volume":"14081","author":"Lennart Braun","year":"2023"},{"volume-title":"Large-Scale Non-Interactive Threshold Cryptosystems Through\n  Anonymity","year":"2021","author":"Andreas Erwig","key":"ref14:cryptoeprint:2021\/1290"},{"key":"ref15:TCC:AHKP22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"502","DOI":"10.1007\/978-3-031-22365-5_18","article-title":"SCALES - MPC with Small Clients and Larger Ephemeral\n  Servers","volume":"13748","author":"Anasuya Acharya","year":"2022"},{"key":"ref16:cryptoeprint:2024\/383","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"502","DOI":"10.1007\/978-3-031-22365-5_18","volume-title":"TCC\u00a02022: 20th Theory of Cryptography Conference, Part\u00a0II","volume":"13748","author":"Anasuya Acharya","year":"2022"},{"key":"ref17:C:DDGIKKLN23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"360","DOI":"10.1007\/978-3-031-38557-5_12","article-title":"Perfect MPC over Layered Graphs","volume":"14081","author":"Bernardo David","year":"2023"},{"key":"ref18:TCC:CKRSY23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1007\/978-3-031-48618-0_2","article-title":"Taming Adaptivity in YOSO Protocols: The Modular Way","volume":"14370","author":"Ran Canetti","year":"2023"},{"key":"ref19:C:GorLiuShi15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"63","DOI":"10.1007\/978-3-662-48000-7_4","article-title":"Constant-Round MPC with Fairness and Guarantee of Output\n  Delivery","volume":"9216","author":"S. Dov Gordon","year":"2015"},{"key":"ref20:C:HalLinPin11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"132","DOI":"10.1007\/978-3-642-22792-9_8","article-title":"Secure Computation on the Web: Computing without\n  Simultaneous Interaction","volume":"6841","author":"Shai Halevi","year":"2011"},{"key":"ref21:EC:GarSri18a","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"468","DOI":"10.1007\/978-3-319-78375-8_16","article-title":"Two-Round Multiparty Secure Computation from Minimal\n  Assumptions","volume":"10821","author":"Sanjam Garg","year":"2018"},{"key":"ref22:EC:BenLin18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"500","DOI":"10.1007\/978-3-319-78375-8_17","article-title":"k-Round Multiparty Computation from k-Round Oblivious\n  Transfer via Garbled Interactive Circuits","volume":"10821","author":"Fabrice Benhamouda","year":"2018"},{"key":"ref23:C:ACGJ18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"395","DOI":"10.1007\/978-3-319-96881-0_14","article-title":"Round-Optimal Secure Multiparty Computation with Honest\n  Majority","volume":"10992","author":"Prabhanjan Ananth","year":"2018"},{"key":"ref24:EC:CohGarZik20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"828","DOI":"10.1007\/978-3-030-45724-2_28","article-title":"Broadcast-Optimal Two-Round MPC","volume":"12106","author":"Ran Cohen","year":"2020"},{"key":"ref25:C:DMRSY21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"155","DOI":"10.1007\/978-3-030-84245-1_6","article-title":"Broadcast-Optimal Two Round MPC with an Honest Majority","volume":"12826","author":"Ivan Damg\u00e5rd","year":"2021"},{"key":"ref26:TCC:GMPS21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"162","DOI":"10.1007\/978-3-030-90453-1_6","article-title":"Blockchains Enable Non-interactive MPC","volume":"13043","author":"Vipul Goyal","year":"2021"},{"key":"ref27:C:GenSahWat13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1007\/978-3-642-40041-4_5","article-title":"Homomorphic Encryption from Learning with Errors:\n  Conceptually-Simpler, Asymptotically-Faster, Attribute-Based","volume":"8042","author":"Craig Gentry","year":"2013"},{"key":"ref28:RSA:CasLag15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"487","DOI":"10.1007\/978-3-319-16715-2_26","article-title":"Linearly Homomorphic Encryption from $\\mathsf{DDH}$","volume":"9048","author":"Guilhem Castagnos","year":"2015"},{"key":"ref29:FOCS:Canetti01","doi-asserted-by":"publisher","first-page":"136","DOI":"10.1109\/SFCS.2001.959888","article-title":"Universally Composable Security: A New Paradigm for\n  Cryptographic Protocols","author":"Ran Canetti","year":"2001"},{"key":"ref30:EC:AJLTVW12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"483","DOI":"10.1007\/978-3-642-29011-4_29","article-title":"Multiparty Computation with Low Communication, Computation\n  and Interaction via Threshold FHE","volume":"7237","author":"Gilad Asharov","year":"2012"},{"key":"ref31:JC:GroOst14","doi-asserted-by":"publisher","first-page":"506","DOI":"10.1007\/s00145-013-9152-y","article-title":"Cryptography in the Multi-string Model","volume":"27","author":"Jens Groth","year":"2014","journal-title":"Journal of Cryptology"},{"key":"ref32:Shamir79","doi-asserted-by":"publisher","first-page":"612","DOI":"10.1145\/359168.359176","article-title":"How to Share a Secret","volume":"22","author":"Adi Shamir","year":"1979","journal-title":"Communications of the Association for Computing Machinery"},{"key":"ref33:EC:Paillier99","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"223","DOI":"10.1007\/3-540-48910-X_16","article-title":"Public-Key Cryptosystems Based on Composite Degree\n  Residuosity Classes","volume":"1592","author":"Pascal Paillier","year":"1999"},{"key":"ref34:ACISP:DamJur03","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"350","DOI":"10.1007\/3-540-45067-X_30","article-title":"A Length-Flexible Threshold Cryptosystem with Applications","volume":"2727","author":"Ivan Damg\u00e5rd","year":"2003"},{"key":"ref35:AC:BreCatPoi03","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1007\/978-3-540-40061-5_3","article-title":"A Simple Public-Key Cryptosystem with a Double Trapdoor\n  Decryption Mechanism and Its Applications","volume":"2894","author":"Emmanuel Bresson","year":"2003"},{"key":"ref36:FOCS:Yao82b","doi-asserted-by":"publisher","first-page":"160","DOI":"10.1109\/SFCS.1982.38","article-title":"Protocols for Secure Computations (Extended Abstract)","author":"Andrew Chi-Chih Yao","year":"1982"},{"key":"ref37:CCS:BelHoaRog12","doi-asserted-by":"publisher","first-page":"784","DOI":"10.1145\/2382196.2382279","article-title":"Foundations of garbled circuits","author":"Mihir Bellare","year":"2012"},{"key":"ref38:AC:BelHoaRog12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"134","DOI":"10.1007\/978-3-642-34961-4_10","article-title":"Adaptively Secure Garbling with Applications to One-Time\n  Programs and Secure Outsourcing","volume":"7658","author":"Mihir Bellare","year":"2012"},{"key":"ref39:STOC:Regev05","doi-asserted-by":"publisher","first-page":"84","DOI":"10.1145\/1060590.1060603","article-title":"On lattices, learning with errors, random linear codes, and\n  cryptography","author":"Oded Regev","year":"2005"},{"key":"ref40:C:GroOst07","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"323","DOI":"10.1007\/978-3-540-74143-5_18","article-title":"Cryptography in the Multi-string Model","volume":"4622","author":"Jens Groth","year":"2007"},{"volume-title":"Linearly Homomorphic Encryption from DDH","year":"2015","author":"Guilhem Castagnos","key":"ref41:EPRINT:CasLag15"}],"container-title":["IACR Communications in Cryptology"],"original-title":[],"language":"en","deposited":{"date-parts":[[2024,12,10]],"date-time":"2024-12-10T21:28:31Z","timestamp":1733866111000},"score":1,"resource":{"primary":{"URL":"https:\/\/cic.iacr.org\/p\/1\/3\/30"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,10,7]]},"references-count":41,"URL":"https:\/\/doi.org\/10.62056\/ae5w4fe-3","archive":["Internet Archive","Internet Archive"],"relation":{},"ISSN":["3006-5496"],"issn-type":[{"type":"electronic","value":"3006-5496"}],"subject":[],"published":{"date-parts":[[2024,10,7]]},"assertion":[{"value":"2024-07-08","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-09-02","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}}],"article-number":"cc1-3-87"}}