{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,7]],"date-time":"2025-07-07T21:40:06Z","timestamp":1751924406198,"version":"3.41.2"},"reference-count":20,"publisher":"International Association for Cryptologic Research","issue":"2","license":[{"start":{"date-parts":[[2025,4,3]],"date-time":"2025-04-03T00:00:00Z","timestamp":1743638400000},"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":[[2025,6,2]]},"abstract":" In ASIACRYPT 2011, Backes, Kate, and Patra (BKP) introduced two computationally secure round-optimal (2-round) Verifiable Secret Sharing (VSS) schemes in the honest-majority setting, one based on non-homomorphic commitments and the other on homomorphic ones. Their scheme based on non-homomorphic commitments has \n \n O<\/mml:mi>\n (<\/mml:mo>\n \n n<\/mml:mi>\n 2<\/mml:mn>\n <\/mml:msup>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math> computational complexity and necessitates \n \n O<\/mml:mi>\n (<\/mml:mo>\n \n n<\/mml:mi>\n 2<\/mml:mn>\n <\/mml:msup>\n \u03bb<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math> public and private communication for the dealer, where \n \n n<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math> denotes the number of parties and \n \n \u03bb<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math> is the security parameter. They showed that these costs are \n \n n<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math> times higher compared to their round-optimal VSS scheme employing homomorphic commitments and posed a research question regarding the inevitability of this gap. In this paper, we fill this gap by introducing a new variant of the recently proposed unified framework \n \n \n \u03a0<\/mml:mi>\n <\/mml:mrow>\n <\/mml:mrow>\n <\/mml:math> by Baghery at PKC 2025, designed to enable the construction of more efficient round-optimal VSS schemes in the honest-majority setting. Compared to the original framework, our variant reduces the required rounds by one while maintaining compatibility with any commitments and achieving comparable efficiency. Leveraging this new general construction, we develop several round-optimal VSS schemes that surpass state-of-the-art alternatives. Particularly noteworthy is the new round-optimal VSS scheme based on non-homomorphic commitments, which improves the BKP scheme by a factor of \n \n n<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math> across all efficiency metrics. Compared to their schemes based on homomorphic commitments, our schemes demonstrate significantly expedited verification and reconstruction. Implementation results further validate the practicality of these new VSS schemes. For example, for \n \n (<\/mml:mo>\n n<\/mml:mi>\n ,<\/mml:mo>\n t<\/mml:mi>\n )<\/mml:mo>\n =<\/mml:mo>\n (<\/mml:mo>\n 256<\/mml:mn>\n ,<\/mml:mo>\n 127<\/mml:mn>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math>, where \n \n t<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math> represents the threshold, compared to the hash-based BKP VSS scheme, our proposed scheme showcases speed-ups exceeding \n \n 120<\/mml:mn>\n ,<\/mml:mo>\n 000<\/mml:mn>\n \u00d7<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math> (and \n \n 50<\/mml:mn>\n \u00d7<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math>) for the dealer (and parties, respectively), while also requiring \n \n 365<\/mml:mn>\n \u00d7<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math> (and \n \n 512<\/mml:mn>\n \u00d7<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math>) less communication. <\/jats:p>","DOI":"10.62056\/a0zo-4tw9","type":"journal-article","created":{"date-parts":[[2025,7,7]],"date-time":"2025-07-07T21:09:09Z","timestamp":1751922549000},"update-policy":"https:\/\/doi.org\/10.62056\/adfjwm02dj","source":"Crossref","is-referenced-by-count":0,"title":["On Round-Optimal Computational VSS"],"prefix":"10.62056","volume":"2","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-7213-8496","authenticated-orcid":false,"given":"Karim","family":"Baghery","sequence":"first","affiliation":[{"id":[{"id":"https:\/\/ror.org\/05f950310","id-type":"ROR","asserted-by":"publisher"}],"name":"COSIC, KU Leuven","place":["Kasteelpark Arenberg 10, Leuven, 3001, Belgium"]}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9872-6157","authenticated-orcid":false,"given":"Navid","family":"Bardeh","sequence":"additional","affiliation":[{"id":[{"id":"https:\/\/ror.org\/05q9m0937","id-type":"ROR","asserted-by":"publisher"}],"name":"University of Klagenfurt","place":["Klagenfurt, Austria"]}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2493-8840","authenticated-orcid":false,"given":"Shahram","family":"Khazaei","sequence":"additional","affiliation":[{"id":[{"id":"https:\/\/ror.org\/024c2fq17","id-type":"ROR","asserted-by":"publisher"}],"name":"Sharif University of Technology","place":["Tehran, Iran"]}]},{"ORCID":"https:\/\/orcid.org\/0009-0003-0223-9082","authenticated-orcid":false,"given":"Mahdi","family":"Rahimi","sequence":"additional","affiliation":[{"id":[{"id":"https:\/\/ror.org\/05f950310","id-type":"ROR","asserted-by":"publisher"}],"name":"COSIC, KU Leuven","place":["Kasteelpark Arenberg 10, Leuven, 3001, Belgium"]}]}],"member":"48349","published-online":{"date-parts":[[2025,7,7]]},"reference":[{"key":"ref1: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":"ref2:FOCS:CGMA85","doi-asserted-by":"publisher","first-page":"383","DOI":"10.1109\/SFCS.1985.64","article-title":"Verifiable Secret Sharing and Achieving Simultaneity in the\n Presence of Faults (Extended Abstract)","author":"Benny Chor","year":"1985"},{"key":"ref3:FOCS:Feldman87","doi-asserted-by":"publisher","first-page":"427","DOI":"10.1109\/SFCS.1987.4","article-title":"A Practical Scheme for Non-interactive Verifiable Secret\n Sharing","author":"Paul Feldman","year":"1987"},{"key":"ref4:STOC:BenGolWig88","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/62212.62213","article-title":"Completeness Theorems for Non-Cryptographic Fault-Tolerant\n Distributed Computation (Extended Abstract)","author":"Michael Ben-Or","year":"1988"},{"key":"ref5:C:Pedersen91","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"129","DOI":"10.1007\/3-540-46766-1_9","article-title":"Non-Interactive and Information-Theoretic Secure Verifiable\n Secret Sharing","volume":"576","author":"Torben P. Pedersen","year":"1992"},{"key":"ref6:PODC:GenRabRab98","doi-asserted-by":"publisher","first-page":"101","DOI":"10.1145\/277697.277716","article-title":"Simplified VSS and Fast-Track Multiparty Computations with\n Applications to Threshold Cryptography","author":"Rosario Gennaro","year":"1998"},{"key":"ref7:AC:BacKatPat11","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"590","DOI":"10.1007\/978-3-642-25385-0_32","article-title":"Computational Verifiable Secret Sharing Revisited","volume":"7073","author":"Michael Backes","year":"2011"},{"key":"ref8:AC:ABCP23","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"405","DOI":"10.1007\/978-981-99-8721-4_13","article-title":"VSS from Distributed ZK Proofs and Applications","volume":"14438","author":"Shahla Atapoor","year":"2023"},{"key":"ref9:JoC:ShoSma24","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":"J. Cryptol."},{"key":"ref10:AC:CasCozGiu24","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"100","DOI":"10.1007\/978-981-96-0941-3_4","article-title":"Verifiable Secret Sharing from Symmetric Key Cryptography\n with Improved Optimistic Complexity","volume":"15490","author":"Ignacio Cascudo","year":"2024"},{"key":"ref11:PKC:Baghery25","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"110","DOI":"10.1007\/978-3-031-91829-2_4","article-title":"$\\Pi$: A Unified Framework for Computational Verifiable\n Secret Sharing","volume":"15677","author":"Karim Baghery","year":"2025"},{"key":"ref12:C:Schoenmakers99","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"148","DOI":"10.1007\/3-540-48405-1_10","article-title":"A Simple Publicly Verifiable Secret Sharing Scheme and Its\n Application to Electronic","volume":"1666","author":"Berry Schoenmakers","year":"1999"},{"key":"ref13:ACNS:CasDav17","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"537","DOI":"10.1007\/978-3-319-61204-1_27","article-title":"SCRAPE: Scalable Randomness Attested by Public Entities","volume":"10355","author":"Ignacio Cascudo","year":"2017"},{"key":"ref14:EPRINT:Groth21","volume-title":"Non-interactive distributed key generation and key\n resharing","author":"Jens Groth","year":"2021"},{"key":"ref15:EC:GenHalLyu22","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"458","DOI":"10.1007\/978-3-031-06944-4_16","article-title":"Practical Non-interactive Publicly Verifiable Secret Sharing\n with Thousands of Parties","volume":"13275","author":"Craig Gentry","year":"2022"},{"key":"ref16:ACNS:BKNR25","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"89","DOI":"10.1007\/978-3-031-95761-1_4","article-title":"Pre-constructed Publicly Verifiable Secret Sharing\n and\u00a0Applications","volume":"13906","author":"Karim Baghery","year":"2025"},{"key":"ref17:AC:CasDav20","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"311","DOI":"10.1007\/978-3-030-64840-4_11","article-title":"ALBATROSS: Publicly AttestabLe BATched Randomness\n Based On Secret Sharing","volume":"12493","author":"Ignacio Cascudo","year":"2020"},{"key":"ref18:STOC:GIKR01","doi-asserted-by":"publisher","first-page":"580","DOI":"10.1145\/380752.380853","article-title":"The round complexity of verifiable secret sharing and secure\n multicast","author":"Rosario Gennaro","year":"2001"},{"key":"ref19:C:BBCGI19","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1007\/978-3-030-26954-8_3","article-title":"Zero-Knowledge Proofs on Secret-Shared Data via Fully Linear\n PCPs","volume":"11694","author":"Dan Boneh","year":"2019"},{"key":"ref20: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"}],"container-title":["IACR Communications in Cryptology"],"original-title":[],"language":"en","deposited":{"date-parts":[[2025,7,7]],"date-time":"2025-07-07T21:09:36Z","timestamp":1751922576000},"score":1,"resource":{"primary":{"URL":"https:\/\/cic.iacr.org\/p\/2\/2\/13"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,7,7]]},"references-count":20,"journal-issue":{"issue":"2","published-online":{"date-parts":[[2025,7,7]]}},"URL":"https:\/\/doi.org\/10.62056\/a0zo-4tw9","archive":["Internet Archive","Internet Archive"],"relation":{},"ISSN":["3006-5496"],"issn-type":[{"value":"3006-5496","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,7,7]]},"assertion":[{"value":"2025-04-03","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-06-02","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}}],"article-number":"cc2-2-24"}}