Paper 2011/535
Multiparty Computation from Somewhat Homomorphic Encryption
I. Damgard, V. Pastro, N. P. Smart, and S. Zakarias
Abstract
We propose a general multiparty computation protocol secure against an active adversary corrupting up to $n1$ of the $n$ players. The protocol may be used to compute securely arithmetic circuits over any finite field $\F_{p^k}$. Our protocol consists of a preprocessing phase that is both independent of the function to be computed and of the inputs, and a much more efficient online phase where the actual computation takes place. The online phase is unconditionally secure and has total computational (and communication) complexity linear in $n$, the number of players, where earlier work was quadratic in $n$. Hence, the work done by each player in the online phase is independent of $n$ and moreover is only a small constant factor larger than what one would need to compute the circuit in the clear. It is the first protocol in the preprocessing model with these properties. We show a lower bound implying that for computation in large fields, our protocol is optimal. In practice, for 3 players, a secure 64bit multiplication can be done in 0.05 ms. Our preprocessing is based on a somewhat homomorphic cryptosystem. We extend a scheme by Brakerski et al., so that we can perform distributed decryption and handle many values in parallel in one ciphertext. The computational complexity of our preprocessing phase is dominated by the publickey operations, we need $O(n^2/s)$ operations per secure multiplication where $s$ is a parameter that increases with the security parameter of the cryptosystem. Earlier work in this model needed $\Omega(n^2)$ operations. In practice, the preprocessing prepares a secure 64bit multiplication for 3 players in about 13 ms, which is 23 order of magnitude faster than the best previous results.
Metadata
 Available format(s)
 Category
 Cryptographic protocols
 Publication info
 Published elsewhere. Unknown where it was published
 Contact author(s)

ivan @ cs au dk
vpastro @ cs au dk
zarah @ cs au dk
nigel @ cs bris ac uk  History
 20121106: last of 5 revisions
 20111001: received
 See all versions
 Short URL
 https://ia.cr/2011/535
 License

CC BY
BibTeX
@misc{cryptoeprint:2011/535, author = {I. Damgard and V. Pastro and N. P. Smart and S. Zakarias}, title = {Multiparty Computation from Somewhat Homomorphic Encryption}, howpublished = {Cryptology ePrint Archive, Paper 2011/535}, year = {2011}, note = {\url{https://eprint.iacr.org/2011/535}}, url = {https://eprint.iacr.org/2011/535} }