Multiparty Computation from Somewhat Homomorphic Encryption
By Ivan Bjerre Damgård, Valerio Pastro, Nigel P. Smart, Sarah Zakarias. 2012
1,492 citations recorded by the source corpus.
We propose a general multiparty computation protocol secure against an active adversary corrupting up to $$n-1$$ of the n players. The protocol may be used to compute securely arithmetic circuits over any finite field $$\mathbb {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. Moreover, the work done by each player is only a small constant factor larger than what one would need to compute the circuit in the clear. We show this is optimal for computation in large fields. In practice, for 3 players, a secure 64-bit 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 public-key operations, we need $$On^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 $$\varOmega n^2$$ operations. In practice, the preprocessing prepares a secure 64-bit multiplication for 3 players in about 13 ms.
Subfields: Artificial Intelligence, Computational Theory and Mathematics, Information Systems, Privacy & Security
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Artificial Intelligence
- Marcel Keller
- David E. Evans
- Thomas Schneider
- Dan Boneh
- Yehuda Lindell
- Mike Rosulek
- Adrià Gascón
- Benny Pinkas
In Computational Theory and Mathematics
- Marcel Keller
- David E. Evans
- Yehuda Lindell
- Thomas Schneider
- Mike Rosulek
- Benny Pinkas
- Nigel P. Smart
- Ariel Nof
In Information Systems
- Marcel Keller
- Yehuda Lindell
- Ariel Nof
- David E. Evans
- Nigel P. Smart
- Thomas Schneider
- Dan Boneh
- Yuval Ishai
In Privacy & Security
- Yehuda Lindell
- David E. Evans
- Adrià Gascón
- Dan Boneh
- Marcel Keller
- Thomas Schneider
- Benny Pinkas
- Lingjuan Lyu
Citations in the corpus
- Turbo-Aggregate: Breaking the Quadratic Aggregation Barrier in Secure Federated Learning (2020, background): “size), and performing computations in the encrypted domain is computationally expensive [25], [26].”
- Honeycrisp: large-scale differentially private aggregation without a trusted core (2019, methodology): “It is the successor to the SPDZ framework [23], and is based on many of the same protocols.”
- A generic framework for privacy preserving deep learning (2018, methodology): “We show the ability of the framework to support various implementations of MPC and DP solutions and report the results obtained when instantiating the SPDZ[2] and moment accountant[1] methods respectively for MPC and DP in a federated learning context.”
- Privacy-Preserving Distributed Linear Regression on High-Dimensional Data (2017, background): “Generally, MPC techniques represent the implemented functionality either as arithmetic circuits (e.g., SPDZ [15], TinyOT [58]) or as Boolean circuits (e.g., Yao’s protocol [70], GMW [31]).”
- Prio: Private, Robust, and Scalable Computation of Aggregate Statistics (2017, methodology): “That said, there have been great advances in practical general-purpose MPC protocols of late [12,13,23,45,46,73,89,91,93,98].”
- VC3: Trustworthy Data Analytics in the Cloud Using SGX (2015, background): “The computation can also be shared between independent parties while guaranteeing confidentiality for individual inputs (using e. g., garbled circuits [29]) and providing protection against corrupted parties (see e. g., SPDZ [19]).”
- Chameleon: A Hybrid Secure Computation Framework for Machine Learning Applications (2018, background): “SPDZ [31] is a secure computation protocol based on additive secret sharing that is secure against n − 1 corrupted computation nodes in the malicious model.”
- A Survey on Homomorphic Encryption Schemes (2017, neutral): “Even though there exist a few FHE-based MPC protocols [Damgård et al. 2012; López-Alt et al. 2012; Choudhury et al. 2013; Damgård et al. 2016] proposing these powerful and useful tools, unfortunately, their performances are not yet comparable with the conventional MPC approaches [Mood et al. 2014;…”
- Blind Justice: Fairness with Encrypted Sensitive Attributes (2018, methodology): “Several generic protocols for MPC exists, such as the ones based on arithmetic sharing (Damg˚ard et al., 2012), garbled circuits (Yao, 1986), or GMW (Goldreich et al., 1987), with several available implementations (Demmler et al., 2015b; Zahur & Evans, 2015b).”
- Fast Cut-and-Choose-Based Protocols for Malicious and Covert Adversaries (2013, result): “Our protocol achieves covert security with deterrent = 1 − 2 − s +1 (i.e., the error is 2 − s +1 ) which is far more efficient than all previous work.”
- ABY - A Framework for Efficient Mixed-Protocol Secure Two-Party Computation (2015, methodology): “One promising direction is to investigate the malicious secure SPDZ protocol [27], [28], which uses Arithmetic circuits, and TinyOT [58], which uses Boolean circuits.”
- Optimized Honest-Majority MPC for Malicious Adversaries — Breaking the 1 Billion-Gate Per Second Barrier (2017, methodology): “This paradigm has been utilized in many protocols; see [20], [9], [16] for just a few examples.”
- A Pragmatic Introduction to Secure Multi-Party Computation (2019, methodology): “A di erent approach introduced by Damgård, Pastro, Smart, and Zakarias (SPDZ, often pronounced “speeds”) (Damgård et al., 2012b) results in constant-sized shares for each party.”
- Distributed Measurement with Private Set-Union Cardinality (2017, background): “General secure multiparty computation (MPC) protocols can realize any functionality including set-union cardinality, even in the UC model [1, 7], and recent advances in efficient MPC have been made in the multi-party, dishonest-majority setting that we require [10, 33, 34].”
- Secure Computation for Machine Learning With SPDZ (2019, methodology): “This project investigates the efficiency of the SPDZ framework [1], which provides an implementation of an MPC protocol with malicious security, in the context of popular machine learning (ML) algorithms.”
- Billion-Gate Secure Computation with Malicious Adversaries (2012, result): “Our results are in the standard model (i.e., no common reference strings or PKIs) and, in contrast to prior work, we do not use the random oracle model which has well-established theoretical shortcomings.”
- HybridAlpha: An Efficient Approach for Privacy-Preserving Federated Learning (2019, neutral): “tocol [12, 13].”
- Private Nearest Neighbors Classification in Federated Databases (2018, methodology): “This technique is generally used to hide the values of intermediate results, and it’s the basis of various MPC protocols (Beaver, 1991; Damgård et al., 2012; Mohassel & Zhang, 2017).”