Rafail Ostrovsky - Publications

Broadcast (and Round) Efficient Verifiable Secret Sharing

Juan A. Garay, Clint Givens, Rafail Ostrovsky, Pavel Raykov


Verifiable secret shearing (VSS) isa 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 tis setting it is typically assumed that parties are connected pairwise by authenticated, private channels , and that addition they have access to a “broadcast”channel. Because broadcast cannot be simulated on a pont-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 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.

The unabridged version of this paper appears in [GGOR13].

Clint Givens is supported on part by NSF grants 08 30803,09165174, 1065276,1118126 and 1136174, US-Israel BSF grant 2008411, OKAWA Foundation Research Award, IBM Faculty Research Award, Xerox Faculty Research Award B. John Garrick Foundation Award, Teradata Research award, and Lockheed-Martin Corporation Research Award. This material is based upon work supported by Defense Advanced Research Projects Agency through the U.S. Office of naval Research under Contract N00014-11-1-0392. The views expressed are those of the author and do not reflect the official policy or postion of the Department of Defense or the U.S.Government.

comment: ICITS 2013: 200-219

Fetch PDF file of the paper

Back to Publications List