The Round Complexity of Perfectly Secure General VSS

Ashish Choudhury, Kaoru Kurosawa, Arpita Patra

ICITS, Lecture Notes in Computer Science, Springer, vol. 6673, pp. 143-162, 2011.

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 3 t + 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 perfectly secure VSS is possible if and only if the underlying adversary structure satisfies the $Q^{4}$ condition;
Three round perfectly secure VSS is possible if and only if the underlying adversary structure satisfies the $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 = 3 t + 1$ . More precisely, the communication complexity of the reconstruction phase is reduced from $O (n^{3})$ to $O (n^{2})$ . We finally point out a flaw in the reconstruction phase of the VSS of Fitzi et al., and show how to fix it.

BibTeX Citation

@inproceedings{ChKuPa11b,
    author       = {Ashish Choudhury, Kaoru Kurosawa, Arpita Patra},
    title        = {The Round Complexity of Perfectly Secure General VSS},
    editor       = {Serge Fehr},
    booktitle    = {ICITS},
    pages        = {143-162},
    series       = {Lecture Notes in Computer Science},
    volume       = {6673},
    year         = {2011},
    publisher    = {Springer},
}