(TBD)Secure Multipart Computing
安全多方计算(sd04630460)
Instructor: Zengpeng Li and Hong-Sheng Zhou
淦昌苑D座(K4)403
Course coordinator: Puwen Wei
淦昌苑D座(K4)319
Course Syllabus
This course will cover topics in secure mult-party computation.
-
Models of Secure Computation: Honest vs. Dishonest majority settings, semi-honest vs active(malicious) adversary, static vs. adaptive computation, computational vs. information theoretic security, synchronous vs. asynchronous network...
-
Defining Secure Computation: Computational/statistical Indistinguishability, Real-Ideal World or Simulation-based Security notions.
-
Secure computation with semi-honest security: Honest-majority Setting: Secret Sharing, BenOr-Goldwasser-Wigderson (BGW) Construction, Optimizations (MPC in preprocessing mode and circuit randomization), Cramer-Damgaard-Neilsen (CDN) Construction. Dishonest majority Setting: Oblivious Transfers (OT), two-party Goldreich-Micali-Wigderson (GMW) construction, Optimizations of GMW (Random input OT and OT extension), Yao construction, BMR construction and multi-party GMW construction.
-
Secure computation with Active security: Honest Majority Setting. Verifiable Secret Sharing, BGW Construction with active security, Hyper-invertible Matrices and Beerliova-Hirt (BH) Construction, Information Checking Protocol. Dishonest majority Setting: Commitment Schemes, Zero-knowledge, GMW Compiler for active corruption, Cut-and-Choose OT and Lindell-Pinkas Construction.
-
Practical Secure Computation: Secure Set Intersection, Privacy Preserving Biometrics & Genomics, Secure Cloud Computing
Grading:
Homeworks and a final large homework.
Schedule of Courses and Presentation Materials
Please note: The references below are chosen for pedagogical
reasons, not historical ones. Also, the scribe notes have for the most
part not been edited by me, and may contain errors. Most of scribe notes are from Jonathan Katz.
- [March XX: Lecture 1-1]
Introduction. Computational indistinguishability.
Defining secure multi-party computation in the semi-honest setting.
References:
- [March XX: Lecture 1-2]
Defining secure multi-party computation in the semi-honest setting.
Real worlds, ideal worlds, and hybrid worlds. Composition.
References:
Definitions of secure computation, and the composition theorem, are covered in Canetti
2000
scribe notes
- [March XX: Lecture 2-1]
Oblivious transfer (OT) in the semi-honest setting.
References:
Goldreich, vol. 2, Chapter 7, Naor-Pinkas 2001
scribe notes
Interesting Links:
Tung Chou and Claudio Orlandi. The Simplest Protocol for Oblivious Transfer
- [March XX: Lecture 2-2]
OT in the semi-honest setting, continued. 1-out-of-N OT.
References: Peikert et al. 2008, Naor-Pinkas 2005
scribe notes
- [April XX: Lecture 2-3]
OT extension.
References: Ishai et al. (OT extension),
scribe notes
(Note: the protocol in Section 1.1 is only secure if a single instance
of the online phase is run per instance of the pre-processing phase.)
OT extension lib
Interesting Links: Yehuda Lindell et al. 2013
Peter Scholl 2020
Arpita Patra
Emmanuela Orsini and Peter Scholl
- [April XX: Lecture 3-1]
The GMW protocol. Proof of security for the GMW protocol. Yao's garbled-circuit approach.
References:
Goldreich, vol. 2, Chapter 7 (the GMW protocol),
Goldreich, vol. 2, Chapter 7,
Lindell-Pinkas 2009
scribe notes
- [April XX: Lecture 3-2]
Optimizations (and implementations) of garbled circuits.
References: Kolesnikov-Schneider 2008,
PSSW09,
Bellare et al. #1,
#2, and
#3,
Asharov et al. 2013
scribe notes
- [April XX: Lecture 3-3]
Implementations of semi-honest secure two-party computation.
References:
Fairplay, TASTY (see also here),
Huang et al. 2011, Choi et al., Schneider-Zohner 2013
scribe notes
- [May XX: Lecture 4-1]
Beaver Triple Based-Protocols. ABY Secret Sharing. SPDZ Sharing.
References:
scribe notes
- [May XX: Lecture 9]
Secure computation using FHE. Oblivious RAM, and secure computation in the RAM model of computation.
References: Goldreich-Ostrovsky '96 (link only works within UMD), Gordon et al.
scribe notes
- [May XX: Lecture 10]
Sublinear-time secure computation. "Special-purpose" protocols. Private set intersection.
References:
Freedman et al. 2004,
Huang et al. 2012
scribe notes
- [May XX: Lecture 11]
Semi-honest multi-party computation. Information-theoretic security.
References:
Goldreich, vol. 2, Chapter 7, Asharov-Lindell,
Cramer et al., Chapter 3
scribe notes
- [May XX: Lecture 12]
The BGW protocol in the semi-honest setting, continued.
Multi-party computation in constant rounds (the Beaver-Micali-Rogaway protocol).
References: Rogaway's thesis
scribe notes
- [June XX: Lecture 13]
Implementations of multi-party computation with semi-honest security. Defining malicious security.
References:
- Implementations: FairplayMP, SecureSCM, sugar-beet auction, SEPIA, Sharemind, VIFF, MPC for financial-data analysis, Choi et al.
- Definitions of malicious security: Canetti 2000, Goldreich, vol. 2, Chapter 7, Lindell-Pinkas 2008
scribe notes
- [June XX: Lecture 14]
Zero-knowledge proofs/arguments. A zero-knowledge proof of Hamiltonicity.
References: Goldreich's survey
scribe notes
- [June XX: Lecture 15]
Sequential vs. parallel composition of ZK proofs. Proofs of knowledge.
References: Lecture notes from grad cryptography class (note: sometimes buggy)
scribe notes
- [June XX: Lecture 16]
Witness indistinguishability. A constant-round ZK argument of knowledge.
Constant-round two-party coin-tossing with malicious security.
References: Feige-Shamir, grad crypto scribe notes, Lecture 24, Goldreich, vol. 2, Chapter 7, Lindell 2003
scribe notes
- [June XX: Lecture 17]
Using zero knowledge for secure multi-party computation (with abort) in the malicious setting (assuming broadcast).
References: Goldreich, vol. 2, Chapter 7, Lindell 2003
scribe notes
- [June XX: Lecture 18]
Protocols for broadcast/Byzantine agreement.
References: Lecture 26, Notes on Byzantine agreement
- [June XX: Lecture 19]
Fully secure computation with honest majority.
References: Goldreich, vol. 2, Chapter 7
scribe notes
- [June XX: Lecture 20]
Cut-and-choose for efficient secure two-party computation.
References: Lindell-Pinkas 2007
- [June XX: Lecture 21]
Efficient two-party computation with 1-bit leakage.
References: Huang et al.
scribe notes
- [June XX: Lecture 22]
Knowledge inference for optimizing secure MPC.
References: Rastogi et al.
scribe notes
- [June XX: Lecture 23]
Covert security.
References: Aumann-Lindell, Asharov-Orlandi
scribe notes
- [June XX: Lecture 24]
Rational secret sharing and multi-party computation.
References: Gordon-Katz, Fuchsbauer et al., Groce-Katz
scribe notes
- [June XX: Lecture 25]
The BGW protocol in the malicious setting.
References: Asharov-Lindell
scribe notes
- [June XX: Lecture 26]
The BGW protocol in the malicious setting, continued.
scribe notes
- [June XX: Lecture 27]
Finish up BGW. More efficient cut-and-choose in the two-party setting.
References: Lindell 2013, Huang et al. 2013
- [June XX: Lecture 28]
Authenticated data structures, generically.
References: Miller et al.
- [June XX: Lecture 29]
The IPS compiler.
References: Ishai-Prabhakaran-Sahai, Lindell-Pinkas-Oxman
- [June XX: Lecture 30]
(Efficient) zero knowledge from secure computation.
References: Ishai et al., Jawurek et al.
- [June XX: Lecture 31]
The Damgard-Orlandi protocol for malicious MPC without honest majority.
References: Damgard-Orlandi (see also here for an implementation)
- [June XX: Lecture 32]
Universal composability. Impossibility in the plain model, and UC commitment in the CRS model.
References: Canetti 2001, Canetti 2006, Canetti-Fischlin, CLOS
- [June XX: Lecture 33]
UC two-party computation in the CRS model.
References: CLOS
- [June XX: Lecture 33]
Fairness without an honest majority.
References: Cleve 1986, Moran-Naor-Segev, Gordon-Katz
- [June XX: Lecture 34]
Impossibility results.
References: Goldreich-Oren, Goldreich-Krawczyk
- [Dec 13: Final exam (in class)]
-
Awesome-mpc, maintained by github: https://github.com/rdragos/awesome-mpc.
Useful Lectures and Scribe Notes
Some Resources for Getting Started with MPC are selected from Yehuda Lindell and Arpita Patra
Books
Books are always the best way to get started, since they provide a
holistic presentation of the field. The following books on MPC all teach
a different aspect, and are all helpful:
-
David Evans, Vladimir Kolesnikov and Mike Rosulek. A Pragmatic Introduction to Secure Multi-Party Computation,
NOW Publishers, 2018. This short book contains a friendly introduction
and comprehensive survey of techniques for achieving efficient secure
computation. The book does not go into details regarding each technique
and does not provide proofs. However, it gives a fantastic overview and
pointers to where you can find all of the details. As such, it is an
invaluable resource. Refer to Pragmatic MPC.
-
Ronald Cramer, Ivan Damgård and Jesper Buus Nielsen. Secure Multiparty Computation and Secret Sharing,
Cambridge University Press, 2015. This book includes definitions,
constructions for both the computational and information theoretic
settings, techniques for efficiency, and more. This is the most
comprehensive treatment of the basics of MPC, and I recommend reading it
methodically from the beginning.
-
Carmit Hazay and Yehuda Lindell. Efficient Secure Two-Party Protocols: Techniques and Constructions,
Springer, 2010. This book focuses specifically on the two-party case
and efficiency. It includes definitions, general constructions based on
the garbled circuit technique, and chapters on specific tools like
oblivious transfer, sigma protocols, and more. The specific techniques
for general constructions are outdated (with must faster techniques
available today), but the text is very relevant for study and includes
basic results like a full proof of the security of Yao's garbled
circuits construction.
-
Oded Goldreich. Foundations of Cryptography Vol. 2,
Cambridge University Press, 2004. Chapter 7 of the book introduces
two-party and multiparty computation, contains a thorough and
comprehensive definitional treatment, provides a full and detailed proof
of the GMW construction, and surveys advanced topics. The book's formal
and rigorous treatment makes it a must-read for the MPC researcher.
-
Thomas Schneider. Engineering Secure Two-Party Computation Protocols,
Springer, 2012. This book focuses specifically tools for optimizing
secure computation in practice, including circuit optimizations,
frameworks for constructing protocols, and more. The book provides a
very good overview of different techniques and tools that MPC
researchers should be familiar with.
-
Mahdi Zamani and Mahnush Movahedi, Reference on Cryptography, including Notions of Security (e.g., rushing adversary)
-
Ittai Abraham. Decentralized Thoughts
The power of the adversary.
-
Survey Papers
-
Marcella Hastings, Brett Hemenway, Daniel Noble, and Steve Zdancewic. SoK: General Purpose Compilers for Secure
Multi-Party Computation ,
- Yehuda Lindell. Secure Multiparty Computation (MPC),
Communications of the ACM, January 2021. This is a general and friendly
introduction to secure multiparty computation - what it is, how it
works, and what it is used for.
-
Yehuda Lindell. How to Simulate It - A Tutorial on the Simulation Proof Technique,
2016. The simulation paradigm is fundamental to secure computation.
However, many have difficulties in understanding how to write simulation
proofs. This tutorial explains this proof technique in great detail.
-
Manoj Prabhakaran and Amit Sahai (Eds.). Secure Multi-Party Computation,
IOS Press, 2013. This is a compilation of surveys on the topic of
multiparty computation. It focuses on theoretical aspects and is highly
useful for those wishing to study the theory of MPC.
-
Ran Cannitte. Universally Composable Security:
A New Paradigm for Cryptographic Protocols.
Useful Resources on MPC
Video Tutorials
Videos are often a more friendly way of getting started in the field.
There are many talks that you can find online.