Round-Optimal and Efficient Verifiable Secret Sharing

We consider perfect verifiable secret sharing (VSS) in a synchronous network of

n

processors (players) where a designated player called the

dealer

wishes to distribute a secret

s

among the players in a way that no

t

of them obtain any information, but any

t

+ 1 players obtain full information about the secret. The round complexity of a VSS protocol is defined as the number of rounds performed in the sharing phase. Gennaro, Ishai, Kushilevitz and Rabin showed that three rounds are necessary and sufficient when

n

> 3

t

. Sufficiency, however, was only demonstrated by means of an inefficient (i.e., exponential-time) protocol, and the construction of an efficient three-round protocol was left as an open problem.

In this paper, we present an efficient three-round protocol for VSS. The solution is based on a three-round solution of so-called

weak verifiable secret sharing

(WSS), for which we also prove that three rounds is a lower bound. Furthermore, we also demonstrate that one round is sufficient for WSS when

n

> 4

t

, and that VSS can be achieved in 1 +

ε

amortized rounds (for any

ε

> 0 ) when

n

>3

t

.