Publications: Abstract

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