Asynchronous Multi-Party Computation With Quadratic Communication

Martin Hirt, Jesper Buus Nielsen, and Bartosz Przydatek

Automata, Languages and Programming — ICALP 2008, Lecture Notes in Computer Science, Springer-Verlag, vol. 5126, pp. 473–485, Jul 2008.

We present an efficient protocol for secure multi-party computation in the asynchronous model with optimal resilience. For $n$ parties, up to $t < n / 3$ of them being corrupted, and security parameter $κ$ , a circuit with $c$ gates can be securely computed with communication complexity $O (c n^{2} κ)$ bits, which improves on the previously known solutions by a factor of $Ω (n)$ . The construction of the protocol follows the approach introduced by Franklin and Haber (Crypto'93), based on a public-key encryption scheme with threshold decryption. To achieve the quadratic complexity, we employ several techniques, including circuit randomization due to Beaver (Crypto'91), and an abstraction of certificates, which can be of independent interest.

BibTeX Citation

@inproceedings{HiNiPr08,
    author       = {Martin Hirt and Jesper Buus Nielsen and Bartosz Przydatek},
    title        = {Asynchronous Multi-Party Computation With Quadratic Communication},
    editor       = {Luca Aceto and Magnus M.~Halldorsson and Anna Ingolfsdottir},
    booktitle    = {Automata, Languages and Programming --- ICALP 2008},
    pages        = {473--485},
    series       = {Lecture Notes in Computer Science},
    volume       = {5126},
    year         = {2008},
    month        = {7},
    publisher    = {Springer-Verlag},
}