Asynchronous Verifiable Secret-Sharing Protocols on a Good Day.

Arpita Patra, Ashish Choudhury, Chandrasekharan Pandu Rangan

Ashish Choudhury

Zheng Huang, Zheng Gong, Qiang Li

黄征, 龚征, Qiang Li

Arpita Patra, Ashish Choudhary, Chitra Rangan

Abstract. Verifiable Secret Sharing (VSS) is a fundamental primitive used in many distributed cryptographic tasks, such as Multiparty Computation (MPC) and Byzantine Agreement (BA). It is a two phase (sharing, reconstruction) protocol. The VSS and MPC protocols are carried out among n parties, where t out of n parties can be under the influence of a Byzantine (active) adversary, having unbounded computing power. It is well known that protocols for perfectly secure VSS and perfectly secure MPC exist in an asynchronous network iff n ≥ 4t+1. Hence, we call any perfectly secure VSS (MPC) protocol designed over an asynchronous network with n = 4t + 1 as optimally resilient VSS (MPC) protocol. A secret is d-shared among the parties if there exists a random degreed polynomial whose constant term is the secret and each honest party possesses a distinct point on the degree-d polynomial. Typically VSS is used as a primary tool to generate t-sharing of secret(s). In this paper, we present an optimally resilient, perfectly secure Asynchronous VSS (AVSS)

Michael Backes A, Amit Jyoti Datta, Aniket Kate

Verifiable secret sharing (VSS) is a vital primitive in secure distributed computing. It allows an untrusted dealer to verifiably share a secret among n parties in the presence of an adversary controlling at most t of them. VSS in the synchronous communication model has received tremendous attention in the cryptographic research community. Nevertheless, recent interest in deploying secure distributed computing over the Internet requires going beyond the synchronous communication model and thoroughly investigating VSS in the asynchronous communication model. In this work, we consider the communication complexity of asynchronous VSS in the computational setting for the optimal resilience of n = 3t + 1. The best known asynchronous VSS protocol by Cachin et al. has O(n 2) message complexity and O(κn 3) communication complexity, where κ is a security parameter corresponding to the size of the secret. We close the linear complexity gap between these two measures for asynchronous VSS by presenting two protocols with O(n 2) message complexity and O(κn 2) communication complexity. Our first protocol satisfies the standard VSS definition, and can be used in stand-alone VSS scenarios as well as in applications such as Byzantine agreement. Our second and more intricate protocol satisfies a stronger VSS definition, and is useful in all VSS applications including multiparty computation and threshold cryptography.