Communication efficient statistical asynchronous multiparty computation with optimal resilience

We propose an efficient statistically secure asynchronous multiparty computation (AMPC) protocol with optimal fault tolerance; i.e., with n=3t+1, where n is the total number of parties and t is the number of parties that can be under the influence of a Byzantine (active) adversary At having unbounded computing power. Our protocol privately communicates O(n 5κ) bits per multiplication gate and involves a negligible error probability of 2-Ω(κ), where κ is the error parameter. As far as our knowledge is concerned, the only known statistically secure AMPC protocol with n=3t+1 is due to [7], which privately communicates Ω(n11 κ 4) bits and A-casts Ω(n 11 κ 2 log(n)) bits per multiplication gate. Here A-cast is an asynchronous broadcast primitive, which allows a party to send some information to all other parties identically. Thus our AMPC protocol shows significant improvement in communication complexity over the AMPC protocol of [7]. © 2010 Springer-Verlag.