Welcome to the resource topic for 2010/609
Title:
The Round Complexity of General VSS
Authors: Ashish Choudhury, Kaoru Kurosawa, 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.
ePrint: https://eprint.iacr.org/2010/609
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 .