Multiparty Computation from Somewhat Homomorphic Encryption
Open accessAbstract
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 $$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 $$\varOmega (n^2)$$ operations. In practice, the preprocessing prepares a secure 64-bit multiplication for 3 players in about 13 ms.
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
Byzantine-robust aggregation rules may ensure that the influence of Byzantine workers in any single round is limited, but attackers can couple attacks across rounds, moving weights significantly away from the desired direction and lowering model quality.
“[133], [70] showed that while the Byzantine-robust aggregation rules may ensure that the influence of the Byzantine workers in any single round is limited, the attackers can couple their attacks across the rounds, moving weights significantly away from the desired direction and thus achieve the goal of lowering the model quality.”
From Privacy and Robustness in Federated Learning: Attacks and Defenses (2024) · cites this paper as [133]
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Cites
Fully homomorphic encryption using ideal lattices
Gentry, C. (2009) · Proceedings of the forty-first annual ACM symposium on Theory of computing · doi:10.1145/1536414.1536440 · Cited by 6,806 · see citing works
On Ideal Lattices and Learning with Errors over Rings
Lyubashevsky, V., Peikert, C., & Regev, O. (2010) · Lecture notes in computer science · doi:10.1007/978-3-642-13190-5_1 · Cited by 1,908 · see citing works
(Leveled) fully homomorphic encryption without bootstrapping
Brakerski, Z., Gentry, C., & Vaikuntanathan, V. (2012) · Conference on Innovations in Theoretical Computer Science · doi:10.1145/2090236.2090262 · Cited by 1,825 · see citing works
Fully Homomorphic Encryption from Ring-LWE and Security for Key Dependent Messages
Brakerski, Z., & Vaikuntanathan, V. (2011) · Lecture notes in computer science · doi:10.1007/978-3-642-22792-9_29 · Cited by 1,114 · see citing works
Founding crytpography on oblivious transfer
Kilian, J. (1988) · doi:10.1145/62212.62215 · Cited by 1,035 · see citing works
Efficient Multiparty Protocols Using Circuit Randomization
Beaver, D. (2007) · Springer eBooks · doi:10.1007/3-540-46766-1_34 · Cited by 913 · see citing works
Advances in Cryptology – CRYPTO 2019
(2019) · Lecture notes in computer science · doi:10.1007/978-3-030-26951-7 · Cited by 753 · see citing works
Universally composable two-party and multi-party secure computation
Canetti, R., Lindell, Y., Ostrovsky, R., et al. (2002) · doi:10.1145/509907.509980 · Cited by 719 · see citing works
Better Key Sizes (and Attacks) for LWE-Based Encryption
Lindner, R., & Peikert, C. (2011) · Lecture notes in computer science · doi:10.1007/978-3-642-19074-2_21 · Cited by 703 · see citing works
Advances in Cryptology – CRYPTO 2018
(1992) · Lecture notes in computer science · doi:10.1007/3-540-46766-1 · Cited by 687 · see citing works
Fully homomorphic SIMD operations
Smart, N. P., & Vercauteren, F. (2012) · Designs Codes and Cryptography · doi:10.1007/s10623-012-9720-4 · Cited by 663 · see citing works
Self-citationBKZ 2.0: Better Lattice Security Estimates
Chen, Y., & Nguyễn, P. Q. (2011) · Lecture notes in computer science · doi:10.1007/978-3-642-25385-0_1 · Cited by 601 · see citing works
Fiat-Shamir with Aborts: Applications to Lattice and Factoring-Based Signatures
Lyubashevsky, V. (2009) · Lecture notes in computer science · doi:10.1007/978-3-642-10366-7_35 · Cited by 583 · see citing works
Fully Homomorphic Encryption with Polylog Overhead
Gentry, C., Halevi, S., & Smart, N. P. (2012) · Lecture notes in computer science · doi:10.1007/978-3-642-29011-4_28 · Cited by 501 · see citing works
Self-citationRegev, O. (2006) · Lecture notes in computer science · doi:10.1007/11818175_8 · Cited by 499 · see citing works
Multiparty Computation with Low Communication, Computation and Interaction via Threshold FHE
Asharov, G., Jain, A., López-Alt, A., Tromer, E., Vaikuntanathan, V., & Wichs, D. (2012) · Lecture notes in computer science · doi:10.1007/978-3-642-29011-4_29 · Cited by 466 · see citing works
Founding Cryptography on Oblivious Transfer – Efficiently
Ishai, Y., Prabhakaran, M., & Sahai, A. (2008) · Lecture notes in computer science · doi:10.1007/978-3-540-85174-5_32 · Cited by 457 · see citing works
Gama, N., & Nguyễn, P. Q. (2008) · Springer eBooks · doi:10.1007/978-3-540-78967-3_3 · Cited by 425 · see citing works
Zero-knowledge from secure multiparty computation
Ishai, Y., Eyal Kushilevitz, Z., Ostrovsky, R., & Sahai, A. (2007) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/1250790.1250794 · Cited by 425 · see citing works
A New Approach to Practical Active-Secure Two-Party Computation
Nielsen, J. B., Nordholt, P. S., Orlandi, C., & Burra, S. S. (2012) · Lecture notes in computer science · doi:10.1007/978-3-642-32009-5_40 · Cited by 388 · see citing works
Advances in Cryptology – CRYPTO 2010
Rabin, T., & 2010, C. (2010) · Lecture notes in computer science · doi:10.1007/978-3-642-14623-7 · Cited by 370 · see citing works
Beyond Uniformity: Better Security/Efficiency Tradeoffs for Compression Functions
Stam, M. (2008) · Lecture notes in computer science · doi:10.1007/978-3-540-85174-5_22 · Cited by 361 · see citing works
Semi-homomorphic Encryption and Multiparty Computation
Bendlin, R., Damgård, I., Orlandi, C., & Zakarias, S. (2011) · Lecture notes in computer science · doi:10.1007/978-3-642-20465-4_11 · Cited by 356 · see citing works
Self-citationFully Homomorphic Encryption without Bootstrapping.
Brakerski, Z., Gentry, C., & Vaikuntanathan, V. (2011) · Cited by 324 · see citing works
A Comprehensive Evaluation of Mutual Information Analysis Using a Fair Evaluation Framework
Whitnall, C., & Oswald, E. (2011) · Lecture notes in computer science · doi:10.1007/978-3-642-22792-9_18 · Cited by 283 · see citing works
Advances in Cryptology – EUROCRYPT 2011
(2011) · Lecture notes in computer science · doi:10.1007/978-3-642-20465-4 · Cited by 252 · see citing works
New Algorithms for Learning in Presence of Errors
Arora, S., & Ge, R. (2011) · Lecture notes in computer science · doi:10.1007/978-3-642-22006-7_34 · Cited by 246 · see citing works
Security of Symmetric Encryption in the Presence of Ciphertext Fragmentation
Boldyreva, A., Degabriele, J. P., Paterson, K. G., et al. (2012) · Lecture notes in computer science · doi:10.1007/978-3-642-29011-4_40 · Cited by 212 · see citing works
Damgård, I., & Nielsen, J. B. (2002) · Lecture notes in computer science · doi:10.1007/3-540-45708-9_37 · Cited by 135 · see citing works
Self-citationAlgebraic Signal Processing Theory: Cooley–Tukey Type Algorithms for Real DFTs
Voronenko, Y., & Püschel, M. (2008) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2008.2006152 · Cited by 126 · see citing works
Near-Linear Unconditionally-Secure Multiparty Computation with a Dishonest Minority
Ben‐Sasson, E., Fehr, S., & Ostrovsky, R. (2012) · Lecture notes in computer science · doi:10.1007/978-3-642-32009-5_39 · Cited by 109 · see citing works
Universally composable two-party and multi-party secure computation
Canetti, R., Lindell, Y., Ostrovsky, R., et al. (2002) · doi:10.1145/509978.509980 · Cited by 96 · see citing works
Highly-Efficient Universally-Composable Commitments Based on the DDH Assumption
Lindell, Y. (2011) · Lecture notes in computer science · doi:10.1007/978-3-642-20465-4_25 · Cited by 87 · see citing works
Multiparty Computation for Dishonest Majority: From Passive to Active Security at Low Cost
Damgård, I., & Orlandi, C. (2010) · Lecture notes in computer science · doi:10.1007/978-3-642-14623-7_30 · Cited by 71 · see citing works
Self-citationImplementing AES via an Actively/Covertly Secure Dishonest-Majority MPC Protocol
Damgård, I., Keller, M., Larraia, E., et al. (2012) · Lecture notes in computer science · doi:10.1007/978-3-642-32928-9_14 · Cited by 62 · see citing works
Self-citationThreshold Fully Homomorphic Encryption and Secure Computation.Preprint
Myers, S., Sergi, M., & Shelat, A. A. (2011) · IACR Cryptology ePrint Archive · Cited by 30 · see citing works
On the Efficiency of Classical and Quantum Oblivious Transfer Reductions
Winkler, S., & Wullschleger, J. (2010) · Lecture notes in computer science · doi:10.1007/978-3-642-14623-7_38 · Cited by 27 · see citing works
On the Amortized Complexity of Zero Knowledge Protocols for Multiplicative Relations
Cramer, R., Damgård, I., & Pastro, V. (2012) · Lecture notes in computer science · doi:10.1007/978-3-642-32284-6_4 · Cited by 21 · see citing works
Self-citation
Flagged first, then by citations
Cited by
Sorted by citations
Practical Secure Aggregation for Privacy-Preserving Machine Learning
Bonawitz, K., Ivanov, V., Kreuter, B., Marcedone, A., McMahan, H. B., Patel, S., Ramage, D., Segal, A., & Seth, K. (2017) · Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security · doi:10.1145/3133956.3133982 · Cited by 3,956 · see citing works
A Survey on Homomorphic Encryption Schemes: Theory and Implementation
Acar, A., Aksu, H., Uluagac, A. S., & Conti, M. (2019) · ACM Computing Surveys · doi:10.1145/3214303 · Cited by 1,397 · see citing works
Secure Multi-Party Computation: Theory, practice and applications
Zhao, C., Zhao, S., Zhao, M., Chen, Z., Gao, C.-Z., Li, H., & Tan, Y.-A. (2019) · Information Sciences · doi:10.1016/j.ins.2018.10.024 · Cited by 508 · see citing works
Privacy and Robustness in Federated Learning: Attacks and Defenses
Lyu, L., Yu, H., Ma, X., Chen, C., Sun, L., Zhao, J., Yang, Q., & Yu, P. S. (2024) · IEEE Transactions on Neural Networks and Learning Systems · doi:10.1109/tnnls.2022.3216981 · Cited by 548 · see citing works
End-to-end privacy preserving deep learning on multi-institutional medical imaging
Kaissis, G., Ziller, A., Passerat-Palmbach, J., Ryffel, T., Usynin, D., Trask, A., Lima, I., Mancuso, J., Jungmann, F., Steinborn, M.-M., et al. (2021) · Nature Machine Intelligence · doi:10.1038/s42256-021-00337-8 · Cited by 513 · see citing works
Turbo-Aggregate: Breaking the Quadratic Aggregation Barrier in Secure Federated Learning
So, J., Guler, B., & Avestimehr, A. S. (2021) · IEEE Journal on Selected Areas in Information Theory · doi:10.1109/jsait.2021.3054610 · Cited by 318 · see citing works
Towards Fair and Privacy-Preserving Federated Deep Models
Lyu, L., Yu, J., Nandakumar, K., Li, Y., Ma, X., Jin, J., Yu, H., & Ng, K. S. (2020) · IEEE Transactions on Parallel and Distributed Systems · doi:10.1109/tpds.2020.2996273 · Cited by 250 · see citing works
Privacy-preserving distributed linear regression on high-dimensional data
Gascón, A., Schoppmann, P., Balle, B., Raykova, M., Doerner, J., Zahur, S., & Evans, D. (2017) · Proceedings on Privacy Enhancing Technologies · doi:10.1515/popets-2017-0053 · Cited by 193 · see citing works
Deriving genomic diagnoses without revealing patient genomes
Jagadeesh, K. A., Wu, D. J., Birgmeier, J. A., Boneh, D., & Bejerano, G. (2017) · Science · doi:10.1126/science.aam9710 · Cited by 134 · see citing works
Secure Partial Aggregation: Making Federated Learning More Robust for Industry 4.0 Applications
Gao, J., Zhang, B., Guo, X., Baker, T., Li, M., & Liu, Z. (2022) · IEEE Transactions on Industrial Informatics · doi:10.1109/tii.2022.3145837 · Cited by 41 · see citing works
A federated learning architecture for secure and private neuroimaging analysis
Stripelis, D., Gupta, U., Saleem, H., Dhinagar, N., Ghai, T., Anastasiou, C., Sánchez, R., Steeg, G. V., Ravi, S., Naveed, M., et al. (2024) · Patterns · doi:10.1016/j.patter.2024.101031 · Cited by 31 · see citing works
- Authors
- Damgård, I., Pastro, V., Smart, N., & Zakarias, S.
- Affiliations
- Aarhus University (DK)
- University of Bristol (GB)
- Venue
- Lecture Notes in Computer Science
- Publisher
- Springer Berlin Heidelberg
- Published
- 2012
- Pages
- 643-662
- ISSN
- 0302-9743 (ISSN-L)
- 1611-3349
- OpenAlex
- W2402235285
- Cited by
- 1,331
- References
- 38
- Citations by year
- 2026: 71 · 2025: 121 · 2024: 116 · 2023: 127 · 2022: 115 · 2021: 146 · 2020: 130 · 2019: 88 · 2018: 87 · 2017: 80 · 2016: 56 · 2015: 66 · 2014: 62 · 2013: 47 · 2012: 17
- FWCI
- 46.98
- Type
- conference paper
- Language
- en
- Open access
- green
- pure.au.dk
- Licence
- Locations
- Lecture notes in computer science (publishedVersion)
- Bristol Research (University of Bristol) (submittedVersion)
- Funders
- Engineering and Physical Sciences Research Council (EP/I03126X/1)
- Topics
- Physical Sciences › Computer Science › Artificial Intelligence › Cryptography and Data Security
- Physical Sciences › Computer Science › Information Systems › Cloud Data Security Solutions
- Physical Sciences › Computer Science › Artificial Intelligence › Quantum Information and Cryptography
- Keywords
- secure multi-party computation, somewhat homomorphic encryption, active adversaries, finite fields, distributed decryption, secure multiplication, linear computational complexity
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
