-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 formats: Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation Version: 20101130:013653 (All versions of this report) Discussion forum: Show discussion | Start new discussion