Optimally Resilient Asynchronous MPC with Linear Communication Complexity
Ashish Choudhury, Arpita Patra · 2015
We present a secure asynchronous multiparty computation (AMPC) protocol with optimal resilience, involving n = 3t + 1 parties and tolerating a computationally bounded static adversary, capable of corrupting upto t parties. For a security parameter k and for circuits of sufficiently large size, our protocol has an amortized communication complexity of O(cMnk) bits, where cM denotes the number of multiplication gates in the arithmetic circuit, representing the function to be computed. Prior to our work, the most efficient optimally resilient, computationally secure AMPC protocol was due to Hirt et al. (ICALP 2008). The protocol offers an amortized communication complexity of O(cMn2k) bits.