## 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:

- Two round perfectly secure VSS is possible if and only if the underlying adversary structure satisfies the ${\mathcal Q}^4$ condition;
- 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}, }