{{ message }}

# wbernoudy / pygarble Public

Garbled circuits in Python

Switch branches/tags
Nothing to show

## Files

Failed to load latest commit information.
Type
Name
Commit time

# pygarble

This is an implementation of secure two party computation using Yao's garbled circuits.

Alice creates the circuit, and Bob evaluates it.

When specifying the structure of the circuit, you need to create three arrays of gates. The first array represents the gates that are on the inputs. The second is the gates in the middle of the circuit. Finally, the third array consists of the gates that lead to output.

Gates are represented by: `[unique gate ID, type of gate, [input0, input1]]` For gates on circuit inputs (i.e. in the first array), `input0` and `input1` are the indices of input. For the other gates (in the other two arrays), `input0` and `input1` are IDs of other gates.

The `Circuit` class takes as its first argument the number of circuit inputs, and then the three arrays.

For example:

```> from alice import *
> on_input_gates = [[0, "AND", [0, 1]],
>                [1, "XOR", [2, 3]],
>                [2, "OR", [0,3]]]
> mid_gates = [[3, "XOR", [0, 1]],
>             [4, "OR", [1, 2]]]
> output_gates = [[5, "OR", [3, 4]]]
> mycirc = Circuit(4, on_input_gates, mid_gates, output_gates)```

We can now view the possible inputs of the circuit by accessing `mycirc.poss_inputs`:

```> mycirc.poss_inputs
[{0: b'4diGEaU1jdM3Pu-BJNSP9g7_QPc4ujAzGxl2BGoVG0M=', 1: b'wIXEEaM1S004rNrGEJDCxjtkLItla98ybjKE70ffGRU='}, {0: b'GfwHUAuJvWac23NGyT8aeoJbUWAB-yBcucuQhUt2jwg=', 1: b'BfBToX-S0Jqxb5wA1nhFHga-QILPsYzRMRbmuVHgNa8='}, {0: b'louVKwBH3BVABygcEjSd_oZboJBUUFVSoS67q_YLu9E=', 1: b'W6Lk0qWa7ly0QqxOMIrkrQQP-EXBIkC2NHgUWPn2qY8='}, {0: b'_acYcuVdFNjgmHUhDsKe7rTJbg_o2-MSuBv1gBE_lp4=', 1: b'H27Eo04R8_6S9xAMYFo8sxzn_VmJITg9-joTa1HNTzI='}, {0: b'2ihLVa48z4b6c-xI7D7dWPVRMO-XyewKcVTegn2xDPY=', 1: b'u50GeBJpyRbmFLQnFETQmbTgan5vQLYSTtCEBhHQu98='}]```

Each array is a pair of keys, where the first corresponds to `0` and the second to `1`.

We could now evulate the circuit from Alice's side using these keys. For example if we wanted to evaluate the input `0, 1, 0, 1`:

```> my_input = [x[y] for x, y in zip(mycirc.poss_inputs, [0, 1, 0, 1])]
> my_input
[b'4diGEaU1jdM3Pu-BJNSP9g7_QPc4ujAzGxl2BGoVG0M=', b'BfBToX-S0Jqxb5wA1nhFHga-QILPsYzRMRbmuVHgNa8=', b'louVKwBH3BVABygcEjSd_oZboJBUUFVSoS67q_YLu9E=', b'H27Eo04R8_6S9xAMYFo8sxzn_VmJITg9-joTa1HNTzI=']
> mycirc.fire(my_input)
{5: b'\x01'}```

As we can see, `mycirc.fire` returns a dict with key corresponding the ID of each of the output gates (in this case just gate 5), and its output encoded as a byte. In this case, the output of the circuit was 1.

We can then export the `Circuit` object to a dict for json with:

``````> j = mycirc.prep_for_json()
``````

Now, switching to Bob, after loading the json generated by Alice into `json_data` for example, we can do:

```> from bob import *
> mycirc = Circuit(json_data)```

And we have a `Circuit` object that works pretty much the same way as Alice's. However, we don't have the same info as before (i.e. all the possible inputs), making it impossible for Bob see what computation is actually happening.

We could now do (on Bob's terminal):

```> input = [b'4diGEaU1jdM3Pu-BJNSP9g7_QPc4ujAzGxl2BGoVG0M=', b'BfBToX-S0Jqxb5wA1nhFHga-QILPsYzRMRbmuVHgNa8=', b'louVKwBH3BVABygcEjSd_oZboJBUUFVSoS67q_YLu9E=', b'H27Eo04R8_6S9xAMYFo8sxzn_VmJITg9-joTa1HNTzI=']
> mycirc.fire(input)
{5: b'\x01'}```

## Oblivious Transfer

Because Bob doesn't want to show Alice his input, he needs a way to get the input keys from Alice without revealing his input bits. Thus, oblivious transfer.

My implementation is based on this paper: Non-Interactive t-out-of-n Oblivious Transfer Based on the RSA Cryptosystem

`ot.py` provides two classes, `Alice` and `Bob`. On Alice's terminal:

```> from ot import *
> from alice import keypair # we will use this to generate some example keys
> my_keypair = list(keypair().values())
> my_keypair
[b'tWiWGameWDMNOTUDRBM2FUWHkpPg9ZqWPM_e3bsvdqc=', b'5-x4_N0gwM_Hh0AYnSykYn2Ab4sCUw9iUzBVw9ZK8tw=']
> alice = Alice(my_keypair)```

We can now run `setup` on the `Alice` object, which will begin the OT. By default, it writes json to a file called `alice_setup.json`.

```> alice.setup()
Pubkey and hashes published.```

Now switch to Bob's terminal. To create a `Bob` object, we pass the number of messages Alice has, the number of desired messages, and a list of the IDs of the messages we want. Let's say we want the second key Alice has:

```> from ot import *
> bob = Bob(2, 1, )
> bob.setup()
Polynomial published.```

By default, `Bob.setup` reads from `alice_setup.json` and writes to `bob_setup.json`.

Now back to Alice's terminal:

```> alice.transmit()
G has been published.```

This by defualt reads from `bob_setup.json` and writes to `alice_dec.json`.

Finally, back to Bob's terminal:

```> bob.receive()
[b'5-x4_N0gwM_Hh0AYnSykYn2Ab4sCUw9iUzBVw9ZK8tw=']```

This by default reads from `alice_dec.json`.

We can see we have the key we asked for. If something goes wrong in transmission or Alice tries to mess with things (i.e. the hashes don't match), we get:

```> bob.receive()
Hashes don't match. Either something messed up or Alice is up to something.
[b'messed up hash key here']```

Garbled circuits in Python