CryptoDB
Improving the Round Complexity of 'Round-Optimal' VSS
| Authors: | |
|---|---|
| Download: | |
| Abstract: | We revisit the following question: what is the optimal round complexity of verifiable secret sharing~(VSS)? We focus here on the case of perfectly-secure VSS where the number of corrupted parties $t$ satisfies $t < n/3$, with $n$ being the total number of parties. Work of Gennaro et al. (STOC~2001) and Fitzi et al. (TCC~2006) shows that, assuming a broadcast channel, 3~rounds are necessary and sufficient for efficient VSS. The efficient 3-round protocol of Fitzi et al., however, treats the broadcast channel as being available ``for free'' and does not attempt to minimize its usage. As argued previously by the authors, this approach leads to poor round complexity when protocols are compiled for a point-to-point network. We show here a VSS protocol that is simultaneously optimal in terms of both the number of rounds and the number of invocations of broadcast. Our protocol also has a certain ``2-level sharing'' property that makes it useful for constructing protocols for general secure computation. |
BibTeX
@misc{eprint-2007-13638,
title={Improving the Round Complexity of 'Round-Optimal' VSS},
booktitle={IACR Eprint archive},
keywords={cryptographic protocols / VSS, secure multiparty computation},
url={http://eprint.iacr.org/2007/358},
note={ jkatz@cs.umd.edu 13766 received 10 Sep 2007},
author={Jonathan Katz and Chiu-Yuen Koo and Ranjit Kumaresan},
year=2007
}