{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,9]],"date-time":"2025-12-09T08:29:49Z","timestamp":1765268989908,"version":"3.41.2"},"reference-count":44,"publisher":"International Association for Cryptologic Research","issue":"4","license":[{"start":{"date-parts":[[2024,7,9]],"date-time":"2024-07-09T00:00:00Z","timestamp":1720483200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/100000001","name":"U.S. National Science Foundation","doi-asserted-by":"publisher","award":["Grants No. 1801564, 1915763, 2209194, 2217770, and 2228610"],"award-info":[{"award-number":["Grants No. 1801564, 1915763, 2209194, 2217770, and 2228610"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000185","name":"Defense Advanced Research Projects Agency","doi-asserted-by":"publisher","award":["Agreement No. HR00112020021"],"award-info":[{"award-number":["Agreement No. HR00112020021"]}],"id":[{"id":"10.13039\/100000185","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["IACR CiC"],"accepted":{"date-parts":[[2024,12,3]]},"abstract":"<jats:p>Asynchronous complete secret sharing (ACSS) is a foundational primitive in the design of distributed algorithms and cryptosystems that require confidentiality. ACSS permits a dealer to distribute a secret to a collection of N servers so that everyone holds shares of a polynomial containing the dealer's secret.<\/jats:p>\n          <jats:p>This work contributes a new ACSS protocol, called Haven++, that uses packing and batching to make asymptotic and concrete advances in the design and application of ACSS for large secrets. Haven++ allows the dealer to pack multiple secrets in a single sharing phase, and to reconstruct either one or all of them later. For even larger secrets, we contribute a batching technique to amortize the cost of proof generation and verification across multiple invocations of our protocol.<\/jats:p>\n          <jats:p>The result is an asymptotic improvement in the worst-case amortized communication and computation complexity, both for ACSS itself and for its application to asynchronous distributed key generation. Our ADKG based on Haven++ achieves, for the first time, an optimal worst case amortized communication complexity of \u03baN without a trusted setup. To show the practicality of Haven++, we implement it and find that it outperforms the work of Yurek et al. (NDSS 2022) by more than an order of magnitude when there are malicious, faulty parties. <\/jats:p>","DOI":"10.62056\/a0qj5w7sf","type":"journal-article","created":{"date-parts":[[2025,1,13]],"date-time":"2025-01-13T17:00:52Z","timestamp":1736787652000},"update-policy":"https:\/\/doi.org\/10.62056\/adfjwm02dj","source":"Crossref","is-referenced-by-count":4,"title":["Haven++: Batched and Packed Dual-Threshold Asynchronous Complete Secret Sharing with Applications"],"prefix":"10.62056","volume":"1","author":[{"given":"Nicolas","family":"Alhaddad","sequence":"first","affiliation":[{"id":[{"id":"https:\/\/ror.org\/05qwgg493","id-type":"ROR","asserted-by":"publisher"}],"name":"Boston University","place":["United States"]}]},{"given":"Mayank","family":"Varia","sequence":"additional","affiliation":[{"id":[{"id":"https:\/\/ror.org\/05qwgg493","id-type":"ROR","asserted-by":"publisher"}],"name":"Boston University","place":["United States"]}]},{"given":"Ziling","family":"Yang","sequence":"additional","affiliation":[{"id":[{"id":"https:\/\/ror.org\/047426m28","id-type":"ROR","asserted-by":"publisher"}],"name":"University of Illinois Urbana-Champaign","place":["United States"]}]}],"member":"48349","published-online":{"date-parts":[[2025,1,13]]},"reference":[{"key":"ref1:CCS:CKLS02","doi-asserted-by":"publisher","first-page":"88","DOI":"10.1145\/586110.586124","article-title":"Asynchronous Verifiable Secret Sharing and Proactive\n  Cryptosystems","author":"Christian Cachin","year":"2002"},{"key":"ref2:bingo","isbn-type":"print","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1007\/978-3-031-38557-5","article-title":"Bingo: Adaptivity and Asynchrony in Verifiable Secret\n  Sharing and Distributed Key Generation","author":"Ittai Abraham","year":"2023","ISBN":"https:\/\/id.crossref.org\/isbn\/9783031385575"},{"key":"ref3:CCS:KokMalSpi20","doi-asserted-by":"publisher","first-page":"1751","DOI":"10.1145\/3372297.3423364","article-title":"Asynchronous Distributed Key Generation for\n  Computationally-Secure Randomness, Consensus, and Threshold Signatures","author":"Eleftherios Kokoris-Kogias","year":"2020"},{"key":"ref4:FC:AlhVarZha21","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"479","DOI":"10.1007\/978-3-662-64331-0_25","article-title":"High-Threshold AVSS with Optimal Communication\n  Complexity","volume":"12675","author":"Nicolas Alhaddad","year":"2021"},{"key":"ref5:RSA:BacDatKat13","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"259","DOI":"10.1007\/978-3-642-36095-4_17","article-title":"Asynchronous Computational VSS with Reduced Communication\n  Complexity","volume":"7779","author":"Michael Backes","year":"2013"},{"key":"ref6:AC:KatZavGol10","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1007\/978-3-642-17373-8_11","article-title":"Constant-Size Commitments to Polynomials and Their\n  Applications","volume":"6477","author":"Aniket Kate","year":"2010"},{"key":"ref7:CCS:DasXiaRen21","doi-asserted-by":"publisher","first-page":"2705","DOI":"10.1145\/3460120.3484808","article-title":"Asynchronous Data Dissemination and its Applications","author":"Sourav Das","year":"2021"},{"key":"ref8:ShoupAVSS","doi-asserted-by":"publisher","first-page":"27","DOI":"10.1007\/s00145-024-09505-6","article-title":"Lightweight Asynchronous Verifiable Secret Sharing with\n  Optimal Resilience","volume":"37","author":"Victor Shoup","year":"2024","journal-title":"Journal of Cryptology","ISSN":"https:\/\/id.crossref.org\/issn\/1432-1378","issn-type":"electronic"},{"key":"ref9:NDSS:YLFKM22:new","doi-asserted-by":"publisher","DOI":"10.14722\/ndss.2022.23120","article-title":"hbACSS: How to Robustly Share Many Secrets","author":"Thomas Yurek","year":"2022"},{"volume-title":"Distributed Key Generation in the Wild","year":"2012","author":"Aniket Kate","key":"ref10:EPRINT:KatHuaGol12"},{"volume-title":"Correlation-Resistant Storage via Keyword-Searchable\n  Encryption","year":"2005","author":"Lucas Ballard","key":"ref11:cryptoeprint:2005\/417"},{"key":"ref12:Abraham","doi-asserted-by":"publisher","first-page":"219","DOI":"10.1007\/s00446-022-00436-8","article-title":"Reaching consensus for asynchronous distributed key\n  generation","volume":"36","author":"Ittai Abraham","year":"2023","journal-title":"Distributed Computing","ISSN":"https:\/\/id.crossref.org\/issn\/1432-0452","issn-type":"electronic"},{"key":"ref13:GrothADKG","isbn-type":"print","doi-asserted-by":"publisher","first-page":"370","DOI":"10.1007\/978-3-031-58740-5_13","article-title":"Fast Batched Asynchronous Distributed Key Generation","author":"Jens Groth","year":"2024","ISBN":"https:\/\/id.crossref.org\/isbn\/9783031587405"},{"key":"ref14:USENIX:DXKR23","first-page":"5359","article-title":"Practical Asynchronous High-threshold Distributed Key\n  Generation and Distributed Polynomial Sampling","author":"Sourav Das","year":"2023"},{"key":"ref15:SRDS:CacTes05","doi-asserted-by":"publisher","first-page":"191","DOI":"10.1109\/RELDIS.2005.9","article-title":"Asynchronous verifiable information dispersal","author":"Christian Cachin","year":"2005"},{"key":"ref16:STOC:CanRab93","doi-asserted-by":"publisher","first-page":"42","DOI":"10.1145\/167088.167105","article-title":"Fast asynchronous Byzantine agreement with optimal\n  resilience","author":"Ran Canetti","year":"1993"},{"key":"ref17:STOC:BenCanGol93","doi-asserted-by":"publisher","first-page":"52","DOI":"10.1145\/167088.167109","article-title":"Asynchronous secure computation","author":"Michael Ben-Or","year":"1993"},{"volume-title":"Studies in secure multiparty computation and applications","year":"1996","author":"Ran Canetti","key":"ref18:canetti1996studies"},{"key":"ref19:cryptoeprint:2024\/432","isbn-type":"print","doi-asserted-by":"publisher","first-page":"280","DOI":"10.1007\/978-3-031-58740-5_10","article-title":"Perfect Asynchronous MPC with Linear Communication\n  Overhead","author":"Ittai Abraham","year":"2024","ISBN":"https:\/\/id.crossref.org\/isbn\/9783031587405"},{"key":"ref20:cryptoeprint:2024\/245","isbn-type":"print","doi-asserted-by":"publisher","first-page":"418","DOI":"10.1007\/978-3-031-68397-8_13","article-title":"Linear-Communication Asynchronous Complete Secret Sharing\n  with Optimal Resilience","author":"Xiaoyu Ji","year":"2024","ISBN":"https:\/\/id.crossref.org\/isbn\/9783031683978"},{"key":"ref21:SP:BBBPWM18","doi-asserted-by":"publisher","first-page":"315","DOI":"10.1109\/SP.2018.00020","article-title":"Bulletproofs: Short Proofs for Confidential Transactions and\n  More","author":"Benedikt B\u00fcnz","year":"2018"},{"key":"ref22:PKC:BooGro18","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"561","DOI":"10.1007\/978-3-319-76581-5_19","article-title":"Efficient Batch Zero-Knowledge Arguments for Low Degree\n  Polynomials","volume":"10770","author":"Jonathan Bootle","year":"2018"},{"key":"ref23:EC:BunFisSze20","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"677","DOI":"10.1007\/978-3-030-45721-1_24","article-title":"Transparent SNARKs from DARK Compilers","volume":"12105","author":"Benedikt B\u00fcnz","year":"2020"},{"key":"ref24:TCC:LibYun10","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"499","DOI":"10.1007\/978-3-642-11799-2_30","article-title":"Concise Mercurial Vector Commitments and Independent\n  Zero-Knowledge Sets with Short Proofs","volume":"5978","author":"Beno\u00eet Libert","year":"2010"},{"key":"ref25:PKC:CatFio13","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"55","DOI":"10.1007\/978-3-642-36362-7_5","article-title":"Vector Commitments and Their Applications","volume":"7778","author":"Dario Catalano","year":"2013"},{"key":"ref26:JC:CacKurSho05","doi-asserted-by":"publisher","first-page":"219","DOI":"10.1007\/s00145-005-0318-0","article-title":"Random Oracles in Constantinople: Practical Asynchronous\n  Byzantine Agreement Using Cryptography","volume":"18","author":"Christian Cachin","year":"2005","journal-title":"Journal of Cryptology"},{"key":"ref27:dfinity","article-title":"DFINITY Technology Overview Series, Consensus System","volume":"abs\/1805.04548","author":"Timo Hanke","year":"2018","journal-title":"CoRR"},{"key":"ref28:PKC:Boldyreva03","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1007\/3-540-36288-6_3","article-title":"Threshold Signatures, Multisignatures and Blind Signatures\n  Based on the Gap-Diffie-Hellman-Group Signature Scheme","volume":"2567","author":"Alexandra Boldyreva","year":"2003"},{"key":"ref29:JC:GJKR07","doi-asserted-by":"publisher","first-page":"51","DOI":"10.1007\/s00145-006-0347-3","article-title":"Secure Distributed Key Generation for Discrete-Log Based\n  Cryptosystems","volume":"20","author":"Rosario Gennaro","year":"2007","journal-title":"Journal of Cryptology"},{"key":"ref30:C:DamNie07","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"572","DOI":"10.1007\/978-3-540-74143-5_32","article-title":"Scalable and Unconditionally Secure Multiparty Computation","volume":"4622","author":"Ivan Damg\u00e5rd","year":"2007"},{"key":"ref31:macwilliams1977theory","volume-title":"The theory of error-correcting codes","volume":"16","author":"Florence Jessie MacWilliams","year":"1977"},{"key":"ref32:podcrbc","series-title":"PODC'22","isbn-type":"print","doi-asserted-by":"publisher","first-page":"399","DOI":"10.1145\/3519270.3538475","article-title":"Balanced Byzantine Reliable Broadcast with Near-Optimal\n  Communication and Improved Computation","author":"Nicolas Alhaddad","year":"2022","ISBN":"https:\/\/id.crossref.org\/isbn\/9781450392624"},{"key":"ref33:avidBrief","series-title":"PODC'22","isbn-type":"print","doi-asserted-by":"publisher","first-page":"418","DOI":"10.1145\/3519270.3538476","article-title":"Brief Announcement: Asynchronous Verifiable Information\n  Dispersal with Near-Optimal Communication","author":"Nicolas Alhaddad","year":"2022","ISBN":"https:\/\/id.crossref.org\/isbn\/9781450392624"},{"key":"ref34:DBLP:journals\/eccc\/ChiesaFS17","first-page":"57","article-title":"A Zero Knowledge Sumcheck and its Applications","volume":"24","author":"Alessandro Chiesa","year":"2017","journal-title":"Electron. Colloquium Comput. Complex."},{"key":"ref35:EC:BCCGP16","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"327","DOI":"10.1007\/978-3-662-49896-5_12","article-title":"Efficient Zero-Knowledge Arguments for Arithmetic Circuits\n  in the Discrete Log Setting","volume":"9666","author":"Jonathan Bootle","year":"2016"},{"key":"ref36:C:CKPS01","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"524","DOI":"10.1007\/3-540-44647-8_31","article-title":"Secure and Efficient Asynchronous Broadcast Protocols","volume":"2139","author":"Christian Cachin","year":"2001"},{"key":"ref37:PODC:AbrMalSpi19","doi-asserted-by":"publisher","first-page":"337","DOI":"10.1145\/3293611.3331612","article-title":"Asymptotically Optimal Validated Asynchronous Byzantine\n  Agreement","author":"Ittai Abraham","year":"2019"},{"key":"ref38:DBLP:journals\/iandc\/Bracha87","doi-asserted-by":"publisher","first-page":"130","DOI":"10.1016\/0890-5401(87)90054-X","article-title":"Asynchronous Byzantine Agreement Protocols","volume":"75","author":"Gabriel Bracha","year":"1987","journal-title":"Inf. Comput."},{"volume-title":"Succinct Erasure Coding Proof Systems","year":"2021","author":"Nicolas Alhaddad","key":"ref39:ecp"},{"key":"ref40:SP:TCZAPGD20","doi-asserted-by":"publisher","first-page":"877","DOI":"10.1109\/SP40000.2020.00059","article-title":"Towards Scalable Threshold Cryptosystems","author":"Alin Tomescu","year":"2020"},{"key":"ref41:10.1145\/167088.167105","series-title":"STOC '93","isbn-type":"print","doi-asserted-by":"publisher","first-page":"42","DOI":"10.1145\/167088.167105","article-title":"Fast asynchronous Byzantine agreement with optimal\n  resilience","author":"Ran Canetti","year":"1993","ISBN":"https:\/\/id.crossref.org\/isbn\/0897915917"},{"key":"ref42:beaver1991secure","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1007\/BF00196771","article-title":"Secure multiparty protocols and zero-knowledge proof systems\n  tolerating a faulty minority","volume":"4","author":"Donald Beaver","year":"1991","journal-title":"Journal of Cryptology"},{"key":"ref43:t2t","isbn-type":"print","doi-asserted-by":"publisher","first-page":"376","DOI":"10.1007\/978-3-540-76900-2_23","article-title":"Simple and Efficient Perfectly-Secure Asynchronous MPC","author":"Zuzana Beerliov\u00e1-Trub\u00edniov\u00e1","year":"2007","ISBN":"https:\/\/id.crossref.org\/isbn\/9783540769002"},{"key":"ref44:cryptoeprint:2023\/154","series-title":"CCS '23","isbn-type":"print","doi-asserted-by":"publisher","first-page":"815","DOI":"10.1145\/3576915.3616633","article-title":"FIN: Practical Signature-Free Asynchronous Common Subset in\n  Constant Time","author":"Sisi Duan","year":"2023","ISBN":"https:\/\/id.crossref.org\/isbn\/9798400700507"}],"container-title":["IACR Communications in Cryptology"],"original-title":[],"language":"en","deposited":{"date-parts":[[2025,1,13]],"date-time":"2025-01-13T17:10:52Z","timestamp":1736788252000},"score":1,"resource":{"primary":{"URL":"https:\/\/cic.iacr.org\/p\/1\/4\/3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,1,13]]},"references-count":44,"journal-issue":{"issue":"4","published-online":{"date-parts":[[2025,1,13]]}},"URL":"https:\/\/doi.org\/10.62056\/a0qj5w7sf","archive":["Internet Archive","Internet Archive"],"relation":{},"ISSN":["3006-5496"],"issn-type":[{"type":"electronic","value":"3006-5496"}],"subject":[],"published":{"date-parts":[[2025,1,13]]},"assertion":[{"value":"2024-07-09","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-12-03","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}}],"article-number":"cc1-3-84"}}