-
Notifications
You must be signed in to change notification settings - Fork 112
EMP toolkit
This is an extensive library that implements a series of secure computation protocols designed by Xiao Wang & coathors that are based on garbled circuits. These protocols span multiple papers and settings, including:
- 2-party setting, malicious adversary, some pre-processing
- 2-party setting, malicious adversaries, single-execution (no amortization or pre-processing)
- multi-party setting, arbitrary malicious actors, constant rounds in a global setting
- 2-party setting, semi-honest adversary
- 2-party setting, malicious setting with input validation
The library also includes an oblivious transfer implementation.
Shares can optionally be XOR, but they're something else by default.
Threshold: This only applies to the multiparty framework (agmpc). The garbled circuit output labels are represented as secret shares among the garbling parties. The current default behavior returns all the final output shares to one output party, but could easily update to pass the shares to a threshold number of parties.
I'm not sure what sharing scheme is used, though.
The framework comes with installation scripts that we mostly used as-is. We weren't able to compile on OSX, but it worked fine on Ubuntu.
We deviate slightly from the recommended build procedure given in the original repositories. We make a build repository for cmake output, which is easier to clean up after. See install.sh for details. The generated binaries will be in build/bin.
New examples need to be added to the cmake system.
$ vim test/my_secure_computation.cpp
... write code ...
$ echo "add_test (my_secure_computation)" >> CMakeLists.txt
$ cd build
$ cmake ..
$ make my_secure_computation
The executable will be in build/bin. If you make changes, you can simply run
$ make my_test_name
Arbitrary length integers are an option! You can input large values as strings, but there isn't a matching way to output. You can output bit-by-bit using a binary array. The library provides handy tools for converting a binary string to a decimal string (see bin_to_dec in utils.hpp)
We found two user-caused correctness issue. (1) the reveal function requires both parties to run it in order to complete.
if (party == ALICE) {
cout << a.reveal<int> << endl;
}
(2) The reveal function also doesn't verify that the two parties are revealing the same thing. This is possible using party-based conditional behavior, though the output isn't garbage. It's -1 for all parties.
if (party == ALICE) {
cout << a.reveal<int> << endl;
cout << b.reveal<int> << endl;
}
if (party == BOB) {
cout << b.reveal<int> << endl;
cout << a.reveal<int> << endl;
}
You can reveal to a single party by adding them as a parameter.
Integer constructors' third argument is the party, but all the relevant code goes
if (party == ALICE) {
// do something
} else {
// do something else
}
So you can put any value for the third argument. Sometimes there's a separate branch for PUBLIC.
Additional variables need to be attributed to one party.
Each declared variable must belong to a single party. No sharing. This is perfectly reasonable, since all parties need to allocate space for their secret share of the value.
// Valid
Integer a(32, input, ALICE);
Integer b(32, input, BOB);
// Invalid:
Integer c(32, input, party);
We tested our sample programs in two settings: the semi-honest 2-party setting, and the maliciously secure 2-party setting. The latter uses circuits generated by the former, so the above notes don't change.
While secret shared inputs isn't a built-in concept, you can easily input more than one value on the command line or (probably) by reading from a file, so bootstrapping a secret-sharing front end for arbitrary parties is fairly straightforward. Input arbitrary-length integers by passing a string to the Integer constructor.
Brute force implemented (sums of bins).
Note: x.select(b, y) -> if b: y else: x
To build:
$ python geninput.py -n <bits> -l <length>
$ cd build
...hardcode appropriate length into xtabs impl...
$ make xtabs
$ time ./bin/xtabs 1 <port> <bits> & ./bin/xtabs 2 <port> <bits>
The emp-ag2pc library implements a malicious 2-party protocol. This is primarily a protocol implementation, and as such, has far more primitive function specification and I/O abilities than the previous library. Circuits must be built in sh2pc, then passed to the authenticated garbling library as a text file. Any input must be specified as a Boolean array.
Our programming paradigms for this vary from the samples given. The examples are hash and encryption functions. They take an array of 0s as input and produce some interesting output. Our examples do not always produce interesting output in this way (e.g. multiply 3 with 0 input only produces 0s). We have included examples with hard-coded input by party, but you could adjust this to read from a file.
- write circuit in sh2pc format
- wrap circuit impl with
setup_plain_prot(true, "output.txt")andfinalize_plain_prot ()calls - compile with sh2pc
- move
output.txtto/usr/local/include/emp-tool/circuit/files/ - write boilerplate code in ag2pc format
- compile with ag2pc
- run generated binary
EMP-toolkit supports two circuits formats: Bristol Format and Bristol Fashion. They are described in Nigel Smart's MPC documentation; the EMP implementation lives in circuit_file.h.
The format is:
[NUM_GATES] [NUM_WIRES]
[NUM_INPUTS1] [NUM_INPUTS2] [NUM_OUTPUTS]
[NUM_GATE_INPUTS] [UNUSED] [GATE_INPUT1] [GATE_INPUT2] [GATE_OUTPUT] [GATE_TYPE]
Gate types are AND, XOR, NOT. For NOT gates, GATE_INPUT2 is ignored. For example, the file
106601 107113
512 0 160
1 1 177 749 INV
2 1 30 31 3599 XOR
1 1 55 4100 INV
1 1 62 4246 INV
........
has 106601 gates and 107113 wires. Player 1 has 512 input bits, player 2 has 0, and the circuit has 160 output bits. The first line indicates a NOT gate with 1 inputs wires. The input wire is 177, and the output wire is 749. The second line indicates an XOR gate with 2 input wires (30 and 31), and output wire 3599.
Most files specify a number of players, e.g.
const static int nP = 3;
Unfortunately, simply changing this value from 3 to four will result in errors, because the IP addresses of the parties are hard-coded in cmpc_config.h
const static char *IP[] = {""
, "127.0.0.1"
, "127.0.0.1"
, "127.0.0.1"};
If you want to increase the number of parties, you need to manually increase the length of the array of IP addresses in cmpc_config.h.
TL;DR
- Declare all inputs before executing any operations
- Declare all of ALICE's inputs first, then all of BOB's
ag2pc and agmpc can only execute circuits, so the recommended workflow is to generate a circuit using sh2pc, then execute it with ag2pc or agmpc. When outputting these circuits, it is important to declare all inputs first. The ag2pc and agmpc libraries implicitly assume the first wires are the input wires.
Thus
Integer a[n];
Integer b[n];
Integer c[n];
for( int i=0; i<n; i++ ){
a[i] = Integer(BITLEN,0,ALICE);
b[i] = Integer(BITLEN,1,BOB);
c[i] = a[i]+b[i];
}
will run perfectly well in sh2pc, but will result in errors ("no match GT!") in ag2pc and agmpc. Instead, the circuit needs to be generated as
Integer a[n];
Integer b[n];
Integer c[n];
for( int i=0; i<n; i++ ){
a[i] = Integer(BITLEN,0,ALICE);
b[i] = Integer(BITLEN,1,BOB);
}
for( int i=0; i<n; i++ ){
c[i] = a[i]+b[i];
}
So that all the input wires are declared before any other wires are created.
The circuit format does not attribute wires to different owners, it simply has input wires. When you generate the circuit using sh2pc, it does not matter if you assign the wires to ALICE or BOB. When you execute the circuit using agmpc, you simply see a number of sequential wires, and you can assign them bits from any of the parties.
The easiest way to make this work correctly is to declare all your ALICE variables before any of your BOB variables in the sh2pc circuit description, then fill in your ag2pc input vector from index 0 for both players.
At the end of circuit execution in agmpc, only player one gets the output bits (ag2pc now supports output to both parties). The ag2pc and agmpc libraries do not do any implicit input/output formatting: I/O are passed as bit arrays and you must format them yourself. The function bin_to_dec in utils.hpp is useful for converting strings of bits to strings in decimal notation.
global scale paper - describes protocol + evaluates library
2-party paper - describes new 2-party protocol
constant 2-party paper - describes new constant-round 2-party protocol
2-party input valid
github - lots of related libraries.
doc - auto-generated, sparse