Paper 2001/023
Robustness for Free in Unconditional Multi-Party Computation
Martin Hirt and Ueli Maurer
Abstract
We present a very efficient multi-party computation protocol unconditionally secure against an active adversary. The security is maximal, i.e., active corruption of up to $t<n/3$ of the $n$ players is tolerated. The communication complexity for securely evaluating a circuit with $m$ multiplication gates over a finite field is $\O(mn^2)$ field elements, including the communication required for simulating broadcast. This corresponds to the complexity of the best known protocols for the passive model, where the corrupted players are guaranteed not to deviate from the protocol. Even in this model, it seems to be unavoidable that for every multiplication gate every player must send a value to every other player, and hence the complexity of our protocol may well be optimal. The constant overhead factor for robustness is small and the protocol is practical.
Metadata
- Available format(s)
-
PDF
PS
- Category
- Cryptographic protocols
- Publication info
- Published elsewhere. Unknown where it was published
- Keywords
- multi-party computationoptimal efficiencyunconditional security
- Contact author(s)
- hirt @ inf ethz ch
- History
- 2001-03-09: received
- Short URL
- https://ia.cr/2001/023
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2001/023,
author = {Martin Hirt and Ueli Maurer},
title = {Robustness for Free in Unconditional Multi-Party Computation},
howpublished = {Cryptology {ePrint} Archive, Paper 2001/023},
year = {2001},
url = {https://eprint.iacr.org/2001/023}
}
