Cryptology ePrint Archive: Report 2012/619

Asynchronous Computational VSS with Reduced Communication Complexity

Michael Backes and 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.

Category / Keywords: cryptographic protocols / Verifiable Secret Sharing, Asynchronous Communication Model, Communication Complexity, Threshold Cryptography, Polynomial Commitments

Publication Info: A shorter version of the paper is appearing at CT-RSA 2013

Date: received 1 Nov 2012, last revised 7 Nov 2012

Contact author: aniket at mmci uni-saarland de

Available format(s): PDF | BibTeX Citation

Version: 20121107:173119 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]