Welcome to the resource topic for 2010/007
Title:
Efficient Asynchronous Verifiable Secret Sharing and Multiparty Computation
Authors: Arpita Patra, Ashish Choudhary, C. Pandu Rangan
Abstract:Secure Multi-Party Computation (MPC) providing information theoretic security allows a set of n parties to securely compute an agreed function F over a finite field {\mathbb F}, even if t parties are under the control of a computationally unbounded active adversary. Asynchronous MPC (AMPC) is an important variant of MPC, which works over an asynchronous network. It is well known that perfect AMPC is possible if and only if n \geq 4t+1, while statistical AMPC is possible if and only if n \geq 3t+1. In this paper, we study the communication complexity of AMPC protocols (both statistical and perfect) designed with exactly n = 4t+1 parties. Our major contributions in this paper are as follows: 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.
ePrint: https://eprint.iacr.org/2010/007
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .