2012 | Ivan Damgård, Valerio Pastro, Nigel Smart, Sarah Zakarias
This paper presents a secure multiparty computation (MPC) protocol that can compute arithmetic circuits over any finite field $ F_{p^k} $, secure against an active adversary corrupting up to $ n-1 $ of the $ n $ players. The protocol consists of a preprocessing phase and an efficient online phase. The online phase is unconditionally secure and has linear computational and communication complexity in $ n $, the number of players, which is significantly better than previous quadratic complexity. The protocol is statistically UC-secure and optimal for large fields. It leverages a somewhat homomorphic encryption (SHE) scheme for preprocessing, enabling distributed decryption and parallel computation of multiple values in a single ciphertext. The preprocessing phase involves public-key operations with complexity $ O(n^2/s) $, where $ s $ is a security parameter. The protocol is efficient for large fields and can securely perform a 64-bit multiplication in 0.05 ms for 3 players. The online phase uses a secure representation of values with a global key for MAC authentication, allowing efficient multiplication using Beaver triples. The protocol also includes a zero-knowledge proof of plaintext knowledge to ensure correctness. The preprocessing phase is implemented using a distributed decryption procedure, and the protocol is secure against passive attacks. The overall protocol is efficient, with computational complexity $ O(n \cdot |C| + n^3) $, where $ |C| $ is the size of the circuit. The protocol is optimal for large fields and can be used for applications requiring integer arithmetic, modular reductions, and binary conversion. The paper also discusses the use of fully homomorphic encryption (FHE) for MPC, but notes that current FHE schemes are not practical due to their inefficiency. The proposed protocol is more efficient and practical, with a preprocessing phase that is constant-round and UC-secure against active and static corruption. The protocol is implemented for 3 players and achieves a secure 64-bit multiplication in 0.05 ms. The paper also discusses related work, including other MPC protocols and the use of FHE for secure computation. The protocol is based on an abstract SHE scheme and includes a concrete instantiation based on LWE. The protocol is secure against active adversaries and has optimal performance for large fields.This paper presents a secure multiparty computation (MPC) protocol that can compute arithmetic circuits over any finite field $ F_{p^k} $, secure against an active adversary corrupting up to $ n-1 $ of the $ n $ players. The protocol consists of a preprocessing phase and an efficient online phase. The online phase is unconditionally secure and has linear computational and communication complexity in $ n $, the number of players, which is significantly better than previous quadratic complexity. The protocol is statistically UC-secure and optimal for large fields. It leverages a somewhat homomorphic encryption (SHE) scheme for preprocessing, enabling distributed decryption and parallel computation of multiple values in a single ciphertext. The preprocessing phase involves public-key operations with complexity $ O(n^2/s) $, where $ s $ is a security parameter. The protocol is efficient for large fields and can securely perform a 64-bit multiplication in 0.05 ms for 3 players. The online phase uses a secure representation of values with a global key for MAC authentication, allowing efficient multiplication using Beaver triples. The protocol also includes a zero-knowledge proof of plaintext knowledge to ensure correctness. The preprocessing phase is implemented using a distributed decryption procedure, and the protocol is secure against passive attacks. The overall protocol is efficient, with computational complexity $ O(n \cdot |C| + n^3) $, where $ |C| $ is the size of the circuit. The protocol is optimal for large fields and can be used for applications requiring integer arithmetic, modular reductions, and binary conversion. The paper also discusses the use of fully homomorphic encryption (FHE) for MPC, but notes that current FHE schemes are not practical due to their inefficiency. The proposed protocol is more efficient and practical, with a preprocessing phase that is constant-round and UC-secure against active and static corruption. The protocol is implemented for 3 players and achieves a secure 64-bit multiplication in 0.05 ms. The paper also discusses related work, including other MPC protocols and the use of FHE for secure computation. The protocol is based on an abstract SHE scheme and includes a concrete instantiation based on LWE. The protocol is secure against active adversaries and has optimal performance for large fields.