CryptoDB
On Round Complexity of Unconditionally Secure VSS
| Authors: | |
|---|---|
| Download: | |
| 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. |
BibTeX
@misc{eprint-2008-17849,
title={On Round Complexity of Unconditionally Secure VSS},
booktitle={IACR Eprint archive},
keywords={Verifiable Secret Sharing, Error Probability, Information Theoretic Security},
url={http://eprint.iacr.org/2008/172},
note={ arpitapatra_10@yahoo.co.in 14081 received 15 Apr 2008, last revised 20 Jul 2008},
author={Arpita Patra and Ashish Choudhary and Ashwinkumar B.V and C. Pandu Rangan},
year=2008
}