Multiparty Computation from Somewhat Homomorphic Encryption

We propose a general multiparty computation protocol secure against a dishonest majority, for computing securely arithmetic circuits over a finite field $\F_{p^k}$. As in several earlier works, 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. Our preprocessing is based on a somewhat homomorphic cryptosystem. We extend a scheme by Brakersky et al., allowing us to perform distributed decryption and to handle many values in parallel. Our preprocessing phase improves significantly over earlier work both asymptotically and in practice. The online phase may use an existing protocol by Bendlin et al., based on unconditionally secure MACs, but we also propose a new online phase that scales better with $n$, the number of players. The total amount of data the players need to store from the preprocessing is linear in $n$ rather than quadratic as in earlier work. Furthermore, the cost of a secure multiplication in our online phase is $O(n)$ multiplications in $\F_{p^k}$ plus $O(n^2)$ additions, rather than $O(n^2)$ multiplications as in earlier work.