Multiparty Computation from Somewhat Homomorphic Encryption

Multiparty Computation from Somewhat Homomorphic Encryption

2012 | Ivan Damgård, Valerio Pastro, Nigel Smart, and Sarah Zakarias
The paper proposes a general multiparty computation (MPC) protocol that securely computes arithmetic circuits over any finite field \(\mathbb{F}_{p^k}\) against an active adversary corrupting up to \(n-1\) of the \(n\) players. The protocol consists of a preprocessing phase and an online phase. The preprocessing phase is independent of the function to be computed and the inputs, while the online phase is more efficient and unconditionally secure, with computational and communication complexity linear in \(n\). The protocol is optimal for large fields, with each player's work being only a small constant factor larger than computing the circuit in the clear. The preprocessing phase is based on a somewhat homomorphic cryptosystem, extending a scheme by Brakerski et al. to support distributed decryption and parallel processing of multiple values in a single ciphertext. The computational complexity of the preprocessing phase is dominated by public-key operations, requiring \(O(n^2/s)\) operations per secure multiplication, where \(s\) is a parameter that increases with the security parameter of the cryptosystem. The paper also presents a lower bound showing that the protocol is optimal up to a constant factor in terms of the amount of data required from the preprocessing phase and the number of bit operations. The protocol is implemented and tested for 3 players, achieving a secure 64-bit multiplication in 0.05 ms, which is significantly faster than previous efficient MPC protocols.The paper proposes a general multiparty computation (MPC) protocol that securely computes arithmetic circuits over any finite field \(\mathbb{F}_{p^k}\) against an active adversary corrupting up to \(n-1\) of the \(n\) players. The protocol consists of a preprocessing phase and an online phase. The preprocessing phase is independent of the function to be computed and the inputs, while the online phase is more efficient and unconditionally secure, with computational and communication complexity linear in \(n\). The protocol is optimal for large fields, with each player's work being only a small constant factor larger than computing the circuit in the clear. The preprocessing phase is based on a somewhat homomorphic cryptosystem, extending a scheme by Brakerski et al. to support distributed decryption and parallel processing of multiple values in a single ciphertext. The computational complexity of the preprocessing phase is dominated by public-key operations, requiring \(O(n^2/s)\) operations per secure multiplication, where \(s\) is a parameter that increases with the security parameter of the cryptosystem. The paper also presents a lower bound showing that the protocol is optimal up to a constant factor in terms of the amount of data required from the preprocessing phase and the number of bit operations. The protocol is implemented and tested for 3 players, achieving a secure 64-bit multiplication in 0.05 ms, which is significantly faster than previous efficient MPC protocols.
Reach us at info@study.space