TY - JOUR
T1 - Improving the round complexity of VSS in point-to-point networks
JF - Information and Computation
Y1 - 2009
A1 - Katz, Jonathan
A1 - Koo,Chiu-Yuen
A1 - Kumaresan,Ranjit
AB - We revisit the following question: what is the optimal round complexity of verifiable secret sharing (VSS)? We focus here on the case of perfect VSS where the number of corrupted parties t satisfies t < n / 3 , with n the total number of parties. Work of Gennaro et al. (STOC 2001) and Fitzi et al. (TCC 2006) shows that, assuming a broadcast channel, three rounds are necessary and sufficient for efficient VSS. Existing protocols, however, treat the broadcast channel as being available “for free” and do not attempt to minimize its usage. This approach leads to relatively poor round complexity when such protocols are compiled to run over 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 satisfies a certain “2-level sharing” property that makes it useful for constructing protocols for general secure computation.
VL - 207
SN - 0890-5401
UR - http://www.sciencedirect.com/science/article/pii/S0890540109000935
CP - 8
M3 - 10.1016/j.ic.2009.03.007
ER -