awesome-secure-computation

This repo is a paper summary for cryptography-based secure computation papers (I prefer published papers 😛), including topics like Multiparty Computation, Homomorphic Encryption (or Lattice) and Differential Privacy. If you are looking for hardware solutions like Trusted Platform Module (TPM), or Trusted Execution Environment (TEE), I'm sorry this repo is not what you're looking for :(.

Here's a good place to ask questions about cryptography/cryptanalysis, or answering one (if you are capable of doing so): https://crypto.stackexchange.com/, and finding papers Cryptology ePrint Archive.

Useful Links:

• Security Conferences Ranking (By Prof. Guofei Gu)
• Security and Privacy Conference Deadlines
• Crypto21: Mentoring Videos about how to do research in cryptography

Texbooks:

• A Pragmatic Introduction to Secure Multi-Party Computation
  David Evans, Vladimir Kolesnikov, and Mike Rosulek
  eprint avaliable
• Foundations of Cryptography
  Oded Goldreich
  author's notes
• Introduction to Modern Cryptography
  Jonathan Katz and Yehuda Lindell
  author's notes

Open-source Tools (mostly in C++):

• [secretflow/yacl]: OT, OPRF (🤠 I participant in the develop of yacl, so don't hesitate to contact me if you have any questions or suggestions)
• [emp-toolkit]: OT, ZKP, MPC
• [libOTe]: OT, VOLE
• [libPSI]: PSI
• [MP-SPDZ]: Generic MPC

Table of Papers

• MPC
  • Summaries and Talks
  • OT
  • OLE/vOLE
  • OPRF and PSI
  • PIR
  • PFE
  • FSS
  • Semi-honest MPC
  • Malicious MPC
• Lattice
  • Summaries and Talks
  • HE

MPC

MPC: Multi-Party Computation

Summaries and Talks

• 10th BIU Winter School: information-theoretic cryptography, 2020, link
• 9th BIU Winter School: information-theoretic cryptography: zero-knowledge proofs, 2019
• SoK: General purpose compilers for secure multi-party computation, 2019, Github, Paper
• Crypto Innovation School 2018, link

OT

OT: Oblivious Transfer
1-out-of-2 base OT and OT Extensions

• SoftSpokenOT: Quieter OT Extension from Small-Field Silent VOLE in the Minicrypt Model
  Lawrence Roy
  Crypto 2022, publisher, 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

• 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)

• 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

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

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

(s)(v)OLE

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

• 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

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

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

• 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

• 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, 2017,
  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

OPRF and PSI

• Improved Private Set Intersection for Sets with Small Entries
  S. Dov Gordon, Carmit Hazay, Phi Hung Le
  PKC 2023, eprint

• Blazing Fast PSI from Improved OKVS and Subfield VOLE
  Peter Rindal, Srinivasan Raghuraman
  CCS 2022, eprint

• Fully Secure PSI via MPC-in-the-Head
  S. Dov Gordon, Carmit Hazay, Phi Hung Le
  Pets 2022, eprint

• PSI from Ring-OLE
  Wutichai Chongchitmate, Yuval Ishai, Steve Lu, Rafail Ostrovsky
  CCS 2022, link

• (Industry) The Apple PSI System
  analysis

• Circuit-PSI with Linear Complexity via Relaxed Batch OPPRF
  Nishanth Chandran, Divya Gupta, Akash Shah
  PETS 2022, eprint, CGS22

• Oblivious Key-Value Stores and Amplification for Private Set Intersection
  Gayathri Garimella, Benny Pinkas, Mike Rosulek, Ni Trieu, Avishay Yanai
  Crypto 2021, eprint, GPRT+21

• Compact and Malicious Private Set Intersection for Small Sets
  Mike Rosulek, Ni Trieu
  CCS 2021, eprint, RT21

• Simple, Fast Malicious Multiparty Private Set Intersection
  Ofri Nevo, Ni Trieu, Avishay Yanai
  CCS 2021, eprint, NTY21

• Labeled PSI from Homomorphic Encryption with Reduced Computation and Communication
  Kelong Cong, Radames Cruz Moreno, Mariana Botelho da Gama, Wei Dai, Ilia Iliashenko, Kim Laine, Michael Rosenberg
  CCS 2021, eprint, CMBD+21

• VOLE-PSI: Fast OPRF and Circuit-PSI from Vector-OLE
  Peter Rindal, Phillipp Schoppmann
  EuroCrypt 2021, eprint, RS21

• Private Set Operations from Oblivious Switching
  Gayathri Garimella, Payman Mohassel, Mike Rosulek, Saeed Sadeghian, Jaspal Singh
  PKC 2021, eprint, GMRS21

• Private Matching for Compute
  Prasad Buddhavarapu, Andrew Knox, Payman Mohassel, Shubho Sengupta, Erik Taubeneck, Vlad Vlaskin
  Unpublished 2020, eprint

• Private Set Intersection in the Internet Setting From Lightweight Oblivious PRF
  Melissa Chase, Peihan Miao
  Crypto 2020, eprint, CM20

• SpOT-Light: Lightweight Private Set Intersection from Sparse OT Extension, 2019,
  Benny Pinkas, Mike Rosulek, Ni Trieu, Avishay Yanai
  Crypto 2019, eprint, PRTY19

• PIR-PSI: Scaling Private Contact Discovery
  Daniel Demmler, Peter Rindal, Mike Rosulek, Ni Trieu
  PETS 2018, eprint, DRRT18

• Malicious-Secure Private Set Intersection via Dual Execution
  Peter Rindal, Mike Rosulek
  CCS 2017, eprint, RR17b

• Improved Private Set Intersection Against Malicious Adversaries
  Peter Rindal, Mike Rosulek
  EuroCrypt 2017, eprint, RR17a

• Efficient Batched Oblivious PRF with Applications to Private Set Intersection
  Vladimir Kolesnikov, Ranjit Kumaresan, Mike Rosulek, Ni Trieu
  CCS 2016, eprint, KKRT16

• Phasing: Private Set Intersection using Permutation-based Hashing
  Benny Pinkas, Thomas Schneider, Gil Segev, Michael Zohner
  Usenix Security 2015, eprint, PSSZ15

• Private Set Intersection: Are Garbled Circuits Better than Custom Protocols? Yan Huang, David Evans, Jonathan Katz
  NDSS 2012, eprint, HEK12

• Linear-Complexity Private Set Intersection Protocols Secure in Malicious Model
  Emiliano De Cristofaro, Jihye Kim, Gene Tsudik
  AsiaCrypt 2010, eprint, CKT10

• Practical Private Set Intersection Protocols with Linear Computational and Bandwidth Complexity
  Emiliano De Cristofaro, Gene Tsudik
  Unpublished 2010, eprint, CT10

• Information Sharing Across Private Databases
  Rakesh Agrawal, Alexandre V. Evfimievski, Ramakrishnan Srikant
  SIGMOD 2003, eprint, AES03

PIR

• OnionPIR: Response Efficient Single-Server PIR
  Muhammad Haris Mughees, Hao Chen, Ling Ren
  CCS 2021, eprint, MCR21

• On the Security of Doubly Efficient PIR
  Elette Boyle, Justin Holmgren, Fermi Ma, Mor Weiss
  Report 2021, eprint

• Random-index PIR with Applications to Large-Scale Secure MPC
  Craig Gentry, Shai Halevi, Bernardo Magri, Jesper Buus Nielsen, Sophia Yakoubov
  TCC 2021, eprint, GHMN+20

• Private Information Retrieval with Sublinear Online Time
  Henry Corrigan-Gibbs, Dmitry Kogan
  EuroCrypt 2020, eprint, GK20

• Batched Differentially Private Information Retrieval
  Kinan Dak Albab, Rawane Issa, Mayank Varia, Kalman Graffi
  Unpublished 2020, eprint, AIVG20

• Communication Computation Trade-offs in PIR
  Asra Ali, Tancrède Lepoint, Sarvar Patel, Mariana Raykova, Phillipp Schoppmann, Karn Seth, Kevin Yeo
  Usenix Security 2019, eprint, ALPR+19

• PIR with Compressed Queries and Amortized Query Processing
  Sebastian Angel, Hao Chen, Kim Laine, Srinath T. V. Setty
  SP 2018, eprint, ACLS+18

• Private Stateful Information Retrieval
  Sarvar Patel, Giuseppe Persiano, Kevin Yeo
  CCS 2018, eprint, PPY18

• Can We Access a Database Both Locally and Privately?
  Elette Boyle, Yuval Ishai, Rafael Pass, Mary Wootters
  TCC 2017, eprint, BIPW17

• Towards Doubly Efficient Private Information Retrieval
  Ran Canetti, Justin Holmgren, Silas Richelson
  TCC 2017, eprint, CHR17

• XPIR : Private Information Retrieval for Everyone
  Carlos Aguilar Melchor, Joris Barrier, Laurent Fousse, Marc-Olivier Killijian
  PETS 2016, eprint, MBFK16

• Optimal Rate Private Information Retrieval from Homomorphic Encryption
  Aggelos Kiayias, Nikos Leonardos, Helger Lipmaa, Kateryna Pavlyk, Qiang Tang
  PETS 2015, eprint, KLLP+15

• First CPIR Protocol with Data-Dependent Computation
  Helger Lipmaa
  ICISC 2009, eprint, LIP09

• An Oblivious Transfer Protocol with Log-Squared Communication
  Helger Lipmaa
  ISC 2005, eprint, LIP05

• Single-Database Private Information Retrieval with Constant Communication Rate
  Craig Gentry, Zulfikar Ramzan
  ICALP 2005, eprint, GR05

• A New Efficient All-Or-Nothing Disclosure of Secrets Protocol
  Julien P. Stern
  AsiaCrypt 1998, eprint, Stern98

• Replication is NOT needed: SINGLE database, computationally- private information retrieval
  Eyal Kushilevitz, Rafail Ostrovsky
  FOCS 1997, eprint, KO97

PFE

• Linear-Complexity Private Function Evaluation is Practical
  Marco Holz, Ágnes Kiss, Deevashwer Rathee, Thomas Schneider
  ESORICS 2020, eprint, HKRS20

• An Efficient 2-Party Private Function Evaluation Protocol Based on Half Gates
  Muhammed Ali Bingöl, Osman Biçer, Mehmet Sabir Kiraz, Albert Levi
  Comput. J 2019, eprint, BBKL19

• Highly Efficient and Reusable Private Function Evaluation with Linear Complexity
  Osman Biçer, Muhammed Ali Bingöl, Mehmet Sabir Kiraz
  Unpublished 2018, eprint, BBKL18

• Actively Secure Private Function Evaluation
  Payman Mohassel, Seyed Saeed Sadeghian, Nigel P. Smart
  AsiaCrypt 2014, eprint, MSS14

• How to Hide Circuits in MPC: An Efficient Framework for Private Function Evaluation
  Payman Mohassel, Seyed Saeed Sadeghian
  EuroCrypt 2013, eprint, MS13

• Constant-round private function evaluation with linear complexity
  Jonathan Katz, Lior Malka
  AsiaCrypt 2011, eprint, KM11

• Bureaucratic protocols for secure two-party sorting, selection, and permuting
  Guan Wang, Tongbo Luo, Michael T. Goodrich, Wenliang Du, Zutao Zhu
  AsiaCCS 2010, eprint, WLGD+10

• Selective private function evaluation with applications to private statistics
  Ran Canetti, Yuval Ishai, Ravi Kumar, Michael K. Reiter, Ronitt Rubinfeld, Rebecca N. Wright
  PODC 2001, eprint, CIKR+01

FSS

• 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, GI19

Semi-honest MPC

• 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 MPC

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

• MonZa2k: Fast Maliciously Secure Two Party Computation on Z_{2^k}
  Dario Catalano, Mario Di Raimondo, Dario Fiore, Irene Giacomelli
  PKC 2020, eprint, CRFG20

• Overdrive2k: Efficient Secure MPC over $Z_{2^k}$ from Somewhat Homomorphic Encryption
  Emmanuela Orsini, Nigel P. Smart, Frederik Vercauteren
  CT-RSA 2020, eprint, OSVJ19

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

• Using TopGear in Overdrive: A more efficient ZKPoK for SPDZ
  Carsten Baum, Daniele Cozzo, Nigel P. Smart
  SAC 2019, eprint, BCS19

• SPDZ2k: Efficient MPC MOD 2k for dishonest majority
  Ronald Cramer, Ivan Damgård, Daniel Escudero, Peter Scholl, Chaoping Xing
  Crypto 2018, eprint, SDES+18

• Overdrive: Making SPDZ great again
  Marcel Keller, Valerio Pastro, Dragos Rotaru
  EuroCrypt 2018, eprint, KPR18

• High-throughput secure three-party computation for malicious adversaries and an honest majority
  Jun Furukawa, Yehuda Lindell, Ariel Nof, Or Weinstein
  EuroCrypt 2017, eprint, FLNW17

• MASCOT: Faster Malicious Arithmetic Secure Computation with Oblivious Transfer
  Marcel Keller, Emmanuela Orsini, Peter Scholl
  CCS 2016, eprint, KOS16

• A New Approach to Practical Active-Secure Two-Party Computation
  Jesper Buus Nielsen, Peter Sebastian Nordholt, Claudio Orlandi, Sai Sheshank Burra
  Crypto 2012, eprint, NNOB12

Lattice

Summaries and Talks

• Crypto Innovation School 2019, link

HE

• Homomorphic Encryption for Arithmetic of Approximate Numbers
  Jung Hee Cheon, Andrey Kim, Miran Kim, Yong Soo Song
  AsiaCrypt 2017, eprint, CKKS17

• Homomorphic Encryption from Learning with Errors: Conceptually-Simpler, Asymptotically-Faster, Attribute-Based
  Craig Gentry, Amit Sahai, Brent Waters
  Crypto 2013, eprint, GSW13

• Somewhat Practical Fully Homomorphic Encryption
  Junfeng Fan, Frederik Vercauteren
  Unpublished 2012, eprint, BFV12

• Fully Homomorphic Encryption without Bootstrapping
  Zvika Brakerski, Craig Gentry, Vinod Vaikuntanathan
  Electron. Colloquium Comput. Complex. eprint, BGV11

• Computing Arbitrary Functions of Encrypted Data
  Craig Gentry
  Commun. ACM 2009, eprint, Gen09