Cryptology ePrint Archive: Report 2007/358

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

Jonathan Katz and 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.

Category / Keywords: VSS, distributed computation

Publication Info: This is the full version of the paper appearing at ICALP 2008

Date: received 10 Sep 2007, last revised 18 Jun 2008

Contact author: jkatz at cs umd edu, cykoo at cs umd edu, ranjit at cs umd edu

Available format(s): PDF | BibTeX Citation

Note: Typos corrected.

Version: 20080618:112311 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]