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 formats: PDF | BibTeX Citation Version: 20121107:173119 (All versions of this report) Discussion forum: Show discussion | Start new discussion