Multi-Protocol SPDZ

This is a software to benchmark various secure multi-party computation (MPC) protocols in a variety of security models such as honest and dishonest majority, semi-honest/passive and malicious/active corruption. The underlying technologies span secret sharing, homomorphic encryption, and garbled circuits.

Frequently Asked Questions

The documentation contains section on a number of frequently asked topics as well as information on how to solve common issues.

Contact

Filing an issue on GitHub is the preferred way of contacting us, but you can also write an email to mp-spdz@googlegroups.com (archive). Before reporting a problem, please check against the list of known issues and possible solutions.

Filing Issues

Please file complete code examples because it's usually not possible to reproduce problems from incomplete code, and please include which protocol you have used (if applicable) because there are considerable differences between the various protocols.

Paper and Citation

The design of MP-SPDZ is described in this paper. If you use it for an academic project, please cite:

@inproceedings{mp-spdz,
    author = {Marcel Keller},
    title = {{MP-SPDZ}: A Versatile Framework for Multi-Party Computation},
    booktitle = {Proceedings of the 2020 ACM SIGSAC Conference on
    Computer and Communications Security},
    year = {2020},
    doi = {10.1145/3372297.3417872},
    url = {https://doi.org/10.1145/3372297.3417872},
}

TL;DR (Binary Distribution on Linux or Source Distribution on macOS)

This requires either a Linux distribution originally released 2019 or later (glibc 2.28) or macOS High Sierra or later as well as Python 3 and basic command-line utilities. On macOS, we recommend downloading directly from GitHub due to the use of git for dependencies (see next section).

Download and unpack the distribution, then execute the following from the top folder:

Scripts/tldr.sh
echo 1 2 3 4 > Player-Data/Input-P0-0
echo 1 2 3 4 > Player-Data/Input-P1-0
Scripts/compile-run.py -E mascot tutorial

This runs the tutorial with two parties and malicious security.

TL;DR (Source from GitHub)

You need to have Git in order to clone the repository.

On Linux, this requires a working toolchain and all requirements. On Ubuntu, the following might suffice:

sudo apt-get install automake build-essential clang cmake git libboost-dev libboost-filesystem-dev libboost-iostreams-dev libboost-thread-dev libgmp-dev libntl-dev libsodium-dev libssl-dev libtool python3

On MacOS, this requires High Sierra or later. It uses brew to install the required dependencies. You will be offered an automatic download if it is not found.

The following will execute the tutorial with two parties and malicious security.

make setup
echo 1 2 3 4 > Player-Data/Input-P0-0
echo 1 2 3 4 > Player-Data/Input-P1-0
Scripts/compile-run.py mascot tutorial

On strong enough hardware setups (several cores and GB of RAM), you can speed up the last step by running make -j8 mascot-party.x beforehand.

TL;DR (Docker)

Build a docker image for mascot-party.x:

docker build --tag mpspdz:mascot-party --build-arg machine=mascot-party.x .

Run the the tutorial:

docker run --rm -it mpspdz:mascot-party ./Scripts/compile-run.py mascot tutorial

See the Dockerfile for examples of how it can be used.

Relevant papers

The protocols in MP-SPDZ are based on numerous papers, and many computations will rely on several, ranging from the most basic building blocks to higher-level protocols making use of the building blocks in a black-box manner. You can have the compiler output links to relevant reading with the option --paper. Use either of the following:

./compile.py --papers -E <protocol> <program>
Scripts/compile-run.py --papers <protocol> <program>

You can find a more systematic overview in the documentation.

Preface

The primary aim of this software is to run the same computation in various protocols in order to compare the performance. All protocols in the matrix below are fully implemented. However, this does not mean that the software has undergone a security review as should be done with critical production code.

Protocols

The following table lists all protocols that are fully supported.

Security model	Mod prime / GF(2^n)	Mod 2^k	Bin. SS	Garbling
Malicious, dishonest majority	MASCOT / LowGear / HighGear	SPDZ2k	Tiny / Tinier	BMR
Covert, dishonest majority	CowGear / ChaiGear	N/A	N/A	N/A
Semi-honest, dishonest majority	Semi / Hemi / Temi / Soho	Semi2k	SemiBin	Yao's GC / BMR
Malicious, honest majority	Shamir / Rep3 / PS / SY / Rep4	Brain / Rep3 / PS / SY / Rep4	Rep3 / CCD / PS / Rep4	BMR
Semi-honest, honest majority	Shamir / ATLAS / Rep3	Rep3 / Astra / Trio	Rep3 / CCD	BMR
Malicious, honest supermajority	Rep4	Rep4	Rep4	N/A
Semi-honest, dealer	Dealer	Dealer	Dealer	N/A

Modulo prime and modulo 2^k are the two settings that allow integer-like computation. For k = 64, the latter corresponds to the computation available on the widely used 64-bit processors. GF(2^n) denotes Galois extension fields of order 2^n, which are different to computation modulo 2^n. In particular, every element has an inverse, which is not the case modulo 2^n. See this article for an introduction. Modulo prime and GF(2^n) are lumped together because the protocols are very similar due to the mathematical properties.

Bin. SS stands for binary secret sharing, that is secret sharing modulo two. In some settings, this requires specific protocols as some protocols require the domain size to be larger than two. In other settings, the protocol is the same mathematically speaking, but a specific implementation allows for optimizations such as using the inherent parallelism of bit-wise operations on machine words.

A security model specifies how many parties are "allowed" to misbehave in what sense. Malicious means that not following the protocol will at least be detected while semi-honest means that even corrupted parties are assumed to follow the protocol. See this paper for an explanation of the various security models and a high-level introduction to multi-party computation.

Finding the most efficient protocol

Lower security requirements generally allow for more efficient protocols. Within the same security model (line in the table above), there are a few things to consider:

• Computation domain: Arithmetic protocols (modulo prime or power of two) are preferable for many applications because they offer integer addition and multiplication at low cost. However, binary circuits might be a better option if there is very little integer computation. See below to find the most efficient mixed-circuit variant. Furthermore, local computation modulo a power of two is cheaper, but MP-SPDZ does not offer this domain with homomorphic encryption.

• Secret sharing vs garbled circuits: Computation using secret sharing requires a number of communication rounds that grows depending on the computation, which is not the case for garbled circuits. However, the cost of integer computation as a binary circuit often offset this. MP-SPDZ only offers garbled circuit with binary computation.

• Underlying technology for dishonest majority: While secret sharing alone suffice honest-majority computation, dishonest majority requires either homomorphic encryption (HE) or oblivious transfer (OT). The two options offer a computation-communication trade-off: While OT is easier to compute, HE requires less communication. Furthermore, the latter requires a certain of batching to be efficient, which makes OT preferable for smaller tasks.

• Malicious, honest-majority three-party computation: A number of protocols are available for this setting, but SY/SPDZ-wise is the most efficient one for a number of reasons: It requires the lowest communication, and it is the only one offering constant-communication dot products.

• Fixed-point multiplication: Three- and four-party replicated secret sharing as well semi-honest full-threshold protocols allow a special probabilistic truncation protocol (see Dalskov et al. and Dalskov et al.). You can activate it by adding program.use_trunc_pr = True at the beginning of your high-level program.

• Larger number of parties: ATLAS scales better than the plain Shamir protocol, and Temi scale better than Hemi or Semi.

• Minor variants: Some command-line options change aspects of the protocols such as:

  • --bucket-size: In some malicious binary computation and malicious edaBit generation, a smaller bucket size allows preprocessing in smaller batches at a higher asymptotic cost.
  • --batch-size: Preprocessing in smaller batches avoids generating too much but larger batches save communication rounds.
  • --direct: In protocols with any number of parties, direct communication instead of star-shaped saves communication rounds at the expense of a quadratic amount. This might be beneficial with a small number of parties.
  • --bits-from-squares: In some protocols computing modulo a prime (Shamir, Rep3, SPDZ-wise), this switches from generating random bits via XOR of parties' inputs to generation using the root of a random square.

History

The software started out as an implementation of the improved SPDZ protocol. The name SPDZ is derived from the authors of the original protocol.

This repository combines the functionality previously published in the following repositories: - https://github.com/bristolcrypto/SPDZ-2 - https://github.com/mkskeller/SPDZ-BMR-ORAM - https://github.com/mkskeller/SPDZ-Yao

Overview

For the actual computation, the software implements a virtual machine that executes programs in a specific bytecode. Such code can be generated from high-level Python code using a compiler that optimizes the computation with a particular focus on minimizing the number of communication rounds (for protocols based on secret sharing) or on AES-NI pipelining (for garbled circuits).

The software uses two different bytecode sets, one for arithmetic circuits and one for boolean circuits. The high-level code differs between the two variants. Most computation functionality is available in both, but binary circuits are lacking some input-output functionality.

In the section on computation we will explain how to compile a high-level program for the various computation domains and then how to run it with different protocols.

The section on offline phases will explain how to benchmark the offline phases required for the SPDZ protocol. Running the online phase outputs the amount of offline material required, which allows to compute the preprocessing time for a particular computation.

Requirements

• GCC 11 or later (tested with up to 15) or LLVM/clang 11 or later (tested with up to 22). The default is to use clang because it performs better.
• For protocols using oblivious transfer, libOTe with the necessary patches but without SimplestOT. The easiest way is to run make libote, which will install it as needed in a subdirectory. libOTe requires CMake of version at least 3.15, which is not available by default on older systems such as Ubuntu 18.04. You can run make cmake to install it locally. libOTe also requires boost of version at least 1.75, which is not available by default on relatively recent systems such as Ubuntu 22.04. You can install it locally by running make boost.
• GMP library, compiled with C++ support (use flag --enable-cxx when running configure). Tested against 6.2.1 as supplied by Ubuntu.
• libsodium library, tested against 1.0.18
• OpenSSL, tested against 3.0.2
• Boost.Asio with SSL support (libboost-dev on Ubuntu), tested against 1.83
• Boost.Thread for BMR (`libboost-th