Information Security and Cryptography Research Group

The Round Complexity of Perfectly Secure General VSS

Ashish Choudhury, Kaoru Kurosawa, 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:

1. Two round perfectly secure VSS is possible if and only if the underlying adversary structure satisfies the ${\mathcal Q}^4$ condition;
2. Three round perfectly secure VSS is possible if and only if the underlying adversary structure satisfies the ${\mathcal 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 ${\mathcal O}(n^3)$ to ${\mathcal 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},
}

Files and Links

• PDF