Paper 2026/2818
Round-Optimal Statistical Verifiable Secret Sharing with Polynomial Complexity
, Lucerne University of Applied Sciences and ArtsAbstract
Verifiable secret sharing (Chor, Goldwasser, Micali, and Awerbuch; FOCS'85) is a central primitive in secure computation, and its round complexity has been studied extensively. Rabin and Ben-Or [STOC'89] established the feasibility of statistical security up to $t<n/2$ corruptions, and Patra, Choudhary, Rabin, and Rangan [Crypto'09] showed that three sharing rounds are necessary. The work of Applebaum, Kachlon and Patra [STOC'23] introduced the first round-optimal VSS with three rounds of sharing and one round for reconstruction, albeit with exponential communication in the number of parties. We give the first round-optimal statistical VSS that has polynomial communication and computation for $t<n/2$. This resolves the efficiency question left open by Applebaum, Kachlon and Patra. The protocol is obtained from a new notion of weak secret sharing, in which the reconstruction-time freedom of a corrupt dealer is limited to choosing verification keys, which is of independent interest.
Metadata
- Available format(s)
-
PDF
- Category
- Cryptographic protocols
- Publication info
- Preprint.
- Keywords
- VSSMPCstatistical security
- Contact author(s)
-
chendaliu @ gmail com
elisawem @ andrew cmu edu - History
- 2026-11-10: approved
- 2026-11-07: received
- See all versions
- Short URL
- https://ia.cr/2026/2818
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2026/2818,
author = {Chen-Da Liu-Zhang and Elisaweta Masserova},
title = {Round-Optimal Statistical Verifiable Secret Sharing with Polynomial Complexity},
howpublished = {Cryptology {ePrint} Archive, Paper 2026/2818},
year = {2026},
url = {https://eprint.iacr.org/2026/2818}
}
