### Improving the Round Complexity of VSS in Point-to-Point Networks

Jonathan Katz, Chiu-Yuen Koo, and Ranjit Kumaresan

##### 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. This approach leads to relatively 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.

Note: Typos corrected.

Available format(s)
Publication info
Published elsewhere. This is the full version of the paper appearing at ICALP 2008
Keywords
VSSdistributed computation
Contact author(s)
jkatz @ cs umd edu
cykoo @ cs umd edu
ranjit @ cs umd edu
History
2008-06-18: last of 2 revisions
See all versions
Short URL
https://ia.cr/2007/358

CC BY

BibTeX

@misc{cryptoeprint:2007/358,
author = {Jonathan Katz and Chiu-Yuen Koo and Ranjit Kumaresan},
title = {Improving the Round Complexity of VSS in Point-to-Point Networks},
howpublished = {Cryptology ePrint Archive, Paper 2007/358},
year = {2007},
note = {\url{https://eprint.iacr.org/2007/358}},
url = {https://eprint.iacr.org/2007/358}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.