Abstract:

                             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 none 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 > 3t. Sufficiency, however, was only demonstrated by means of an inefficient (i.e., exponential-time) protocol and the construction of inefficient three-round protocol were 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 are a lower bound. Furthermore, we also demonstrate that one round is sufficient for WSS when n > 4t, and that VSS can be achieved in 1 + " amortized rounds (for any " > 0) when n > 3t.

Keywords: Decryption, Encryption, Verifiable Secret Sharing, Hybrid Secure Communication, RSA.