Information Security and Cryptography Research Group

Robustness for Free in Unconditional Multi-Party Computation

Martin Hirt and Ueli Maurer

Advances in Cryptology — CRYPTO 2001, Lecture Notes in Computer Science, Springer-Verlag, vol. 2139, pp. 101–118, Aug 2001.

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, but excluding some overhead costs (independent of $m$) for sharing the inputs and reconstructing the outputs. 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. The complexity of our protocol may well be optimal. The constant overhead factor for robustness is small and the protocol is practical.

BibTeX Citation

    author       = {Martin Hirt and Ueli Maurer},
    title        = {Robustness for Free in Unconditional Multi-Party Computation},
    editor       = {Joe Kilian},
    booktitle    = {Advances in Cryptology --- CRYPTO 2001},
    pages        = {101--118},
    series       = {Lecture Notes in Computer Science},
    volume       = {2139},
    year         = {2001},
    month        = {8},
    publisher    = {Springer-Verlag},

Files and Links