@article {15100,
title = {Improving the round complexity of vss in point-to-point networks},
journal = {Automata, Languages and Programming},
year = {2008},
month = {2008///},
pages = {499 - 510},
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 {\textquotedblleft}for free{\textquotedblright} 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 {\textquotedblleft}2-level sharing{\textquotedblright} property that makes it useful for constructing protocols for general secure computation.
},
doi = {10.1007/978-3-540-70583-3_41},
author = {Katz, Jonathan and Koo,C. Y and Kumaresan,R.}
}