CryptoDB
Verifiable Secret Sharing from Symmetric Key Cryptography with Improved Optimistic Complexity
| Authors: |
|
|---|---|
| Download: | |
| Presentation: | Slides |
| Conference: | ASIACRYPT 2024 |
| Abstract: | In this paper we propose verifiable secret sharing (VSS) schemes secure for any honest majority in the synchronous model, and that only use \textit{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 \textit{``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 \textit{polylogarithmic} and the total amount of broadcast information by the dealer is \textit{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. |
BibTeX
@inproceedings{asiacrypt-2024-34615,
title={Verifiable Secret Sharing from Symmetric Key Cryptography with Improved Optimistic Complexity},
publisher={Springer-Verlag},
author={Ignacio Cascudo and Daniele Cozzo and Emanuele Giunta},
year=2024
}