A Pragmatic Introduction to Secure Multi-Party Computation

A Pragmatic Introduction to
Secure Multi-Party Computation

David Evans, Vladimir Kolesnikov and Mike Rosulek

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 book 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.

NOW Publishers, December 2018: Publishers Page

Full Text (PDF) (Last update: 11 June 2022; Errata) (scroll down for links to PDFs of individual chapters)

News

May 2022: Lúcás Meier includes Pragmatic MPC in his list of Some Cryptography Books I Like:

I read this one quite recently, and I’d highly recommend it. ... I highly recommend this book if you’re interested in MPC. It’s also a short read, so if you’re not interested in MPC, you should still give it a look, and you might change that.

June 2021: A Chinese translation of the book is now available from China Machine Press!

Thanks to Weiran Liu and Sengchao Ding for all the work they did on the translation (which also substantially improve the English version with all the mistakes they found in their careful translation work).

To order: JD.com book link

January 2021: For a quick introduction to MPC, read Yehuda Lindell’s article: Secure Multiparty Computation (Communications of the ACM, January 2021). There’s even a movie:

Contents

1 Introduction [PDF]
1.1 Outsourced Computation
1.2 Multi-Party Computation
1.3 MPC Applications
1.4 Overview
2 Defining Multi-Party Computation [PDF]
2.1 Notations and Conventions
2.2 Basic Primitives
2.3 Security of Multi-Party Computation
2.4 Specific Functionalities of Interest
2.5 Further Reading
3 Fundamental MPC Protocols [PDF]
3.1 Yao's Garbled Circuits Protocol
3.2 Goldreich-Micali-Wigderson (GMW) Protocol
3.3 BGW protocol
3.4 MPC From Preprocessed Multiplication Triples
3.5 Constant-Round Multi-Party Computation: BMR
3.6 Information-Theoretic Garbled Circuits
3.7 Oblivious Transfer
3.8 Custom Protocols
3.9 Further Reading
4 Implementation Techniques [PDF]
4.1 Less Expensive Garbling
4.2 Optimizing Circuits
4.3 Protocol Execution
4.4 Programming Tools
4.5 Further Reading
5 Oblivious Data Structures [PDF]
5.1 Tailored Oblivious Data Structures
5.2 RAM-Based MPC
5.3 Tree-Based RAM-MPC
5.4 Square-Root RAM-MPC
5.5 Floram
5.6 Further Reading
6 Malicious Security [PDF]
6.1 Cut-and-Choose
6.2 Input Recovery Technique
6.3 Batched Cut-and-Choose
6.4 Gate-level Cut-and-Choose: LEGO
6.5 Zero-Knowledge Proofs
6.6 Authenticated Secret Sharing: BDOZ and SPDZ
6.7 Authenticated Garbling
6.8 Further Reading
7 Alternative Threat Models [PDF]
7.1 Honest Majority
7.2 Asymmetric Trust
7.3 Covert Security
7.4 Publicly Verifiable Covert (PVC) Security
7.5 Reducing Communication in Cut-and-Choose Protocols
7.6 Trading Off Leakage for Efficiency
7.7 Further Reading
8 Conclusion [PDF]
References [PDF]

Adoptions

We are aware of parts of this book being used in the following courses:

Jonas Spenger has notes from an MPC study group that follows some parts of the book including Yao’s Garbled Circuits, BGW Protocol and Beaver Triples, Malicious BGW and SPDZ, GMW Protocol, Oblivious Transfer Extension, and more.

Boston University CS 791/JD 673 / UC Berkeley CS 294, Law for Algorithms
Ran Canetti (BU CS), Stacey Dogan (BU Law), Aloni Cohen (BU CS & Law), Shafi Goldwasser (UC Berkeley CS), Frank Partnoy (UC Berkeley Law)

Brown CS 2950, Topics in Applied Cryptography: Crypto for Social Good
Seny Kamara

EURECOM Spohis Antipolis, Multiparty Computation and Blockchains (Fall 2022)
Antonio Faonio

George Washington University GWU CSIC 3907-83/6907-81, Advanced Cryptography
Arkady Yerukhimovich

IT University of Copenhagen, Cryptographic Computation and Blockchain (Spring 2023)
Bernardo Machado David

Stanford CS 355, Topics in Cryptography
Saba Eskandarian, Dima Kogan, and Florian Tramèr

University of Bern and Swiss Joint Master in Computer Science, Cryptographic Protocols/Cryptographic Protocols
Christian Cachin

University of Maryland, CMSC 858T — Introduction to Secure Distributed Computation
Jonathan Katz

University of Missouri, CMP_SC 8001 — Wei Jiang has shared slides he developed for his course following the book:

University of Vermont, UVM CS 295/395: Secure Distributed Computation
Joe Near

If you know of other courses using the book, please let me know.

More Reading
Older// Welcome