Skip to content

Latest commit

 

History

History
365 lines (268 loc) · 17.4 KB

mpc.md

File metadata and controls

365 lines (268 loc) · 17.4 KB

Secure Multi-Party Computation (MPC)

"The design of scure protocols that implement arbitrarily desired functionalities is a major part of mordern cryptography." -- Foundation of Cryptography, Volumn 2, Oded Goldreich.

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. In the following, we try to show the newest and interesting advances in mpc (both theory & applicaiton), and also the infulential papers in history.

Note: one paper may be included in several categories (e.g. a paper may introduce a new protocol for both OT and VOLE, we decide to include it in both categories).

Table of Contents

Basic

Books

  • A Pragmatic Introduction to Secure Multi-Party Computation David Evans, Vladimir Kolesnikov, Mike Rosulek eprint

Offline Techniques

Oblivious transfer

  • Endemic Oblivious Transfer via Random Oracles, Revisited Zhelei Zhou, Bingsheng Zhang, Hong-Sheng Zhou, Kui Ren EuroCrypt 2023, eprint, ZZZR23

  • SoftSpokenOT: Quieter OT Extension from Small-Field Silent VOLE in the Minicrypt Model Lawrence Roy Crypto 2022, eprint, Roy22

  • Silver: Silent VOLE and Oblivious Transfer from Hardness of Decoding Structured LDPC Codes Geoffroy Couteau, Peter Rindal, Srinivasan Raghuraman Crypto 2021, eprint, CRR21

  • The Rise of Paillier: Homomorphic Secret Sharing and Public-Key Silent OT Claudio Orlandi, Peter Scholl, Sophia Yakoubov EuroCrypt 2021, eprint, OSY21

  • Batching Base Oblivious Transfers Ian McQuoid, Mike Rosulek, Lawrence Roy AsiaCrypt 2021, eprint, MRR21

  • Ferret: Fast Extension for Correlated OT with Small Communication Kang Yang, Chenkai Weng, Xiao Lan, Jiang Zhang, Xiao Wang CCS 2020, eprint, YWLZ+20

  • Efficient and Round-Optimal Oblivious Transfer and Commitment with Adaptive Security Ran Canetti, Pratik Sarkar, Xiao Wang AsiaCrypt 2020, eprint, CSW20

  • Efficient Two-Round OT Extension and Silent Non-Interactive Secure Computation Elette Boyle, Geoffroy Couteau, Niv Gilboa, Yuval Ishai, Lisa Kohl, Peter Rindal, Peter Scholl CCS 2019, eprint, BCGI+19 (with Peter Rindal)

  • Endemic Oblivious Transfer Daniel Masny, Peter Rindal CCS 2019, eprint, MR19

  • Efficient Pseudorandom Correlation Generators: Silent OT Extension and More Elette Boyle, Geoffroy Couteau, Niv Gilboa, Yuval Ishai, Lisa Kohl, Peter Scholl Crypto 2019, eprint, BCGI+19 (without Peter Rindal)

  • Equational Security Proofs of Oblivious Transfer Protocols Baiyu Li, Daniele Micciancio PKC 2018, eprint, LM18

  • Actively Secure 1-out-of-N OT Extension with Application to Private Set Intersection Michele Orrù, Emmanuela Orsini, Peter Scholl CT-RSA 2017, eprint, OOS17

  • Actively Secure OT Extension with Optimal Overhead Marcel Keller, Emmanuela Orsini, Peter Scholl Crypto 2015, eprint, KOS15

  • The Simplest Protocol for Oblivious Transfer Tung Chou, Claudio Orlandi LatinCrypt 2015, eprint, CO15

  • More Efficient Oblivious Transfer and Extensions for Faster Secure Computation Gilad Asharov, Yehuda Lindell, Thomas Schneider, Michael Zohner CCS 2013, eprint, ALSZ13

  • A Framework for Efficient and Composable Oblivious Transfer Chris Peikert, Vinod Vaikuntanathan, Brent Waters Crypto 2008, eprint, PVW08

  • Extending Oblivious Transfers Efficiently Yuval Ishai, Joe Kilian, Kobbi Nissim, Erez Petrank Crypto 2003, eprint, IKNP03

  • Efficient oblivious transfer protocols Moni Naor, Benny Pinkas SODA 2001, eprint, NP01

  • Oblivious Transfer and Polynomial Evaluation Moni Naor, Benny Pinkas STOC 1999, eprint, NP99

  • Non-interactive oblivious transfer and applications Mihir Bellare, Silvio Micali Crypto 1989, eprint, BM89

vector Oblivious Linear Evaluation

  • Actively Secure Arithmetic Computation and VOLE with Constant Computational Overhead Benny Applebaum, Niv Konstantini EuroCrypt 2023, eprint, AK23

  • Two-Round Oblivious Linear Evaluation from Learning with Errors Pedro Branco, Nico Do ̈ttling, Paulo Mateus PKC 2022, eprint, BDM22

  • Moz$\mathbb{Z}_{2^k}$ arella: Efficient Vector-OLE and Zero-Knowledge Proofs Over $\mathbb{Z}_{2^k}$ Carsten Baum, Lennart Braun, Alexander Munch-Hansen, and Peter Scholl Crypto 2022, eprint, BBMS22

  • Correlated Pseudorandomness from Expand-Accumulate Codes Elette Boyle, Geoffroy Couteau, Niv Gilboa, Yuval Ishai, Lisa Kohl, Nicolas Resch, Peter Scholl Crypto 2022, eprint, BCG+22

  • Two-Round Oblivious Linear Evaluation from Learning with Errors Pedro Branco, Nico Döttling, Paulo Mateus PKC 2022, eprint, BDM22

  • Wolverine: Fast, Scalable, and Communication-Efficient Zero-Knowledge Proofs for Boolean and Arithmetic Circuits Chenkai Weng, Kang Yang, Jonathan Katz, and Xiao Wang S&P 2021, paper, WYK+21

  • Silver: Silent VOLE and Oblivious Transfer from Hardness of Decoding Structured LDPC Codes Geoffroy Couteau, Peter Rindal, Srinivasan Raghuraman Crypto 2021, eprint, CRR21

  • Efficient Protocols for Oblivious Linear Function Evaluation from Ring-LWE Carsten Baum, Daniel Escudero, Alberto Pedrouzo-Ulloa, Peter Scholl, Juan Ramón Troncoso-Pastoriza SCN 2020, eprint, BEPS+20

  • Distributed vector-OLE: Improved constructions and implementation Phillipp Schoppmann, Adrià Gascón, Leonie Reichert, Mariana Raykova CCS 2019, eprint, SGRR19

  • Compressing vector OLE Elette Boyle, Geoffroy Couteau, Niv Gilboa, Yuval Ishai CCS 2018, eprint, BCGI18

  • Secure Arithmetic Computation with Constant Computational Overhead Benny Applebaum, Ivan Damgård, Yuval Ishai, Michael Nielsen, Lior Zichron Crypto 2017, eprint, ADI+17

  • Maliciously secure oblivious linear function evaluation with constant overhead Satrajit Ghosh, Jesper Buus Nielsen, Tobias Nilges AsiaCrypt 2017, eprint, GNN17

  • TinyOLE: Efficient actively secure two-party computation from oblivious linear function evaluation Nico Döttling, Satrajit Ghosh, Jesper Buus Nielsen, Tobias Nilges, Roberto Trifiletti CCS 2017, eprint, DGNN+17

  • Oblivious Transfer and Polynomial Evaluation Moni Naor, Benny Pinkas STOC 1999, eprint, NP99

Pseudorandom-Correlation Generator

  • Correlated Pseudorandomness from the Hardness of Quasi-Abelian Decoding Maxime Bombar, Geoffroy Couteau, Alain Couvreur, Clément Ducros Crypto 2023, eprint, BCCD23

  • Expand-Convolute Codes for Pseudorandom Correlation Generators from LPN Srinivasan Raghuraman, Peter Rindal, Titouan Tanguy Crypto 2023, eprint, RRT23

  • Correlated Pseudorandomness from Expand-Accumulate Codes Elette Boyle, Geoffroy Couteau, Niv Gilboa, Yuval Ishai, Lisa Kohl, Nicolas Resch, Peter Scholl Crypto 2022, eprint, BCG+22

  • Efficient Pseudorandom Correlation Generators from Ring-LPN Elette Boyle, Geoffroy Couteau, Niv Gilboa, Yuval Ishai, Lisa Kohl, Peter Scholl Crypto 2020, eprint, BCG+20

Others

  • Overdrive LowGear 2.0: Reduced-Bandwidth MPC without Sacrifice Sebastian Hasler, Toomas Krips, Ralf Küsters, Pascal Reisert, Marc Rivinius ASIA CCS 2023 eprint

Online Techniques

Semi-Honest Secret Sharing

  • Cheetah: Lean and Fast Secure Two-Party Deep Neural Network Inference Zhicong Huang, Wen-jie Lu, Cheng Hong, Jiansheng Ding USENIX Security 2022, eprint, HLHD22

  • ABY2.0: Improved Mixed-Protocol Secure Two-Party Computation Arpita Patra, Thomas Schneider, Ajith Suresh, Hossein Yalame Usenix Security 2021, eprint, PSSY21

  • Improved primitives for MPC over mixed arithmetic-binary circuits Daniel Escudero, Satrajit Ghosh, Marcel Keller ,Rahul Rachuri, Peter Scholl Crypto 2020, eprint

  • MArBled Circuits: Mixing Arithmetic and Boolean Circuits with Active Security Dragos Rotaru, Tim Wood IndoCrypt 2019, eprint

  • High-Throughput Secure Three-Party Computation for Malicious Adversaries and an Honest Majority Jun Furukawa, Yehuda Lindell, Ariel Nof, Or Weistein EuroCrypt 2017, eprint, FLNW17

  • ABY - A Framework for Efficient Mixed-Protocol Secure Two-Party Computation Daniel Demmler, Thomas Schneider, Michael Zohner NDSS 2017, eprint, DSZ17

  • Secure Computation with Fixed-Point Numbers Octavian Catrina, Amitabh Saxena FC 2010, eprint, CS10

  • The Round Complexity of Secure Protocols Donald Beaver, Silvio Micali, Phillip Rogaway STOC 1990, eprint, BMR90

  • Completeness Theorems for Non-Cryptographic Fault Tolerant Distributed Computation Michael Ben-Or, Shafi Goldwasser, Avi Wigderson STOC 1988, eprint, BGW88

  • How to play any mental game? Oded Goldreich, Silvio Micali, Avi Wigderson STOC 1987, eprint, GMW87

  • How to generate and exchange secrets? Andrew Chi-Chih Yao FOCS 1986, eprint, Yao86

Malicious Secret Sharing

  • MHz2k: MPC from HE over Z2k with New Packing, Simpler Reshare, and Better ZKP Jung Hee Cheon, Dongwoo Kim, and Keewoo Lee Crypto 2021, eprint, CKL21

  • High-Performance Multi-party Computation for Binary Circuits Based on Oblivious Transfer Sai Sheshank Burra, Enrique Larraia, Jesper Buus Nielsen, Peter Sebastian Nordholt, Claudio Orlandi, Emmanuela Orsini, Peter Scholl, Nigel P. Smart JCryptpo 2021, eprint, BLNN+21

  • An Efficient Passive-to-Active Compiler for Honest-Majority MPC over Rings Mark Absponel, Anders Dalskov, Daniel Escudero, Ariel Nof ACNS 2021, eprint

  • Fantastic Four: Honest-Majority Four-Party Secure Computation With Malicious Security Anders Dalskov, Daniel Escudero, and Marcel Keller Usenix Security 2021, eprint

  • Overdrive2k: Efficient Secure MPC over Z2k from Somewhat Homomorphic Encryption Emmanuela Orsini, Nigel P. Smart, Frederik Vercauteren CT-RSA 2020, eprint, OSV20

  • MonZ2k: Fast Maliciously Secure Two Party Computation on Z2k Dario Catalano, Mario Di Raimondo, Dario Fiore, and Irene Giacomelli PKC 2020, eprint, CRFG20

  • MP-SPDZ: A Versatile Framework for Multi-Party Computation Marcel Keller CCS 2020, eprint, Kel20

  • Covert Security with Public Verifiability: Faster, Leaner, and Simpler Cheng Hong, Jonathan Katz, Vladimir Kolesnikov, Wen-jie Lu, Xiao Wang EuroCrypt 2019, eprint, HKKL+19

  • Two-Thirds Honest-Majority MPC for Malicious Adversaries at Almost the Cost of Semi-Honest Jun Furukawa, Yehuda Lindell CCS 2019, eprint, FL19

  • Communication Lower Bounds for Statistically Secure MPC, With or Without Preprocessing Ivan Damgård, Kasper Green Larsen, Jesper Buus Nielsen Crypto 2019, eprint, DLN19

  • New Primitives for Actively-Secure MPC over Rings with Applications to Private Machine Learning Ivan Damgård, Daniel Escudero, Tore Frederiksen, Marcel Keller, Peter Scholl, Nikolaj Volgushev SP 2019, eprint, DEFK+19

  • Adaptively Secure MPC with Sublinear Communication Complexity Ran Cohen, Abhi Shelat, Daniel Wichs Crypto 2019, eprint, CSW19

  • ABY3: A Mixed Protocol Framework for Machine Learning Payman Mohassel, Peter Rindal CCS 2018, eprint, MR18

  • Fast Large-Scale Honest-Majority MPC for Malicious Adversaries Koji Chida, Daniel Genkin, Koki Hamada, Dai Ikarashi, Ryo Kikuchi, Yehuda Lindell, Ariel Nof Crypto 2018, eprint

  • SPD$\mathbb {Z}_{2^k}$: Efficient MPC mod $2^k$ for Dishonest Majority Ronald Cramer, Ivan Damgård, Daniel Escudero, Peter Scholl, Chaoping Xing Crypto 2018, eprint, Spdz2k

  • Optimized Honest-Majority MPC for Malicious Adversaries — Breaking the 1 Billion-Gate Per Second Barrier Toshinori Araki, Assi Barak, Jun Furukawa, Tamar Lichter, Yehuda Lindell, Ariel Nof, Kazuma Ohara, Adi Watzman, Or Weinstein S&P 2017, eprint

  • Zero-Knowledge Proofs on Secret-Shared Data via Fully Linear PCPs Dan Boneh, Elette Boyle, Henry Corrigan-Gibbs, Niv Gilboa, Yuval Ishai Crypto 2019, eprint, BBCG+19

  • Practical Fully Secure Three-Party Computation via Sublinear Distributed Zero-Knowledge Proofs Elette Boyle, Niv Gilboa, Yuval Ishai, and Ariel Nof CCS 2019, eprint, BGIN19

Function Secret Sharing

  • Programmable Distributed Point Functions Elette Boyle, Niv Gilboa, Yuval Ishai, Victor I. Kolobov Crypto 2022, eprint, BGIK22

  • Lightweight, Maliciously Secure Verifiable Function Secret Sharing Leo de Castro and Antigoni Polychroniadou EuroCrypt 2022, eprint, CP22

  • Lightweight Techniques for Private Heavy Hitters Dan Boneh, Elette Boyle, Henry Corrigan-Gibbs, Niv Gilboa, Yuval Ishai SP 2021, eprint, BBGG+21

  • Function Secret Sharing for PSI-CA : With Applications to Private Contact Tracing Samuel Dittmer, Yuval Ishai, Steve Lu, Rafail Ostrovsky, Mohamed Elsabagh, Nikolaos Kiourtis, Brian Schulte, Angelos Stavrou Unpublished 2021, eprint, DILO+21

  • Function Secret Sharing for Mixed-Mode and Fixed-Point Secure Computation Elette Boyle, Nishanth Chandran, Niv Gilboa, Divya Gupta, Yuval Ishai, Nishant Kumar, Mayank Rathee EuroCrypt 2021, eprint, BCGI+21

  • Correlated Pseudorandom Functions from Variable-Density LPN Elette Boyle, Geoffroy Couteau, Niv Gilboa, Yuval Ishai, Lisa Kohl, Peter Scholl FOCS 2020, eprint, BCGI+20

  • Secure Computation with Preprocessing via Function Secret Sharing Elette Boyle, Niv Gilboa, Yuval Ishai TCC 2019, eprint, BGI19

  • Efficient Two-Round OT Extension and Silent Non-Interactive Secure Computation Elette Boyle, Geoffroy Couteau, Niv Gilboa, Yuval Ishai, Lisa Kohl, Peter Rindal, Peter Scholl CCS 2019, eprint, BCGI+19

  • Function secret sharing: Improvements and extensions Elette Boyle, Niv Gilboa, Yuval Ishai CCS 2016, eprint, BGI16

  • Function Secret Sharing Elette Boyle, Niv Gilboa, Yuval Ishai EuroCrypt 2015, eprint, BGI15

  • Distributed Point Functions and Their Applications Niv Gilboa, Yuval Ishai EuroCrypt 2014, eprint, GI14