Paper 2012/619

Asynchronous Computational VSS with Reduced Communication Complexity

Michael Backes, Amit Datta, and 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 com- putational 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(kn^3) communication complexity, where k 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(kn^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.

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. A shorter version of the paper is appearing at CT-RSA 2013
Verifiable Secret SharingAsynchronous Communication ModelCommunication ComplexityThreshold CryptographyPolynomial Commitments
Contact author(s)
aniket @ mmci uni-saarland de
2012-11-07: revised
2012-11-05: received
See all versions
Short URL
Creative Commons Attribution


      author = {Michael Backes and Amit Datta and Aniket Kate},
      title = {Asynchronous Computational VSS with Reduced Communication Complexity},
      howpublished = {Cryptology ePrint Archive, Paper 2012/619},
      year = {2012},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.