Paper 2008/172

The Round Complexity of Verifiable Secret Sharing Revisited

Arpita Patra, Ashish Choudhary, Tal Rabin, and C. Pandu Rangan


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}

Note: This paper is the combined version of our two papers titled "Probabilistic Verifiable Secret Sharing Tolerating Adaptive Adversary" and "Efficient Protocol for Generating IC Signature and its Application to Unconditional Verifiable Secret Sharing", which appeared earlier as ePrint Archive report no 2008/101 and 2008/172 respectively. The article 2008/172 was based on the improvement of the results of article 2008/101. However, there was a minor common bug in both the papers, which could be easily rectified. So instead of rectifying the bug separately in each paper, we corrected it and combined both the papers. We also changed the title of the combined paper as we found the new title to be more appropriate.

Available format(s)
Publication info
Published elsewhere. This is a full version of thepaper that is accepted in CRYPTO 2009
FoundationsVSSInformation Theoretic Security
Contact author(s)
arpitapatra_10 @ yahoo co in
talr @ us ibm com
2009-06-05: last of 3 revisions
2008-04-21: received
See all versions
Short URL
Creative Commons Attribution


      author = {Arpita Patra and Ashish Choudhary and Tal Rabin and C.  Pandu Rangan},
      title = {The Round Complexity of Verifiable Secret Sharing Revisited},
      howpublished = {Cryptology ePrint Archive, Paper 2008/172},
      year = {2008},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.