Cryptology ePrint Archive: Report 2010/609

The Round Complexity of General VSS

Ashish Choudhury and Kaoru Kurosawa and Arpita Patra

Abstract: 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.

Category / Keywords: cryptographic protocols / Round Complexity, VSS, Non-threshold, Byzantine, Unbounded Computing Power.

Date: received 29 Nov 2010

Contact author: partho_31 at yahoo co in, kurosawa@mx ibaraki ac jp, arpitapatra10@gmail com, arpita@cs au dk

Available format(s): Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation

Version: 20101130:013653 (All versions of this report)

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]