On Round-Optimal Computational VSS

Karim Baghery; Navid Ghaedi Bardeh; Shahram Khazaei; Mahdi Rahimi

doi:10.62056/a0zo-4tw9

On Round-Optimal Computational VSS

Authors

Karim Baghery, Navid Ghaedi Bardeh, Shahram Khazaei, Mahdi Rahimi

Karim Baghery

COSIC, KU Leuven, Leuven, Belgium
karim dot baghery at kuleuven dot be

Navid Ghaedi Bardeh

University of Klagenfurt, Klagenfurt, Austria
navid dot ghaedibardeh at gmail dot com

Shahram Khazaei

Sharif University of Technology, Tehran, Iran
shahram dot khazaei at sharif dot ir

Mahdi Rahimi

COSIC, KU Leuven, Leuven, Belgium
mahdi dot rahimi at kuleuven dot be

Keywords: Verifiable Secret Sharing Round-Optimal Verifiable Secret Sharing Shamir Secret Sharing $Π$ framework

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 $O(n^2)$ computational complexity and necessitates $O(n^2\lambda)$ public and private communication for the dealer, where $n$ denotes the number of parties and $\lambda$ is the security parameter. They showed that these costs are $n$ 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 $\mathbf{\Pi}$ 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$ 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, t)=(256, 127)$, where $t$ represents the threshold, compared to the hash-based BKP VSS scheme, our proposed scheme showcases speed-ups exceeding $120,000\times$ (and $50\times$) for the dealer (and parties, respectively), while also requiring $365\times$ (and $512\times$) less communication.

References

[ABCP23]

Shahla Atapoor, Karim Baghery, Daniele Cozzo, and Robi Pedersen. VSS from Distributed ZK Proofs and Applications. In Jian Guo and Ron Steinfeld, editors, ASIACRYPT 2023, Part I, volume 14438 of LNCS, pages 405–440. December 2023. Springer, Singapore. DOI: 10.1007/978-981-99-8721-4_13

Google Scholar ePrint

[Bag25]

Karim Baghery. $\Pi$: A Unified Framework for Computational Verifiable Secret Sharing. In Tibor Jager and Jiaxin Pan, editors, PKC 2025, Part IV, volume 15677 of LNCS, pages 110–142. May 2025. Springer, Cham. DOI: 10.1007/978-3-031-91829-2_4

Google Scholar ePrint

[BBC⁺19]

Dan Boneh, Elette Boyle, Henry Corrigan-Gibbs, Niv Gilboa, and Yuval Ishai. Zero-Knowledge Proofs on Secret-Shared Data via Fully Linear PCPs. In Alexandra Boldyreva and Daniele Micciancio, editors, CRYPTO 2019, Part III, volume 11694 of LNCS, pages 67–97. August 2019. Springer, Cham. DOI: 10.1007/978-3-030-26954-8_3

Google Scholar ePrint

[BG18]

Jonathan Bootle and Jens Groth. Efficient Batch Zero-Knowledge Arguments for Low Degree Polynomials. In Michel Abdalla and Ricardo Dahab, editors, PKC 2018, Part II, volume 10770 of LNCS, pages 561–588. March 2018. Springer, Cham. DOI: 10.1007/978-3-319-76581-5_19

Google Scholar ePrint

[BGW88]

Michael Ben-Or, Shafi Goldwasser, and Avi Wigderson. Completeness Theorems for Non-Cryptographic Fault-Tolerant Distributed Computation (Extended Abstract). In 20th ACM STOC, pages 1–10. May 1988. ACM Press. DOI: 10.1145/62212.62213

Google Scholar ePrint

[BKNR25]

Karim Baghery, Noah Knapen, Georgio Nicolas, and Mahdi Rahimi. Pre-constructed Publicly Verifiable Secret Sharing and Applications. In Marc Fischlin and Veelasha Moonsamy, editors, Applied Cryptography and Network Security - 23st International Conference, ACNS 2025, Munich, Germany, June 23-27, 2025, Proceedings, volume 13906 of Lecture Notes in Computer Science, pages 89–119. 2025. Springer. DOI: 10.1007/978-3-031-95761-1_4

Google Scholar ePrint

[BKP11]

Michael Backes, Aniket Kate, and Arpita Patra. Computational Verifiable Secret Sharing Revisited. In Dong Hoon Lee and Xiaoyun Wang, editors, ASIACRYPT 2011, volume 7073 of LNCS, pages 590–609. December 2011. Springer, Berlin, Heidelberg. DOI: 10.1007/978-3-642-25385-0_32

Google Scholar ePrint

[CCG24]

Ignacio Cascudo, Daniele Cozzo, and Emanuele Giunta. Verifiable Secret Sharing from Symmetric Key Cryptography with Improved Optimistic Complexity. In Kai-Min Chung and Yu Sasaki, editors, ASIACRYPT 2024, Part VII, volume 15490 of LNCS, pages 100–128. December 2024. Springer, Singapore. DOI: 10.1007/978-981-96-0941-3_4

Google Scholar ePrint

[CD17]

Ignacio Cascudo and Bernardo David. SCRAPE: Scalable Randomness Attested by Public Entities. In Dieter Gollmann, Atsuko Miyaji, and Hiroaki Kikuchi, editors, ACNS 2017, volume 10355 of LNCS, pages 537–556. July 2017. Springer, Cham. DOI: 10.1007/978-3-319-61204-1_27

Google Scholar ePrint

[CD20]

Ignacio Cascudo and Bernardo David. ALBATROSS: Publicly AttestabLe BATched Randomness Based On Secret Sharing. In Shiho Moriai and Huaxiong Wang, editors, ASIACRYPT 2020, Part III, volume 12493 of LNCS, pages 311–341. December 2020. Springer, Cham. DOI: 10.1007/978-3-030-64840-4_11

Google Scholar ePrint

[CGMA85]

Benny Chor, Shafi Goldwasser, Silvio Micali, and Baruch Awerbuch. Verifiable Secret Sharing and Achieving Simultaneity in the Presence of Faults (Extended Abstract). In 26th FOCS, pages 383–395. October 1985. IEEE Computer Society Press. DOI: 10.1109/SFCS.1985.64

Google Scholar ePrint

[Fel87]

Paul Feldman. A Practical Scheme for Non-interactive Verifiable Secret Sharing. In 28th FOCS, pages 427–437. October 1987. IEEE Computer Society Press. DOI: 10.1109/SFCS.1987.4

Google Scholar ePrint

[GHL22]

Craig Gentry, Shai Halevi, and Vadim Lyubashevsky. Practical Non-interactive Publicly Verifiable Secret Sharing with Thousands of Parties. In Orr Dunkelman and Stefan Dziembowski, editors, EUROCRYPT 2022, Part I, volume 13275 of LNCS, pages 458–487. 2022. Springer, Cham. DOI: 10.1007/978-3-031-06944-4_16

Google Scholar ePrint

[GIKR01]

Rosario Gennaro, Yuval Ishai, Eyal Kushilevitz, and Tal Rabin. The round complexity of verifiable secret sharing and secure multicast. In 33rd ACM STOC, pages 580–589. July 2001. ACM Press. DOI: 10.1145/380752.380853

Google Scholar ePrint

[Gro21]

Jens Groth. Non-interactive distributed key generation and key resharing. Cryptology ePrint Archive, Report 2021/339. 2021.

Google Scholar ePrint

[GRR98]

Rosario Gennaro, Michael O. Rabin, and Tal Rabin. Simplified VSS and Fast-Track Multiparty Computations with Applications to Threshold Cryptography. In Brian A. Coan and Yehuda Afek, editors, 17th ACM PODC, pages 101–111. 1998. ACM. DOI: 10.1145/277697.277716

Google Scholar ePrint

[Ped92]

Torben P. Pedersen. Non-Interactive and Information-Theoretic Secure Verifiable Secret Sharing. In Joan Feigenbaum, editor, CRYPTO'91, volume 576 of LNCS, pages 129–140. August 1992. Springer, Berlin, Heidelberg. DOI: 10.1007/3-540-46766-1_9

Google Scholar ePrint

[Sch99]

Berry Schoenmakers. A Simple Publicly Verifiable Secret Sharing Scheme and Its Application to Electronic. In Michael J. Wiener, editor, CRYPTO'99, volume 1666 of LNCS, pages 148–164. August 1999. Springer, Berlin, Heidelberg. DOI: 10.1007/3-540-48405-1_10

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

[SS24]

Victor Shoup and Nigel P. Smart. Lightweight Asynchronous Verifiable Secret Sharing with Optimal Resilience. J. Cryptol., 37(3):27, 2024. DOI: 10.1007/S00145-024-09505-6

Google Scholar ePrint

PDF Open access

DOI: https://doi.org/10.62056/a0zo-4tw9

History

Submitted: 2025-04-03
Accepted: 2025-06-02
Published: 2025-07-07

How to cite

Karim Baghery, Navid Ghaedi Bardeh, Shahram Khazaei, and Mahdi Rahimi, On Round-Optimal Computational VSS. IACR Communications in Cryptology, vol. 2, no. 2, Jul 07, 2025, doi: 10.62056/a0zo-4tw9.

License

Copyright is held by the author(s)

This work is licensed under a Creative Commons Attribution (CC BY) license.

@article{10.62056/a0zo-4tw9,
         author={Karim Baghery and Navid Ghaedi Bardeh and Shahram Khazaei and Mahdi Rahimi},
         title={On Round-Optimal Computational {VSS}},
         volume={2},
         number={2},
         year={2025},
         date={2025-07-07},
         issn={3006-5496},
         doi={10.62056/a0zo-4tw9},
         journal={{IACR} Communications in Cryptology},
         publisher={International Association for Cryptologic Research}
}

TY  - JOUR
AU  - Karim Baghery
AU  - Navid Ghaedi Bardeh
AU  - Shahram Khazaei
AU  - Mahdi Rahimi
PY  - 2025
TI  - On Round-Optimal Computational VSS
JF  - IACR Communications in Cryptology
JA  - CIC
VL  - 2
IS  - 2
DO  - 10.62056/a0zo-4tw9
UR  - https://doi.org/10.62056/a0zo-4tw9
AB  - <p>        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 $O(n^2)$ computational complexity and necessitates $O(n^2\lambda)$ public and private communication for the dealer, where $n$ denotes the number of parties and $\lambda$ is the security parameter. They showed that these costs are $n$ 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 $\mathbf{\Pi}$ 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$ 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, t)=(256, 127)$, where $t$ represents the threshold, compared to the hash-based BKP VSS scheme, our proposed scheme showcases speed-ups exceeding $120,000\times$ (and $50\times$) for the dealer (and parties, respectively), while also requiring $365\times$ (and $512\times$) less communication.         </p>
ER  -

Karim Baghery, Navid Ghaedi Bardeh, Shahram Khazaei, and Mahdi Rahimi, On Round-Optimal Computational VSS. IACR Communications in Cryptology, vol. 2, no. 2, Jul 07, 2025, doi: 10.62056/a0zo-4tw9.