# 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 ${\cal Q}^4$ condition;

Three round perfectly secure VSS is possible if and only if the underlying adversary structure satisfies
the ${\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 the VSS of Fitzi et al.,
and show how to fix it.