International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Ranjit Kumaresan

Affiliation: MIT

Publications

Year
Venue
Title
2017
ASIACRYPT
2016
CRYPTO
2015
EPRINT
2015
EPRINT
2015
CRYPTO
2015
ASIACRYPT
2014
CRYPTO
2014
CRYPTO
2014
EUROCRYPT
2014
TCC
2014
EPRINT
2013
TCC
2013
CRYPTO
2012
TCC
2010
ASIACRYPT
2007
EPRINT
Improving the Round Complexity of 'Round-Optimal' VSS
Jonathan Katz Chiu-Yuen Koo Ranjit Kumaresan
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.

Program Committees

Eurocrypt 2017