The DOI matches its Crossref record; 74 of the 74 references it cites were found in a registry or an index.
A Pragmatic Introduction to Secure Multi-Party Computation
Open accessAbstract
Secure multi-party computation (MPC) has evolved from a theoretical curiosity in the 1980s to a tool for building real systems today. Over the past decade, MPC has been one of the most active research areas in both theoretical and applied cryptography. This article introduces several important MPC protocols, and surveys methods for improving the efficiency of privacy-preserving applications built using MPC. Besides giving a broad overview of the field and the insights of the main constructions, we overview the most currently active areas of MPC research and aim to give readers insights into what problems are practically solvable using MPC today and how different threat models and assumptions impact the practicality of different approaches.
Overview
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
Verification
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.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Shamir, A. (1979) · Communications of the ACM · doi:10.1145/359168.359176 · Cited by 13,756
Random oracles are practical: a paradigm for designing efficient protocols
Bellare, M., & Rogaway, P. (1993) · Proceedings of the 1st ACM conference on Computer and communications security - CCS '93 · doi:10.1145/168588.168596 · Cited by 4,712
Universally composable security: a new paradigm for cryptographic protocols
Canetti, R. (2001) · Proceedings 42nd IEEE Symposium on Foundations of Computer Science · doi:10.1109/sfcs.2001.959888 · Cited by 3,309
Goldwasser, S., & Micali, S. (1984) · Journal of Computer and System Sciences · doi:10.1016/0022-0000(84)90070-9 · Cited by 2,603
SecureML: A System for Scalable Privacy-Preserving Machine Learning
Mohassel, P., & Zhang, Y. (2017) · 2017 IEEE Symposium on Security and Privacy (SP) · doi:10.1109/sp.2017.12 · Cited by 1,936
Goldreich, O. (2004) · Cambridge University Press eBooks · doi:10.1017/cbo9780511721656 · Cited by 1,805
Evaluating 2-DNF Formulas on Ciphertexts
Boneh, D., Goh, E.-J., & Nissim, K. (2005) · Lecture Notes in Computer Science · doi:10.1007/978-3-540-30576-7_18 · Cited by 1,692
Software protection and simulation on oblivious RAMs
Goldreich, O., & Ostrovsky, R. (1996) · Journal of the ACM · doi:10.1145/233551.233553 · Cited by 1,617
A Tool for Checking ANSI-C Programs
Clarke, E., Kroening, D., & Lerda, F. (2004) · Lecture Notes in Computer Science · doi:10.1007/978-3-540-24730-2_15 · Cited by 1,408
Damgård, I., & Jurik, M. (2001) · Lecture Notes in Computer Science · doi:10.1007/3-540-44586-2_9 · Cited by 1,063
ABY - A Framework for Efficient Mixed-Protocol Secure Two-Party Computation
Demmler, D., Schneider, T., & Zohner, M. (2015) · Proceedings 2015 Network and Distributed System Security Symposium · doi:10.14722/ndss.2015.23113 · Cited by 827
Privacy preserving auctions and mechanism design
Naor, M., Pinkas, B., & Sumner, R. (1999) · Proceedings of the 1st ACM conference on Electronic commerce · doi:10.1145/336992.337028 · Cited by 753
Path ORAM: an extremely simple oblivious RAM protocol
Stefanov, E., van Dijk, M., Shi, E., Fletcher, C., Ren, L., Yu, X., & Devadas, S. (2013) · Proceedings of the 2013 ACM SIGSAC conference on Computer & communications security - CCS '13 · doi:10.1145/2508859.2516660 · Cited by 698
Oblivious Neural Network Predictions via MiniONN Transformations
Liu, J., Juuti, M., Lu, Y., & Asokan, N. (2017) · Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security · doi:10.1145/3133956.3134056 · Cited by 691
A Proof of Security of Yao’s Protocol for Two-Party Computation
Lindell, Y., & Pinkas, B. (2009) · Journal of Cryptology · doi:10.1007/s00145-008-9036-8 · Cited by 651
Leakage-Abuse Attacks Against Searchable Encryption
Cash, D., Grubbs, P., Perry, J., & Ristenpart, T. (2015) · Proceedings of the 22nd ACM SIGSAC Conference on Computer and Communications Security · doi:10.1145/2810103.2813700 · Cited by 609
Foundations of garbled circuits
Bellare, M., Hoang, V. T., & Rogaway, P. (2012) · Proceedings of the 2012 ACM conference on Computer and communications security · doi:10.1145/2382196.2382279 · Cited by 541
Secure Multiparty Computation Goes Live
Bogetoft, P., Christensen, D. L., Damgård, I., Geisler, M., Jakobsen, T., Krøigaard, M., Nielsen, J. D., Nielsen, J. B., Nielsen, K., Pagter, J., et al. (2009) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-03549-4_20 · Cited by 539
Inference Attacks on Property-Preserving Encrypted Databases
Naveed, M., Kamara, S., & Wright, C. V. (2015) · Proceedings of the 22nd ACM SIGSAC Conference on Computer and Communications Security · doi:10.1145/2810103.2813651 · Cited by 502
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 454
Privacy-Preserving Ridge Regression on Hundreds of Millions of Records
Nikolaenko, V., Weinsberg, U., Ioannidis, S., Joye, M., Boneh, D., & Taft, N. (2013) · 2013 IEEE Symposium on Security and Privacy · doi:10.1109/sp.2013.30 · Cited by 439
MASCOT: Faster Malicious Arithmetic Secure Computation with Oblivious Transfer
Keller, M., Orsini, E., & Scholl, P. (2016) · Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security · doi:10.1145/2976749.2978357 · Cited by 411
High-Throughput Semi-Honest Secure Three-Party Computation with an Honest Majority
Araki, T., Furukawa, J., Lindell, Y., Nof, A., & Ohara, K. (2016) · Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security · doi:10.1145/2976749.2978331 · Cited by 405
Relations Among Complexity Measures
Pippenger, N., & Fischer, M. J. (1979) · Journal of the ACM · doi:10.1145/322123.322138 · Cited by 387
Efficient Batched Oblivious PRF with Applications to Private Set Intersection
Kolesnikov, V., Kumaresan, R., Rosulek, M., & Trieu, N. (2016) · Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security · doi:10.1145/2976749.2978381 · Cited by 380
Self-citationEfficient Privacy-Preserving Face Recognition
Sadeghi, A.-R., Schneider, T., & Wehrenberg, I. (2010) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-14423-3_16 · Cited by 363
Function Secret Sharing: Improvements and Extensions
Boyle, E., Gilboa, N., & Ishai, Y. (2016) · Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security · doi:10.1145/2976749.2978429 · Cited by 358
A new public key cryptosystem based on higher residues
Naccache, D., & Stern, J. (1998) · Proceedings of the 5th ACM conference on Computer and communications security · doi:10.1145/288090.288106 · Cited by 352
Two Round Multiparty Computation via Multi-key FHE
Mukherjee, P., & Wichs, D. (2016) · Lecture Notes in Computer Science · doi:10.1007/978-3-662-49896-5_26 · Cited by 308
Ligero: Lightweight Sublinear Arguments Without a Trusted Setup
Ames, S., Hazay, C., Ishai, Y., & Venkitasubramaniam, M. (2017) · Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security · doi:10.1145/3133956.3134104 · Cited by 305
EnclaveDB: A Secure Database Using SGX
Priebe, C., Vaswani, K., & Costa, M. (2018) · 2018 IEEE Symposium on Security and Privacy (SP) · doi:10.1109/sp.2018.00025 · Cited by 284
Composition and integrity preservation of secure reactive systems
Pfitzmann, B., & Waidner, M. (2000) · Proceedings of the 7th ACM conference on Computer and Communications Security · doi:10.1145/352600.352639 · Cited by 277
Privacy-preserving matrix factorization
Nikolaenko, V., Ioannidis, S., Weinsberg, U., Joye, M., Taft, N., & Boneh, D. (2013) · Proceedings of the 2013 ACM SIGSAC conference on Computer & communications security - CCS '13 · doi:10.1145/2508859.2516751 · Cited by 271
Improved Garbled Circuit Building Blocks and Applications to Auctions and Computing Minima
Kolesnikov, V., Sadeghi, A.-R., & Schneider, T. (2009) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-10433-6_1 · Cited by 263
Self-citationImproved Non-Interactive Zero Knowledge with Applications to Post-Quantum Signatures
Katz, J., Kolesnikov, V., & Wang, X. (2018) · Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security · doi:10.1145/3243734.3243805 · Cited by 228
Self-citationPerfectly-Secure MPC with Linear Communication Complexity
Beerliová-Trubíniová, Z., & Hirt, M. (2008) · Lecture Notes in Computer Science · doi:10.1007/978-3-540-78524-8_13 · Cited by 222
Practical Multi-party Private Set Intersection from Symmetric-Key Techniques
Kolesnikov, V., Matania, N., Pinkas, B., Rosulek, M., & Trieu, N. (2017) · Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security · doi:10.1145/3133956.3134065 · Cited by 200
Self-citationPrivacy-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
Self-citationScaling ORAM for Secure Computation
Doerner, J., & Shelat, A. (2017) · Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security · doi:10.1145/3133956.3133967 · Cited by 182
Secure Two-Party Computation via Cut-and-Choose Oblivious Transfer
Lindell, Y., & Pinkas, B. (2011) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-19571-6_20 · Cited by 175
Authenticated Garbling and Efficient Maliciously Secure Two-Party Computation
Wang, X., Ranellucci, S., & Katz, J. (2017) · Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security · doi:10.1145/3133956.3134053 · Cited by 168
Oblix: An Efficient Oblivious Search Index
Mishra, P., Poddar, R., Chen, J., Chiesa, A., & Popa, R. A. (2018) · 2018 IEEE Symposium on Security and Privacy (SP) · doi:10.1109/sp.2018.00045 · Cited by 168
Efficient Two-Party Secure Computation on Committed Inputs
Jarecki, S., & Shmatikov, V. (2007) · Lecture Notes in Computer Science · doi:10.1007/978-3-540-72540-4_6 · Cited by 162
LEGO for Two-Party Secure Computation
Nielsen, J. B., & Orlandi, C. (2009) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-00457-5_22 · Cited by 158
Privacy-preserving remote diagnostics
Brickell, J., Porter, D. E., Shmatikov, V., & Witchel, E. (2007) · ACM SIGSAC Conference on Computer and Communications Security (CCS) · doi:10.1145/1315245.1315307 · Cited by 158
Efficiency Tradeoffs for Malicious Two-Party Computation
Mohassel, P., & Franklin, M. (2006) · Lecture notes in computer science · doi:10.1007/11745853_30 · Cited by 154
Implementing Two-Party Computation Efficiently with Security Against Malicious Adversaries
Lindell, Y., Benny Pinkas, B., & Smart, N. P. (2008) · Lecture notes in computer science · doi:10.1007/978-3-540-85855-3_2 · Cited by 142
Efficient, Oblivious Data Structures for MPC
Keller, M., & Schöll, P. (2014) · Lecture notes in computer science · doi:10.1007/978-3-662-45608-8_27 · Cited by 136
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
Secure two-party computations in ANSI C
Holzer, A., Franz, M., Katzenbeisser, S., & Veith, H. (2012) · ACM SIGSAC Conference on Computer and Communications Security (CCS) · doi:10.1145/2382196.2382278 · Cited by 125
Efficient Genome-Wide, Privacy-Preserving Similar Patient Query based on Private Edit Distance
Wang, X. S., Huang, Y., Zhao, Y., Tang, H., Wang, X., & Bu, D. (2015) · ACM SIGSAC Conference on Computer and Communications Security (CCS) · doi:10.1145/2810103.2813725 · Cited by 119
A Practical Universal Circuit Construction and Secure Evaluation of Private Functions
Kolesnikov, V., & Schneider, T. H. (2008) · Lecture notes in computer science · doi:10.1007/978-3-540-85230-8_7 · Cited by 112
Self-citationFast and Secure Three-party Computation: The Garbled Circuit Approach
Mohassel, P., Rosulek, M., & Zhang, Y. (2015) · ACM SIGSAC Conference on Computer and Communications Security (CCS) · doi:10.1145/2810103.2813705 · Cited by 112
Self-citationSecure outsourced garbled circuit evaluation for mobile devices
Carter, H., Mood, B., Traynor, P., & Butler, K. R. B. (2015) · Journal of Computer Security · doi:10.3233/jcs-150540 · Cited by 111
Quid-Pro-Quo-tocols: Strengthening Semi-honest Protocols with Dual Execution
Huang, Y., Katz, J., & Evans, D. (2012) · IEEE Symposium on Security and Privacy (S&P) · doi:10.1109/sp.2012.43 · Cited by 102
Self-citationOn the Security of the “Free-XOR” Technique
Choi, S. G., Katz, J. I., Kumaresan, R., & Zhou, H.-S. (2012) · Lecture notes in computer science · doi:10.1007/978-3-642-28914-9_3 · Cited by 94
Constant-Overhead Secure Computation of Boolean Circuits using Preprocessing
Damgård, I., & Zakarias, S. (2013) · Lecture notes in computer science · doi:10.1007/978-3-642-36594-2_35 · Cited by 94
Combining Differential Privacy and Secure Multiparty Computation
Pettai, M., & Laud, P. (2015) · Annual Computer Security Applications Conference · doi:10.1145/2818000.2818027 · Cited by 94
Fast two-party secure computation with minimal assumptions
Shelat, A. A., & Shen, C.-H. (2013) · ACM SIGSAC Conference on Computer and Communications Security (CCS) · doi:10.1145/2508859.2516698 · Cited by 87
Frigate: A Validated, Extensible, and Efficient Compiler and Interpreter for Secure Computation
Mood, B., Gupta, D., Carter, H., Butler, K. R. B., & Traynor, P. (2016) · IEEE European Symposium on Security and Privacy · doi:10.1109/eurosp.2016.20 · Cited by 83
Privacy-Preserving Distributed Profile Matching in Proximity-Based Mobile Social Networks
Li, M., Yu, S., Cao, N., & Lou, W. (2013) · IEEE Transactions on Wireless Communications · doi:10.1109/twc.2013.032513.120149 · Cited by 70
Constructions of truly practical secure protocols using standardsmartcards
Hazay, C., & Lindell, Y. (2008) · ACM SIGSAC Conference on Computer and Communications Security (CCS) · doi:10.1145/1455770.1455832 · Cited by 69
SGX-BigMatrix: A Practical Encrypted Data Analytic Framework With Trusted Processors
Shaon, F., Kantarcıoğlu, M., Lin, Z., & Khan, L. R. (2017) · ACM SIGSAC Conference on Computer and Communications Security (CCS) · doi:10.1145/3133956.3134095 · Cited by 67
Blazing Fast 2PC in the Offline/Online Setting with Security for Malicious Adversaries
Lindell, Y., & Riva, B. (2015) · ACM SIGSAC Conference on Computer and Communications Security (CCS) · doi:10.1145/2810103.2813666 · Cited by 66
Implementing AES via an Actively/Covertly Secure Dishonest-Majority MPC Protocol
Damgård, I., Keller, M., Larraia, E., Miles, C., & Smart, N. P. (2012) · Lecture notes in computer science · doi:10.1007/978-3-642-32928-9_14 · Cited by 62
Circuit Structures for Improving Efficiency of Security and Privacy Tools
Zahur, S., & Evans, D. (2013) · IEEE Symposium on Security and Privacy (S&P) · doi:10.1109/sp.2013.40 · Cited by 60
Self-citationComplete Characterization of Fairness in Secure Two-Party Computation of Boolean Functions
Asharov, G., Beimel, A., Makriyannis, N., & Omri, E. (2015) · Lecture notes in computer science · doi:10.1007/978-3-662-46494-6_10 · Cited by 47
Secure Stable Matching at Scale
Doerner, J., Evans, D., & Shelat, A. A. (2016) · ACM SIGSAC Conference on Computer and Communications Security (CCS) · doi:10.1145/2976749.2978373 · Cited by 46
Self-citationDifferentially Private Oblivious RAM
Wagh, S., Cuff, P., & Mittal, P. (2018) · Proceedings on Privacy Enhancing Technologies · doi:10.1515/popets-2018-0032 · Cited by 38
Kolesnikov, V., Sadeghi, A., & Schneider, T. H. (2013) · Journal of Computer Security · doi:10.3233/jcs-130464 · Cited by 36
Self-citationBrandão, L. T. A. N. (2013) · Lecture notes in computer science · doi:10.1007/978-3-642-42045-0_23 · Cited by 36
Public Verifiability in the Covert Model (Almost) for Free
Kolesnikov, V., & Malozemoff, A. J. (2015) · Lecture notes in computer science · doi:10.1007/978-3-662-48800-3_9 · Cited by 26
Self-citationEfficient, Constant-Round and Actively Secure MPC
Chandran, N., Garay, J. A., Mohassel, P., & Vusirikala, S. (2017) · ACM SIGSAC Conference on Computer and Communications Security (CCS) · doi:10.1145/3133956.3134100 · Cited by 14
Limits of Practical Sublinear Secure Computation
Boyle, E., Ishai, Y., & Polychroniadou, A. (2018) · Lecture notes in computer science · doi:10.1007/978-3-319-96878-0_11 · Cited by 5
Cited by
Secure, privacy-preserving and federated machine learning in medical imaging
Kaissis, G. A., Makowski, M. R., Rückert, D., & Braren, R. F. (2020) · Nature Machine Intelligence · doi:10.1038/s42256-020-0186-1 · Cited by 1,676
Robust Aggregation for Federated Learning
Pillutla, K., Kakade, S. M., & Harchaoui, Z. (2022) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2022.3153135 · Cited by 801
Trustworthy AI: From Principles to Practices
Li, B., Qi, P., Liu, B., Di, S., Liu, J., Pei, J., Yi, J., & Zhou, B. (2023) · ACM Computing Surveys · doi:10.1145/3555803 · Cited by 612
“A typical SMPC protocol satisfies properties of privacy, correctness, independence of inputs, guaranteed output delivery, and fairness [114, 387].”
BackgroundInfluentialEnd-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
Lindell, Y. (2021) · Communications of the ACM · doi:10.1145/3387108 · Cited by 320
Metadata
- Authors
- Evans, D., Kolesnikov, V., & Rosulek, M.
- Venue
- Foundations and Trends® in Privacy and Security
- Publisher
- Emerald
- Published
- 2018-12-19
- Volume
- 2
- Issue
- 2-3
- Pages
- 70-246
- ISSN
- 2474-1558 (ISSN-L)
- 2474-1566
- OpenAlex
- W2903850320
- Cited by
- 321
- References
- 74
- FWCI
- 16.41
- Type
- journal article
- Language
- en
- Open access
- diamond
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
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.