Information Security and Cryptography Research Group

Perfectly-Secure MPC with Linear Communication Complexity

Zuzana Beerliova-Trubiniova and Martin Hirt

Theory of Cryptography Conference — TCC 2008, Lecture Notes in Computer Science, Springer-Verlag, vol. 4948, pp. 213–230, Mar 2008.

Secure multi-party computation (MPC) allows a set of $n$ players to securely compute an agreed function, even when up to $t$ players are under the control of an adversary. Known perfectly secure MPC protocols require communication of at least $\Omega(n^3)$ field elements per multiplication, whereas cryptographic or unconditional security is possible with communication linear in the number of players. We present a perfectly secure MPC protocol communicating $\O(n)$ field elements per multiplication. Our protocol provides perfect security against an active, adaptive adversary corrupting $t<n/3$ players, which is optimal. Thus our protocol improves the security of the most efficient information-theoretically secure protocol at no extra costs, respectively improves the efficiency of perfectly secure MPC protocols by a factor of $\Omega(n^2)$. To achieve this, we introduce a novel technique – constructing detectable protocols with the help of so-called hyper-invertible matrices, which we believe to be of independent interest. Hyper-invertible matrices allow (among other things) to perform efficient correctness checks of many instances in parallel, which was until now possible only if error-probability was allowed.

BibTeX Citation

@inproceedings{BeeHir08,
    author       = {Zuzana {Beerliova-Trubiniova} and Martin Hirt},
    title        = {Perfectly-Secure {MPC} with Linear Communication Complexity},
    editor       = {Ran Canetti},
    booktitle    = {Theory of Cryptography Conference --- TCC 2008},
    pages        = 213--230,
    series       = {Lecture Notes in Computer Science},
    volume       = 4948,
    year         = 2008,
    month        = 3,
    publisher    = {Springer-Verlag},
}

Files and Links