Efficient Secure Multi-Party Computation

Martin Hirt, Ueli Maurer, and Bartosz Przydatek

Advances in Cryptology — ASIACRYPT 2000, Lecture Notes in Computer Science, Springer-Verlag, vol. 1976, pp. 143–161, Dec 2000.

Since the introduction of secure multi-party computation, all proposed protocols that provide security against cheating players suffer from very high communication complexities. The most efficient unconditionally secure protocols among $n$ players, tolerating cheating by up to $t < n / 3$ of them, require communicating $O (n^{6})$ field elements for each multiplication of two elements, even if only one player cheats.

In this paper, we propose a perfectly secure multi-party protocol which requires communicating $O (n^{3})$ field elements per multiplication. In this protocol, the number of invocations of the broadcast primitive is independent of the size of the circuit to be computed. The proposed techniques are generic and apply to other protocols for robust distributed computations.

Furthermore, we show that a sub-protocol proposed in \cite{GeRaRa98} for improving the efficiency of unconditionally secure multi-party computation is insecure.

BibTeX Citation

@inproceedings{HiMaPr00,
    author       = {Martin Hirt and Ueli Maurer and Bartosz Przydatek},
    title        = {Efficient Secure Multi-Party Computation},
    editor       = {Tatsuaki Okamoto},
    booktitle    = {Advances in Cryptology --- ASIACRYPT 2000},
    pages        = {143--161},
    series       = {Lecture Notes in Computer Science},
    volume       = {1976},
    year         = {2000},
    month        = {12},
    publisher    = {Springer-Verlag},
}