Paper 2012/619

Asynchronous Computational VSS with Reduced Communication Complexity

Michael Backes, Amit Datta, and Aniket Kate

Abstract

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.

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

BibTeX

@misc{cryptoeprint:2012/619,
      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{https://eprint.iacr.org/2012/619}},
      url = {https://eprint.iacr.org/2012/619}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.