Paper 2010/609

The Round Complexity of General VSS

Ashish Choudhury, Kaoru Kurosawa, and Arpita Patra


The round complexity of verifiable secret sharing (VSS) schemes has been studied extensively for threshold adversaries. In particular, Fitzi et al. showed an efficient 3-round VSS for $n \geq 3t+1$ \cite{FitziVSSTCC06}, where an infinitely powerful adversary can corrupt t (or less) parties out of $n$ parties. This paper shows that for non-threshold adversaries, -Two round VSS is possible iff the underlying adversary structure satisfies ${\cal Q}^4$ condition; -Three round VSS is possible iff the underlying adversary structure satisfies ${\cal Q}^3$ condition. Further as a special case of our three round protocol, we can obtain a more efficient 3-round VSS than the VSS of Fitzi et al. for $n = 3t+1$. More precisely, the communication complexity of the reconstruction phase is reduced from ${\cal O}(n^3)$ to ${\cal O}(n^2)$. We finally point out a flaw in the reconstruction phase of VSS of Fitzi et al., and show how to fix it.

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. Unknown where it was published
Round ComplexityVSSNon-thresholdByzantineUnbounded Computing Power.
Contact author(s)
partho_31 @ yahoo co in
kurosawa @ mx ibaraki ac jp
arpitapatra10 @ gmail com
arpita @ cs au dk
2010-11-30: received
Short URL
Creative Commons Attribution


      author = {Ashish Choudhury and Kaoru Kurosawa and Arpita Patra},
      title = {The Round Complexity of  General VSS},
      howpublished = {Cryptology ePrint Archive, Paper 2010/609},
      year = {2010},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.