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

Jonathan Katz; Chiu-Yuen Koo; Ranjit Kumaresan

Paper 2007/358

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.

Metadata

Available format(s): PDF
Publication info: Published elsewhere. This is the full version of the paper appearing at ICALP 2008
Keywords: VSS distributed computation
Contact author(s): jkatz @ cs umd edu
cykoo @ cs umd edu
ranjit @ cs umd edu
History: 2008-06-18: last of 2 revisions; 2007-09-13: received; See all versions
Short URL: https://ia.cr/2007/358
License: 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},
      url = {https://eprint.iacr.org/2007/358}
}