# Information Security and Cryptography Research Group

## 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 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},
}