Robust Multiparty Computation with Linear Communication Complexity
Martin Hirt and Jesper Buus Nielsen
We present a robust multiparty computation protocol. The protocol is for the cryptographic model with open channels and a poly-time adversary, and allows $n$ parties to actively securely evaluate any poly-sized circuit with resilience $t < n/2$. The total communication complexity in bits over the point-to-point channels is $\O(S n \kappa + n \mathcal{BC})$, where $S$ is the size of the circuit being securely evaluated, $\kappa$ is the security parameter and $\mathcal{BC}$ is the communication complexity of one broadcast of a $\kappa$-bit value. This means the average number of bits sent and received by a single party is $\O(S \kappa + \mathcal{BC})$, which is almost independent of the number of participating parties. This is the first robust multiparty computation protocol with this property.
BibTeX Citation
@inproceedings{HirNie06,
author = {Martin Hirt and Jesper Buus Nielsen},
title = {Robust Multiparty Computation with Linear Communication Complexity},
editor = {Cynthia Dwork},
booktitle = {Advances in Cryptology --- CRYPTO 2006},
pages = {463--482},
series = {Lecture Notes in Computer Science},
volume = {4117},
year = {2006},
month = {8},
publisher = {Springer-Verlag},
}