Welcome to the resource topic for 2008/172
Title:
The Round Complexity of Verifiable Secret Sharing Revisited
Authors: Arpita Patra, Ashish Choudhary, Tal Rabin, C. Pandu Rangan
Abstract:The round complexity of interactive protocols is one of their most important complexity measures. In this work we prove that existing lower bounds for the round complexity of VSS can be circumvented by introducing a negligible probability of error in the reconstruction phase. Previous results show matching lower and upper bounds of {\em three} rounds for VSS, with n = 3t+1, where the reconstruction of the secrets always succeeds, i.e. with probability 1. In contrast we show that with a negligible probability of error in the reconstruction phase: \begin{enumerate} \item There exists an efficient 2-round VSS protocol for n = 3t + 1. If we assume that the adversary is non-rushing then we can achieve a 1-round reconstruction phase. \item There exists an efficient 1-round VSS for t = 1 and n > 3. \item We prove that our results are optimal both in resilience and number of sharing rounds by showing: \begin{enumerate} \item There does not exist a 2-round WSS \footnote{WSS is a weaker notion of VSS.} (and hence VSS) for n \leq 3t. \item There does not exist a 1-round VSS protocol for t \geq 2 and n \geq 4. \end{enumerate} \end{enumerate}
ePrint: https://eprint.iacr.org/2008/172
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .