International Association for Cryptologic Research

International Association
for Cryptologic Research


Paper: On Round Complexity of Unconditionally Secure VSS

Arpita Patra
Ashish Choudhary
Ashwinkumar B.V
C. Pandu Rangan
Search ePrint
Search Google
Abstract: In this work, we initiate the study of round complexity of {\it unconditionally secure weak secret sharing} (UWSS) and {\it unconditionally secure verifiable secret sharing} (UVSS) \footnote{In the literature, these problems are also called as statistical WSS and statistical VSS \cite{GennaroVSSSTOC01} respectively.} in the presence of an {\it all powerful} $t$-active adversary. Specifically, we show the following for UVSS: (a) 1-round UVSS is possible iff $t=1$ and $n>3$, (b) 2-round UVSS is possible if $n>3t$ and (c) 5-round {\it efficient} UVSS is possible if $n>2t$. For UWSS we show the following: (a) 1-round UWSS is possible iff $n>3t$ and (b) 3-round UWSS is possible if $n>2t$. Comparing our results with existing results for trade-off between fault tolerance and round complexity of perfect (zero error) VSS and WSS \cite{GennaroVSSSTOC01,FitziVSSTCC06,KatzVSSICALP2008}, we find that probabilistically relaxing the conditions of VSS/WSS helps to increase fault tolerance significantly.
  title={On Round Complexity of Unconditionally Secure VSS},
  booktitle={IACR Eprint archive},
  keywords={Verifiable Secret Sharing, Error Probability, Information Theoretic Security},
  note={ 14081 received 15 Apr 2008, last revised 20 Jul 2008},
  author={Arpita Patra and Ashish Choudhary and Ashwinkumar B.V and C. Pandu Rangan},