Robust Multiparty Computation with Linear Communication Complexity

Martin Hirt and Jesper Buus Nielsen

Advances in Cryptology — CRYPTO 2006, Lecture Notes in Computer Science, Springer-Verlag, vol. 4117, pp. 463–482, Aug 2006.

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 κ + n B C)$ , where $S$ is the size of the circuit being securely evaluated, $κ$ is the security parameter and $B C$ is the communication complexity of one broadcast of a $κ$ -bit value. This means the average number of bits sent and received by a single party is $O (S κ + B C)$ , 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},
}