Paper 2012/517
Unconditionally Secure Asynchronous Multiparty Computation with Linear Communication Complexity
Ashish Choudhury, Martin Hirt, and Arpita Patra
Abstract
Unconditionally secure multiparty computation (MPC) allows a set of n mutually distrusting parties to securely compute an agreed function f over some finite field in the presence of a computationally unbounded adversary, who can actively corrupt any t out of the n parties. Designing an asynchronous MPC (AMPC) protocol with a communication complexity of O(n) field elements per multiplication gate is a long standing open problem. We solve the open problem by presenting two AMPC protocols with the corruption threshold t < n / 4. Our first protocol is statistically secure (i.e. involves a negligible error in the protocol outcome) in a completely asynchronous setting and improves the communication complexity of the previous best AMPC protocol in the same setting by a factor of \Theta(n). Our second protocol is perfectly secure (i.e. error free) in a hybrid setting, where one round of communication is assumed to be synchronous and improves the communication complexity of the previous best AMPC protocol in the hybrid setting by a factor of \Theta(n^2). Starting with the seminal work of Beaver (CRYPTO 1991), it is by now a wellknown technique to evaluate multiplication gates in an MPC protocol using shared random multiplication triples. The central contribution common to both the presented protocols is a new and simple framework for generating shared random multiplication triples. All the existing protocols approach the problem by first producing shared pairs of random values, followed by computing the shared product of each pair of random values by invoking known protocols for multiplication. Our framework takes a completely different approach and avoids using the multiplication protocols that are typically communication intensive. Namely, we ask the parties to verifiably share random multiplication triples and then securely extract shared random multiplication triples unknown to the adversary. The framework is of independent interest and can be adapted to any honest majority setting.
Metadata
 Available format(s)
 Category
 Cryptographic protocols
 Publication info
 Published elsewhere. MINOR revision.DISC 2013
 Contact author(s)

partho31 @ gmail com
hirt @ inf ethz ch
arpitapatra10 @ gmail com  History
 20130802: last of 2 revisions
 20120905: received
 See all versions
 Short URL
 https://ia.cr/2012/517
 License

CC BY
BibTeX
@misc{cryptoeprint:2012/517, author = {Ashish Choudhury and Martin Hirt and Arpita Patra}, title = {Unconditionally Secure Asynchronous Multiparty Computation with Linear Communication Complexity}, howpublished = {Cryptology ePrint Archive, Paper 2012/517}, year = {2012}, note = {\url{https://eprint.iacr.org/2012/517}}, url = {https://eprint.iacr.org/2012/517} }