In this setting it is typically assumed that parties are connected pairwise by authenticated, private channels, and that in addition they have access to a ``broadcast'' channel. Because broadcast {\em cannot} be simulated on a point-to-point network when a third or more of the parties are corrupt, it is impossible to construct VSS (and more generally, MPC) protocols in this setting without using a broadcast channel (or some equivalent addition to the model).
A great deal of research has focused on increasing the efficiency of VSS, primarily in terms of round complexity. In this work we consider a refinement of the round complexity of VSS, by adding a measure we term {\em broadcast complexity}. We view the broadcast channel as an expensive resource and seek to minimize the number of rounds in which it is invoked as well.
We construct a (linear) VSS protocol which uses the broadcast channel only {\em twice} in the sharing phase, while running in an overall constant number of rounds.
Category / Keywords: cryptographic protocols / broadcast, multiparty computation, pseudosignatures, verifiable secret sharing Original Publication (with minor differences): 7th International Conference on Information-Theoretic Security Date: received 8 Mar 2012, last revised 16 Sep 2013 Contact author: juan a garay at gmail com, cgivens at gmail com, rafail at cs ucla edu, pavel raykov at inf ethz ch Available format(s): PDF | BibTeX Citation Version: 20130916:183904 (All versions of this report) Short URL: ia.cr/2012/130