ETH Zürich » Computer Science » Theory » Cryptography

Publications: Abstract

Asynchronous Multi-Party Computation With Quadratic Communication

Martin Hirt and Jesper Buus Nielsen and Bartosz Przydatek

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 $\kappa$, a circuit with $c$ gates can be securely computed with communication complexity $\O(c n^2 \kappa)$ bits, which improves on the previously known solutions by a factor of $\Omega(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.