@article {15110,
title = {Improving the round complexity of VSS in point-to-point networks},
journal = {Information and Computation},
volume = {207},
year = {2009},
month = {2009/08//},
pages = {889 - 899},
abstract = {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.\&$\#$xa0;(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 {\textquotedblleft}for free{\textquotedblright} 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 {\textquotedblleft}2-level sharing{\textquotedblright} property that makes it useful for constructing protocols for general secure computation.
},
isbn = {0890-5401},
doi = {10.1016/j.ic.2009.03.007},
url = {http://www.sciencedirect.com/science/article/pii/S0890540109000935},
author = {Katz, Jonathan and Koo,Chiu-Yuen and Kumaresan,Ranjit}
}