Private Certifier Intersection
This repository contains the implementation of 'Private Certifier Intersection' protocols introduced in the paper: https://eprint.iacr.org/2022/1302 [NDSS 2023]
If you are using this codebase, please cite the following:
@inproceedings{ghosh2023pci,
title = {Private Certifier Intersection},
author = {Bishakh Chandra Ghosh and Sikhar Patranabis and Dhinakaran Vinayagamurthy and Venkatraman Ramakrishna and Krishnasuri Narayanam and Sandip Chakraborty},
booktitle={Network and Distributed System Security Symposium 2023 (NDSS 2023)},
year={2023}
}The implementation is based on the low level interface provided by MPSPDZ.
The MPSPDZ README is also appended below.
Build instructions
Install Prerequisites
These instructions are for Ubuntu 18.04 to 22.04.
Assuming a fresh EC2 instance with Ubuntu server, please install the following:
sudo apt update
sudo apt-get install automake build-essential git libboost-dev libboost-thread-dev libntl-dev libsodium-dev libssl-dev libtool m4 python3 texinfo yasm cmake libgmp-devInstall relic:
git clone git@github.com:relic-toolkit/relic.git
cd relic
# OPTIONAL: git checkout relic-toolkit-0.5.0
mkdir -p relic-target
cd relic-target
# For RELIC 0.5.0: ../preset/x64-pbc-bls381.sh ../
../preset/x64-pbc-bls12-381.sh ../
make -j 8
sudo make installBuild pci:
git clone https://github.com/ghoshbishakh/pci
cd pci
git checkout pci_final
make -j8 tldr
make bls -j 8
make ecdsa -j 8
make ecdsa-pciall -j 8Running benchmarks
BLS:
Run the two parties:
./mascot-bls-party.x -p 0 -I 10
./mascot-bls-party.x -p 1 -I 10
-p denotes player 0/1
-I specifies the size of the input set
To use different hosts, edit the pci_ip.txt file. Then add the additional option -ip pci_ip.txt to the above commands.
For ECDSA use the executable ./mascot-ecdsa-party.x
The changes are concentrated mostly in the two directories ecdsa and bls.
The Mult-G-S / Exp-GT-S protocol specific code is in Protocols directory. Compare the pci_final branch to the master branch of MPSPDZ to realize the changes.
Multi-Protocol SPDZ 
Software to benchmark various secure multi-party computation (MPC) protocols such as SPDZ, SPDZ2k, MASCOT, Overdrive, BMR garbled circuits, Yao's garbled circuits, and computation based on three-party replicated secret sharing as well as Shamir's secret sharing (with an honest majority).
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.
Frequently Asked Questions
The documentation contains sections on a number of frequently asked topics as well as information on how to solve common issues.
TL;DR (Binary Distribution on Linux or Source Distribution on macOS)
This requires either a Linux distribution originally released 2014 or later (glibc 2.17) or macOS High Sierra or later as well as Python 3 and basic command-line utilities.
Download and unpack the distribution, then execute the following from the top folder:
Scripts/tldr.sh
./compile.py tutorial
echo 1 2 3 4 > Player-Data/Input-P0-0
echo 1 2 3 4 > Player-Data/Input-P1-0
Scripts/mascot.sh tutorialThis runs the tutorial with two parties and malicious security.
TL;DR (Source Distribution)
On Linux, this requires a working toolchain and all requirements. On Ubuntu, the following might suffice:
sudo apt-get install automake build-essential git libboost-dev libboost-thread-dev libntl-dev libsodium-dev libssl-dev libtool m4 python3 texinfo yasmOn MacOS, this requires brew to be installed, which will be used for all dependencies. It will execute the tutorial with two parties and malicious security.
Note that this only works with a git clone but not with a binary release.
make -j 8 tldr
./compile.py tutorial
echo 1 2 3 4 > Player-Data/Input-P0-0
echo 1 2 3 4 > Player-Data/Input-P1-0
Scripts/mascot.sh tutorialTL;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/mascot.sh tutorialSee the Dockerfile for examples of how it can be used.
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. In addition, there are further protocols implemented only partially, most notably the Overdrive protocols. They are deactivated by default in order to avoid confusion over security. See the section on compilation on how to activate them.
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 | Brain / Rep[34] / PS / SY | Rep3 / CCD / PS | BMR |
| Semi-honest, honest majority | Shamir / ATLAS / Rep3 | Rep3 | Rep3 / CCD | BMR |
| 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 = Trueat 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 dishonest-majority protocols, 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.
-
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},
}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
Alternatives
There is another fork of SPDZ-2 called SCALE-MAMBA. The main differences at the time of writing are as follows:
- It provides honest-majority computation for any Q2 structure.
- For dishonest majority computation, it provides integration of SPDZ/Overdrive offline and online phases but without secure key generation.
- It only provides computation modulo a prime.
- It only provides malicious security.
More information can be found here: https://homes.esat.kuleuven.be/~nsmart/SCALE
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 protocol 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 slightly differs between the two variants, but we aim to keep these differences a at minimum.
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 5 or later (tested with up to 11) or LLVM/clang 5 or later (tested with up to 12). We recommend clang because it performs better.
- MPIR library, compiled with C++ support (use flag
--enable-cxxwhen running configure). You can usemake -j8 tldrto install it locally. - libsodium library, tested against 1.0.18
- OpenSSL, tested against 1.1.1
- Boost.Asio with SSL support (
libboost-devon Ubuntu), tested against 1.71 - Boost.Thread for BMR (
libboost-thread-devon Ubuntu), tested against 1.71 - x86 or ARM 64-bit CPU (the latter tested with AWS Gravitron and Apple Silicon)
- Python 3.5 or later
- NTL library for homomorphic encryption (optional; tested with NTL 10.5)
- If using macOS, Sierra or later
Compilation
1) Edit CONFIG or CONFIG.mine to your needs:
- On x86, the binaries are optimized for the CPU you are
compiling on.
For all optimizations on x86, a CPU supporting AES-NI, PCLMUL, AVX2, BMI2, ADX is
required. This includes mainstream processors released 2014 or later.
If you intend to run on a different CPU than compiling, you might
need to change the
ARCHvariable inCONFIGorCONFIG.mineto-march=<cpu>. See the GCC documentation for the possible options. To run OT-based protocols on x86 without AVX, addAVX_OT = 0in addition. - For optimal results on Linux on ARM, add
ARCH = -march=-march=armv8.2-a+cryptotoCONFIG.mine. This enables the hardware support for AES. See the GCC documentation on available options. - To benchmark online-only protocols or Overdrive offline phases, add the following line at the top:
MY_CFLAGS = -DINSECURE PREP_DIRshould point to a local, unversioned directory to store preprocessing data (the default isPlayer-Datain the current directory).SSL_DIRshould point to a local, unversioned directory to store ssl keys (the default isPlayer-Datain the current directory).- For homomorphic encryption with GF(2^40), set
USE_NTL = 1.
2) Run make to compile all the software (use the flag -j for faster
compilation using multiple threads). See below on how to compile specific
parts only. Remember to run make clean first after changing CONFIG
or CONFIG.mine.
Running computation
See Programs/Source/ for some example MPC programs, in particular
tutorial.mpc. Furthermore, Read the
Docs hosts a more
detailed reference of the high-level functionality extracted from the
Python code in the Compiler directory as well as a summary of
relevant compiler options.
Compiling high-level programs
There are three computation domains, and the high-level programs have to be compiled accordingly.
Arithmetic modulo a prime
./compile.py [-F <integer bit length>] [-P <prime>] <program>
The integer bit length defaults to 64, and the prime defaults to none given. If a prime is given, it has to be at least two bits longer than the integer length.
Note that in this context integers do not wrap around according to the bit integer bit length but the length is used for non-linear computations such as comparison. Overflow in secret integers might have security implications if no concrete prime is given.
The parameters given together with the computation mandate some
restriction on the prime modulus, either an exact value or a minimum
length. The latter is roughly the integer length plus 40 (default
security parameter). The restrictions are communicated to the virtual
machines, which will use an appropriate prime if they have been
compiled accordingly. By default, they are compiled for prime bit
lengths up to 256. For larger primes, you will have to compile with
MOD = -DGFP_MOD_SZ=<number of limbs> in CONFIG.mine where the
number of limbs is the the prime length divided by 64 rounded up.
The precision for fixed- and floating-point computation are not
affected by the integer bit length but can be set in the code
directly. For fixed-point computation this is done via
sfix.set_precision().
Arithmetic modulo 2^k
./compile.py -R <integer bit length> <program>
The length is communicated to the virtual machines and automatically used if supported. By default, they support bit lengths 64, 72, and
- If another length is required, use
MOD = -DRING_SIZE=<bit length>inCONFIG.mine.
Binary circuits
./compile.py -B <integer bit length> <program>
The integer length can be any number up to a maximum depending on the protocol. All protocols support at least 64-bit integers.
Fixed-point numbers (sfix) always use 16/16-bit precision by default in
binary circuits. This can be changed with sfix.set_precision. See
the tutorial.
If you would like to use integers of various precisions, you can use
sbitint.get_type(n) to get a type for n-bit arithmetic.
Mixed circuits
MP-SPDZ allows to mix computation between arithmetic and binary secret sharing in the same security model. In the compiler, this is used to switch from arithmetic to binary computation for certain non-linear functions such as comparison, bit decomposition, truncation, and modulo power of two, which are use for fixed- and floating-point operations. There are several ways of achieving this as described below.
Classic daBits
You can activate this by adding -X when compiling arithmetic
circuits, that is
./compile.py -X [-F <integer bit length>] <program>
for computation modulo a prime and
./compile.py -X -R <integer bit length> <program>
for computation modulo 2^k.
Internally, this uses daBits described by Rotaru and Wood, that is secret random bits shared in different domains. Some security models allow direct conversion of random bits from arithmetic to binary while others require inputs from several parties followed by computing XOR and checking for malicious security as described by Rotaru and Wood in Section 4.1.
Extended daBits
Extended daBits were introduced by Escudero et
al.. You can activate them by using
-Y instead of -X. Note that this also activates classic daBits
when useful.
Local share conversion
This technique has been used by Mohassel and
Rindal as well as Araki et
al. for three parties and Demmler
et al. for two parties.
It involves locally
converting an arithmetic share to a set of binary shares, from which the
binary equivalent to the arithmetic share is reconstructed using a
binary adder. This requires additive secret sharing over a ring
without any MACs. You can activate it by using -Z <n> with the
compiler where n is the number of parties for the standard variant
and 2 for the special
variant by Mohassel and Rindal (available in Rep3 only).
Finding the most efficient variant
Where available, local share conversion is likely the most efficient
variant. Otherwise, edaBits likely offer an asymptotic benefit. When
using edaBits with malicious protocols, there is a trade-off between
cost per item and batch size. The lowest cost per item requires large
batches of edaBits (more than one million at once), which is only
worthwhile for accordingly large computation. This setting can be
selected by running the virtual machine with -B 3. For smaller
computation, try -B 4 or -B 5, which set the batch size to ~10,000
and ~1,000, respectively, at a higher asymptotic cost. -B 4 is the
default.
Bristol Fashion circuits
Bristol Fashion is the name of a description format of binary circuits
used by
SCALE-MAMBA. You can
access such circuits from the high-level language if they are present
in Programs/Circuits. To run the AES-128 circuit provided with
SCALE-MAMBA, you can run the following:
make Programs/Circuits
./compile.py aes_circuit
Scripts/semi.sh aes_circuitThis downloads the circuit, compiles it to MP-SPDZ bytecode, and runs
it as semi-honest two-party computation 1000 times in parallel. It
should then output the AES test vector
0x3ad77bb40d7a3660a89ecaf32466ef97. You can run it with any other
protocol as well.
See the documentation for further examples.
Compiling and running programs from external directories
Programs can also be edited, compiled and run from any directory with the above basic structure. So for a source file in ./Programs/Source/, all SPDZ scripts must be run from ./. The setup-online.sh script must also be run from ./ to create the relevant data. For example:
spdz$ cd ../
$ mkdir myprogs
$ cd myprogs
$ mkdir -p Programs/Source
$ vi Programs/Source/test.mpc
$ ../spdz/compile.py test.mpc
$ ls Programs/
Bytecode Public-Input Schedules Source
$ ../spdz/Scripts/setup-online.sh
$ ls
Player-Data Programs
$ ../spdz/Scripts/run-online.sh testTensorFlow inference
MP-SPDZ supports inference with selected TensorFlow graphs, in particular DenseNet, ResNet, and SqueezeNet as used in CrypTFlow. For example, you can run SqueezeNet inference for ImageNet as follows:
git clone https://github.com/mkskeller/EzPC
cd EzPC/Athos/Networks/SqueezeNetImgNet
axel -a -n 5 -c --output ./PreTrainedModel https://github.com/avoroshilov/tf-squeezenet/raw/master/sqz_full.mat
pip3 install scipy==1.1.0
python3 squeezenet_main.py --in ./SampleImages/n02109961_36.JPEG --saveTFMetadata True
python3 squeezenet_main.py --in ./SampleImages/n02109961_36.JPEG --scalingFac 12 --saveImgAndWtData True
cd ../../../..
Scripts/fixed-rep-to-float.py EzPC/Athos/Networks/SqueezeNetImgNet/SqNetImgNet_img_input.inp
./compile.py -R 64 tf EzPC/Athos/Networks/SqueezeNetImgNet/graphDef.bin 1 trunc_pr split
Scripts/ring.sh tf-EzPC_Athos_Networks_SqueezeNetImgNet_graphDef.bin-1-trunc_pr-splitThis requires TensorFlow and the axel command-line utility to be
installed. It runs inference with
three-party semi-honest computation, similar to CrypTFlow's
Porthos. Replace 1 by the desired number of thread in the last two
lines. If you run with any other protocol, you will need to remove
trunc_pr and split. Also note that you will need to use a
CrypTFlow repository that includes the patch in
https://github.com/mkskeller/EzPC/commit/2021be90d21dc26894be98f33cd10dd26769f479.
The reference contains further documentation on available layers.
Emulation
For arithmetic circuits modulo a power of two and binary circuits, you can emulate the computation as follows:
./emulate.x <program>
This runs the compiled bytecode in cleartext computation.
Dishonest majority
Some full implementations require oblivious transfer, which is
implemented as OT extension based on
https://github.com/mkskeller/SimpleOT or OpenSSL (activate the
latter with AVX_OT = 0 in CONFIG or CONFIG.mine).
Secret sharing
The following table shows all programs for dishonest-majority computation using secret sharing:
| Program | Protocol | Domain | Security | Script |
|---|---|---|---|---|
mascot-party.x |
MASCOT | Mod prime | Malicious | mascot.sh |
mama-party.x |
MASCOT* | Mod prime | Malicious | mama.sh |
spdz2k-party.x |
SPDZ2k | Mod 2^k | Malicious | spdz2k.sh |
semi-party.x |
OT-based | Mod prime | Semi-honest | semi.sh |
semi2k-party.x |
OT-based | Mod 2^k | Semi-honest | semi2k.sh |
lowgear-party.x |
LowGear | Mod prime | Malicious | lowgear.sh |
highgear-party.x |
HighGear | Mod prime | Malicious | highgear.sh |
cowgear-party.x |
Adapted LowGear | Mod prime | Covert | cowgear.sh |
chaigear-party.x |
Adapted HighGear | Mod prime | Covert | chaigear.sh |
hemi-party.x |
Semi-homomorphic encryption | Mod prime | Semi-honest | hemi.sh |
temi-party.x |
Adapted CDN01 | Mod prime | Semi-honest | temi.sh |
soho-party.x |
Somewhat homomorphic encryption | Mod prime | Semi-honest | soho.sh |
semi-bin-party.x |
OT-based | Binary | Semi-honest | semi-bin.sh |
tiny-party.x |
Adapted SPDZ2k | Binary | Malicious | tiny.sh |
tinier-party.x |
FKOS15 | Binary | Malicious | tinier.sh |
Mama denotes MASCOT with several MACs to increase the security
parameter to a multiple of the prime length. The number of MACs
defaults to three, and it is controlled by the N_MAMA_MACS
compile-time parameter (add MY_CFLAGS += -DN_MAMA_MACS=<number of MACs> to CONFIG.mine).
Semi and Semi2k denote the result of stripping MASCOT/SPDZ2k of all steps required for malicious security, namely amplifying, sacrificing, MAC generation, and OT correlation checks. What remains is the generation of additively shared Beaver triples using OT.
Similarly, SemiBin denotes a protocol that generates bit-wise multiplication triples using OT without any element of malicious security.
Tiny denotes the adaption of SPDZ2k to the binary setting. In particular, the SPDZ2k sacrifice does not work for bits, so we replace it by cut-and-choose according to Furukawa et al.
The virtual machines for LowGear and HighGear run a key generation
similar to the one by Rotaru et
al.. The main difference is using
daBits to generate maBits. CowGear and ChaiGear denote covertly
secure versions of LowGear and HighGear. In all relevant programs,
option -T activates TopGear
zero-knowledge proofs in both.
Hemi and Soho denote the stripped version version of LowGear and HighGear, respectively, for semi-honest security similar to Semi, that is, generating additively shared Beaver triples using semi-homomorphic encryption. Temi in turn denotes the adaption of Cramer et al. to LWE-based semi-homomorphic encryption. Both Hemi and Temi use the diagonal packing by Halevi and Shoup for matrix multiplication.
We will use MASCOT to demonstrate the use, but the other protocols work similarly.
First compile the virtual machine:
make -j8 mascot-party.x
and a high-level program, for example the tutorial (use -R 64 for
SPDZ2k and Semi2k and -B <precision> for SemiBin):
./compile.py -F 64 tutorial
To run the tutorial with two parties on one machine, run:
./mascot-party.x -N 2 -I -p 0 tutorial
./mascot-party.x -N 2 -I -p 1 tutorial (in a separate terminal)
Using -I activates interactive mode, which means that inputs are
solicited from standard input, and outputs are given to any
party. Omitting -I leads to inputs being read from
Player-Data/Input-P<party number>-0 in text format.
Or, you can use a script to do run two parties in non-interactive mode automatically:
Scripts/mascot.sh tutorial
To run a program on two different machines, mascot-party.x
needs to be passed the machine where the first party is running,
e.g. if this machine is name diffie on the local network:
./mascot-party.x -N 2 -h diffie 0 tutorial
./mascot-party.x -N 2 -h diffie 1 tutorial
The software uses TCP ports around 5000 by default, use the -pn
argument to change that.
Yao's garbled circuits
We use half-gate garbling as described by Zahur et
al. and Guo et
al.. Alternatively, you can
activate the implementation optimized by Bellare et
al. by adding MY_CFLAGS += -DFULL_GATES to CONFIG.mine.
Compile the virtual machine:
make -j 8 yao
and the high-level program:
./compile.py -B <integer bit length> <program>
Then run as follows:
- Garbler:
./yao-party.x [-I] -p 0 <program> - Evaluator:
./yao-party.x [-I] -p 1 -h <garbler host> <program>
When running locally, you can omit the host argument. As above, -I
activates interactive input, otherwise inputs are read from
Player-Data/Input-P<playerno>-0.
By default, the circuit is garbled in chunks that are evaluated
whenever received.You can activate garbling all at once by adding
-O to the command line on both sides.
Honest majority
The following table shows all programs for honest-majority computation:
| Program | Sharing | Domain | Malicious | # parties | Script |
|---|---|---|---|---|---|
replicated-ring-party.x |
Replicated | Mod 2^k | N | 3 | ring.sh |
brain-party.x |
Replicated | Mod 2^k | Y | 3 | brain.sh |
ps-rep-ring-party.x |
Replicated | Mod 2^k | Y | 3 | ps-rep-ring.sh |
malicious-rep-ring-party.x |
Replicated | Mod 2^k | Y | 3 | mal-rep-ring.sh |
sy-rep-ring-party.x |
SPDZ-wise replicated | Mod 2^k | Y | 3 | sy-rep-ring.sh |
rep4-ring-party.x |
Replicated | Mod 2^k | Y | 4 | rep4-ring.sh |
replicated-bin-party.x |
Replicated | Binary | N | 3 | replicated.sh |
malicious-rep-bin-party.x |
Replicated | Binary | Y | 3 | mal-rep-bin.sh |
ps-rep-bin-party.x |
Replicated | Binary | Y | 3 | ps-rep-bin.sh |
replicated-field-party.x |
Replicated | Mod prime | N | 3 | rep-field.sh |
ps-rep-field-party.x |
Replicated | Mod prime | Y | 3 | ps-rep-field.sh |
sy-rep-field-party.x |
SPDZ-wise replicated | Mod prime | Y | 3 | sy-rep-field.sh |
malicious-rep-field-party.x |
Replicated | Mod prime | Y | 3 | mal-rep-field.sh |
atlas-party.x |
ATLAS | Mod prime | N | 3 or more | atlas.sh |
shamir-party.x |
Shamir | Mod prime | N | 3 or more | shamir.sh |
malicious-shamir-party.x |
Shamir | Mod prime | Y | 3 or more | mal-shamir.sh |
sy-shamir-party.x |
SPDZ-wise Shamir | Mod prime | Y | 3 or more | sy-shamir.sh |
ccd-party.x |
CCD/Shamir | Binary | N | 3 or more | ccd.sh |
malicious-cdd-party.x |
CCD/Shamir | Binary | Y | 3 or more | mal-ccd.sh |
We use the "generate random triple optimistically/sacrifice/Beaver"
methodology described by Lindell and
Nof to achieve malicious
security with plain arithmetic replicated secret sharing,
except for the "PS" (post-sacrifice) protocols where the
actual multiplication is executed optimistically and checked later as
also described by Lindell and Nof.
The implementations used by brain-party.x,
malicious-rep-ring-party.x -S, malicious-rep-ring-party.x,
and ps-rep-ring-party.x correspond to the protocols called DOS18
preprocessing (single), ABF+17 preprocessing, CDE+18 preprocessing,
and postprocessing, respectively,
by Eerikson et al.
We use resharing by Cramer et
al. for Shamir's secret sharing and
the optimized approach by Araki et
al. for replicated secret sharing.
The CCD protocols are named after the historic
paper by Chaum, Crépeau, and
Damgård, which introduced binary computation using Shamir secret
sharing over extension fields of characteristic two.
SY/SPDZ-wise refers to the line of work started by Chida et
al. for computation modulo a prime
and furthered by Abspoel et al.
for computation modulo a power of two. It involves sharing both a
secret value and information-theoretic tag similar to SPDZ but not
with additive secret sharing, hence the name.
Rep4 refers to the four-party protocol by Dalskov et
al..
malicious-rep-bin-party.x is based on cut-and-choose triple
generation by Furukawa et al. but
using Beaver multiplication instead of their post-sacrifice
approach. ps-rep-bin-party.x is based on the post-sacrifice approach
by Araki et
al. but
without using their cache optimization.
All protocols in this section require encrypted channels because the information received by the honest majority suffices the reconstruct all secrets. Therefore, an eavesdropper on the network could learn all information.
MP-SPDZ uses OpenSSL for secure channels. You can generate the necessary certificates and keys as follows:
Scripts/setup-ssl.sh [<number of parties> <ssl_dir>]
The programs expect the keys and certificates to be in
SSL_DIR/P<i>.key and SSL_DIR/P<i>.pem, respectively, and
the certificates to have the common name P<i> for player
<i>. Furthermore, the relevant root certificates have to be in
SSL_DIR such that OpenSSL can find them (run `c_rehash