Paper 2012/130

Broadcast (and Round) Efficient Verifiable Secret Sharing

Juan Garay, Clint Givens, Rafail Ostrovsky, and Pavel Raykov


Verifiable secret sharing (VSS) is a fundamental cryptographic primitive, lying at the core of secure multi-party computation (MPC) and, as the distributed analogue of a commitment functionality, used in numerous applications. In this paper we focus on unconditionally secure VSS protocols with honest majority. 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.

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. MINOR revision.7th International Conference on Information-Theoretic Security
broadcastmultiparty computationpseudosignaturesverifiable secret sharing
Contact author(s)
juan a garay @ gmail com
cgivens @ gmail com
rafail @ cs ucla edu
pavel raykov @ inf ethz ch
2013-09-16: last of 2 revisions
2012-03-13: received
See all versions
Short URL
Creative Commons Attribution


      author = {Juan Garay and Clint Givens and Rafail Ostrovsky and Pavel Raykov},
      title = {Broadcast (and Round) Efficient Verifiable Secret Sharing},
      howpublished = {Cryptology ePrint Archive, Paper 2012/130},
      year = {2012},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.