Paper 2024/838

Verifiable Secret Sharing from Symmetric Key Cryptography with Improved Optimistic Complexity

Ignacio Cascudo, IMDEA Software Institute
Daniele Cozzo, IMDEA Software Institute
Emanuele Giunta, IMDEA Software Institute, Universidad Politecnica de Madrid
Abstract

In this paper we propose verifiable secret sharing (VSS) schemes secure for any honest majority in the synchronous model, and that only use symmetric-key cryptographic tools, therefore having plausibly post-quantum security. Compared to the state-of-the-art scheme with these features (Atapoor et al., Asiacrypt `23), our main improvement lies on the complexity of the ``optimistic'' scenario where the dealer and all but a small number of receivers behave honestly in the sharing phase: in this case, the running time and download complexity (amount of information read) of each honest verifier is polylogarithmic and the total amount of broadcast information by the dealer is logarithmic; all these complexities were linear in the aforementioned work by Atapoor et al. At the same time, we preserve these complexities with respect to the previous work for the ``pessimistic'' case where the dealer or $O(n)$ receivers cheat actively. The new VSS protocol is of interest in multiparty computations where each party runs one VSS as a dealer, such as distributed key generation protocols. Our main technical handle is a distributed zero-knowledge proof of low degreeness of a polynomial, in the model of Boneh et al. (Crypto `19) where the statement (in this case the evaluations of the witness polynomial) is distributed among several verifiers, each knowing one evaluation. Using folding techniques similar to FRI (Ben-Sasson et al., ICALP `18) we construct such a proof where each verifier receives polylogarithmic information and runs in polylogarithmic time.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Preprint.
Keywords
Verifiable Secret SharingZero-knowledge ProofsRandom Oracle
Contact author(s)
ignacio cascudo @ imdea org
daniele cozzo @ imdea org
emanuele giunta @ imdea org
History
2024-05-31: approved
2024-05-28: received
See all versions
Short URL
https://ia.cr/2024/838
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2024/838,
      author = {Ignacio Cascudo and Daniele Cozzo and Emanuele Giunta},
      title = {Verifiable Secret Sharing from Symmetric Key Cryptography with Improved Optimistic Complexity},
      howpublished = {Cryptology {ePrint} Archive, Paper 2024/838},
      year = {2024},
      url = {https://eprint.iacr.org/2024/838}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.