1. Asynchronous Verifiable Secret Sharing (AVSS) is one of the main building blocks for AMPC. In this paper, we design two AVSS protocols with 4t+1 parties: the first one is statistically secure and has non-optimal resilience, while the second one is perfectly secure and has optimal resilience. Both these schemes achieve a common interesting property, which was not achieved by the previous schemes. Specifically, our AVSS schemes allow to share a secret through a polynomial of degree at most d, where t \leq d \leq 2t. In contrast, the existing AVSS schemes can share a secret only through a polynomial of degree at most t. The new property of our AVSS simplifies the degree reduction step for the evaluation of multiplication gates in an AMPC protocol.
2.Using our statistical AVSS, we design a statistical AMPC protocol with n = 4t+1 which communicates O(n^2) field elements per multiplication gate. Though this protocol has non-optimal resilience, it significantly improves the communication complexity of the existing statistical AMPC protocols.
3. We then present a perfect AMPC protocol with n = 4t+1 (using our perfect AVSS scheme), which also communicates O(n^2) field elements per multiplication gate. This protocol improves on our statistical AMPC protocol as it has optimal resilience. To the best of our knowledge, this is the most communication efficient perfect AMPC protocol in the information theoretic setting.Category / Keywords: foundations / Publication Info: A preliminary version of this paper appeared in AFRICACRYPT 2010. Date: received 8 Jan 2010, last revised 11 Jul 2012 Contact author: arpitapatra_10 at yahoo co in Available format(s): PDF | BibTeX Citation Note: The results related to the statistical AVSS and AMPC in the current paper appeared earlier as Cryptology ePrint Archive: Report 2009/087. We have withdrawn that paper and instead the results are now merged with the results for the perfect AVSS and AMPC in this paper. Version: 20120711:100305 (All versions of this report) Short URL: ia.cr/2010/007 Discussion forum: Show discussion | Start new discussion