A two-party secure function evaluation using Yao's garbled circuit protocol
This project implements a two-party secure function evaluation using Yao's garbled circuit protocol. It has been started on November 2018 for the Privacy Engineering course of Imperial College London (CO408) and refactored on November 2020.
In our model, two parties Alice and Bob compute a function on their inputs without sharing the value of their inputs with the opposing party. Alice is the circuit creator (the garbler) while Bob is the circuit evaluator. Alice creates the yao circuit and sends it to Bob along with her encrypted inputs. Bob then computes the results and sends them back to Alice.
Code is written for Python 3.6+. Dependencies are:
Install all dependencies:
pip3 install --user pyzmq cryptography sympy
Clone this repository wherever you want and follow the instructions in next section.
make bob
.make <circuit-name>
e.g. make bool
. You can also run
make alice
to evaluate all circuits in circuits/ at once.Alice will print the truth table of the circuit for all combination of Alice-Bob inputs. Alice does not know Bob's inputs but for the purpose of printing the truth table only, Alice assumes that Bob's inputs follow a specific order.
The Makefile contains the most useful commands, but you can also directly use the script:
./main.py bob # Run Bob side
./main.py alice -c <circuit.json> # Run Alice side
./main.py -h # See all available options
To print the truth table of a circuit:
./main.py local -c <circuit.json>
To print a clear representation of the garbled tables of a circuit:
./main.py local -c <circuit.json> -m table
The project is composed of 4 python files:
GarbledCircuit
class which generates the keys, p-bits and garbled
gates of the circuit.GarbledGate
class which generates the garbled table of a gate.A few functions converted to boolean circuits are provided in circuits/.
A function is represented as a boolean circuit using available gates:
A few assumptions are made:
Here is the json representation of above circuit:
{
"name": "smart",
"circuits": [
{
"id": "Smart",
"alice": [1, 2],
"bob": [3, 4],
"out": [7],
"gates": [
{"id": 5, "type": "AND", "in": [1, 3]},
{"id": 6, "type": "XOR", "in": [2, 4]},
{"id": 7, "type": "OR", "in": [5, 6]}
]
}
]
}
Here is the truth table of the previous json circuit:
$ ./main.py local -c circuits/smart.json
======== Smart ========
Alice[1, 2] = 0 0 Bob[3, 4] = 0 0 Outputs[7] = 0
Alice[1, 2] = 0 0 Bob[3, 4] = 0 1 Outputs[7] = 1
Alice[1, 2] = 0 0 Bob[3, 4] = 1 0 Outputs[7] = 0
Alice[1, 2] = 0 0 Bob[3, 4] = 1 1 Outputs[7] = 1
Alice[1, 2] = 0 1 Bob[3, 4] = 0 0 Outputs[7] = 1
Alice[1, 2] = 0 1 Bob[3, 4] = 0 1 Outputs[7] = 0
Alice[1, 2] = 0 1 Bob[3, 4] = 1 0 Outputs[7] = 1
Alice[1, 2] = 0 1 Bob[3, 4] = 1 1 Outputs[7] = 0
Alice[1, 2] = 1 0 Bob[3, 4] = 0 0 Outputs[7] = 0
Alice[1, 2] = 1 0 Bob[3, 4] = 0 1 Outputs[7] = 1
Alice[1, 2] = 1 0 Bob[3, 4] = 1 0 Outputs[7] = 1
Alice[1, 2] = 1 0 Bob[3, 4] = 1 1 Outputs[7] = 1
Alice[1, 2] = 1 1 Bob[3, 4] = 0 0 Outputs[7] = 1
Alice[1, 2] = 1 1 Bob[3, 4] = 0 1 Outputs[7] = 0
Alice[1, 2] = 1 1 Bob[3, 4] = 1 0 Outputs[7] = 1
Alice[1, 2] = 1 1 Bob[3, 4] = 1 1 Outputs[7] = 1
And here is the clear representation of the garbled gates:
$ ./main.py local -c circuits/smart.json -m table
======== Smart ========
P-BITS: {1: 0, 2: 1, 3: 0, 4: 0, 5: 1, 6: 0, 7: 0}
GATE: 5, TYPE: AND
[0, 0]: [1, 0][3, 0]([5, 0], 1)
[0, 1]: [1, 0][3, 1]([5, 0], 1)
[1, 0]: [1, 1][3, 0]([5, 0], 1)
[1, 1]: [1, 1][3, 1]([5, 1], 0)
GATE: 6, TYPE: XOR
[0, 0]: [2, 1][4, 0]([6, 1], 1)
[0, 1]: [2, 1][4, 1]([6, 0], 0)
[1, 0]: [2, 0][4, 0]([6, 0], 0)
[1, 1]: [2, 0][4, 1]([6, 1], 1)
GATE: 7, TYPE: OR
[0, 0]: [5, 1][6, 0]([7, 1], 1)
[0, 1]: [5, 1][6, 1]([7, 1], 1)
[1, 0]: [5, 0][6, 0]([7, 0], 0)
[1, 1]: [5, 0][6, 1]([7, 1], 1)