To design our protocol, we first present a novel, simple and optimally resilient statistical asynchronous verifiable secret sharing (AVSS) protocol with $n = 3t+1$, which significantly improves the communication complexity of the only known optimally resilient statistical AVSS protocol of [CR93]. Our AVSS shares multiple secrets concurrently and is far better than multiple parallel executions of AVSS sharing single secret. We believe that our AVSS can be used in many other applications for improving communication complexity and hence is of independent interest.
The common coin primitive is one of the most important building blocks for the construction of ABA protocol. The only known efficient common coin protocol [FM97] uses multiple executions of AVSS sharing a single secret as a black-box. Unfortunately, this common coin protocol does not achieve its goal when multiple invocations of AVSS sharing single secret are replaced by single invocation of AVSS sharing multiple secrets. Therefore in this paper, we extend the existing common coin protocol to make it compatible with our new AVSS. As a byproduct, our new common coin protocol is much more communication efficient than the existing common coin protocol.Category / Keywords: foundations / Date: received 1 Oct 2008, last revised 24 Dec 2010 Contact author: arpitapatra_10 at yahoo co in Available format(s): PDF | BibTeX Citation Version: 20101224:105656 (All versions of this report) Short URL: ia.cr/2008/424 Discussion forum: Show discussion | Start new discussion