Garbled Circuit

In this lab, we will create a garbled circuit for a circuit for the Millionaire problem, in which Alice and Bob wants to decide who is richer. Well, we are going to solve a simplified version of the Millionaire problem -- Alice's (resp. Bob's) input is only two bits long. We want to compute who's input is bigger.

In particular,

Alice's input: \(x_0, x_1\).
Bob's input: \(x_2, x_3\).
The function we compute: \[ f(x_0, x_1, x_2, x_3) = \left \{ \begin{array}{l} 1 \mbox{ if } 2x_0 + x_1 > 2x_2 + x_3 \\ 0 \mbox{ otherwise } \end{array} \right. \]

Throughout the lab, we will use the following circuit that implements the function \(f\):

Here, \(\vee\) denotes an OR gate, and \(\wedge\) denotes an AND gate.
Wire 4 contains whether Alice's first bit \(x_0\) is greater than Bob's.
Wire 5 contains whether Alice's first bit is the same as Bob's.
Wire 6 contains whether Alice's second bit is greater than Bob's.
Wire 7 contains whether Alice's first bit is the same as Bob's but Alice's second bit is greater than Bob's.
It is easy to see Wire4 OR Wire7 is what we want.

[45pts] Part 1: Garbled Circuit Evaluation

Download lab07.tar. There are three types of files: input keys, an output key pair, a garbled circuit.

Input keys file

An input keys file contains 4 keys in binary (one for each wire). Recall that Alice generates two random keys for each wire. Only one of the two is stored in the input keys file. In other words, we are simulating Bob's situation. It is hidden to Bob whether a given key encodes 0 or 1.

These keys correspond to \(x_0, x_1, x_2, x_3\) in order. Note that we don't know what the value of \(x_i\)s just from seeing the input keys.
Each key is 32 bytes long (i.e., two lines in the hexdump).
Each key has a format of b"wire key: ...."

$ hexdump -C ex1-inkeys.bin
00000000  77 69 72 65 20 6b 65 79  3a 20 20 b0 c7 b9 b4 9d  |wire key:  .....|
00000010  ba e5 3b d9 b3 2a 8d 49  fb 28 bf 22 55 d0 84 2b  |..;..*.I.(."U..+|
00000020  77 69 72 65 20 6b 65 79  3a 20 20 be b4 4e 6e 1c  |wire key:  ..Nn.|
00000030  e4 c4 77 f1 06 ec d0 13  8a 8e a6 ba 43 5b 6b 3a  |..w.........C[k:|
00000040  77 69 72 65 20 6b 65 79  3a 20 20 e9 75 8f 76 e9  |wire key:  .u.v.|
00000050  16 27 bd 60 e9 a7 f9 26  47 70 ef d2 19 bb 88 38  |.'.`...&Gp.....8|
00000060  77 69 72 65 20 6b 65 79  3a 20 20 07 78 21 94 f8  |wire key:  .x!..|
00000070  c4 1f c7 43 71 8f f8 7b  ad 77 d1 39 f7 46 f6 bc  |...Cq..{.w.9.F..|
00000080

Output key pair file

An output keypair file contains a pair of keys for the output wire (i.e., wire 8).

As above, each key is 32 bytes long.
The first key corresponds the bit value 0 for wire 8.
The second key corresponds the bit value 1 for wire 8.

$ hexdump -C ex1-outkeys.bin
00000000  77 69 72 65 20 6b 65 79  3a 20 20 5e c7 c0 ec 11  |wire key:  ^....|
00000010  12 c4 d0 fc 76 01 9e a4  1c 0b 28 44 b5 5e f4 a7  |....v.....(D.^..|
00000020  77 69 72 65 20 6b 65 79  3a 20 20 23 89 86 ee ae  |wire key:  #....|
00000030  78 e5 b9 d8 16 7a d3 6f  0e 94 c8 8e e0 52 34 b4  |x....z.o.....R4.|
00000040

Garbled Circuit file

A garbled circuit file contains 5 garble tables.

Each garbled table is 8 lines long in the hex dump.
Each garbled table contains 4 encryptions. That is, each ciphertext is 2 lines long (i.e., 32 bytes).
The file contains the garbled gate tables whose output wires are 4, 5, 6, 7, and 8 in order.

$ hexdump -C ex1-gc.bin
00000000  d2 21 4c fc 4f 37 a0 73  3b 97 b1 c1 40 ba 3f 60  |.!L.O7.s;...@.?`|
00000010  57 4e bc 02 3b 3f 73 9b  f8 c7 b8 7b 04 bb b8 36  |WN..;?s....{...6|
00000020  ce a3 0c 42 57 62 ab 27  41 5c 79 60 a2 be 39 0b  |...BWb.'A\y`..9.|
00000030  c0 25 c1 50 b8 9c 0e 63  a0 e9 54 83 4f 74 c9 63  |.%.P...c..T.Ot.c|
00000040  8f 01 ba ec 9d b6 11 c7  a2 d9 3d 42 65 c7 6a 38  |..........=Be.j8|
00000050  ca 8c 46 bf 7f 1c ca 2a  68 69 1a b0 7c f0 1e a3  |..F....*hi..|...|
00000060  24 12 61 c1 c6 c9 c8 43  a9 b2 4b c5 5b 40 f2 70  |$.a....C..K.[@.p|
00000070  51 f8 7c 87 a3 27 a3 c8  29 ae ce b8 a3 89 70 55  |Q.|..'..).....pU|
00000080  d2 21 4c fc 4f 37 a0 73  3b 97 b1 5e 50 c4 bc fb  |.!L.O7.s;..^P...|
00000090  b6 ee c7 f1 bf 32 a6 05  04 97 b7 62 d6 ee 50 be  |.....2.....b..P.|
000000a0  ce a3 0c 42 57 62 ab 27  41 5c 79 ff b2 c0 ba 90  |...BWb.'A\y.....|
000000b0  21 85 ba a3 3c 91 db fd  5c b9 5b 9a 9d 21 21 eb  |!...<...\.[..!!.|
000000c0  8f 01 ba ec 9d b6 11 c7  a2 d9 3d 7d 3e f0 22 ee  |..........=}>.".|
000000d0  f4 4d 59 b8 48 cd f1 83  5a 80 34 3a 77 2e 70 e8  |.MY.H...Z.4:w.p.|
000000e0  24 12 61 c1 c6 c9 c8 43  a9 b2 4b 1d be 2f 8f e0  |$.a....C..K../..|
000000f0  68 0c 1d 34 92 5b 19 ca  f8 ef 49 9b 2e 5c 38 df  |h..4.[....I..\8.|
00000100  9e d0 47 57 a5 8c 2b df  f4 d2 84 29 e7 f4 ec ea  |..GW..+....)....|
00000110  12 fd f8 f4 d8 2c 7d 25  54 54 be 93 ca e8 53 e4  |.....,}%TT....S.|
00000120  73 85 2b 58 57 f4 cf 1c  82 82 d6 f1 0c df c3 eb  |s.+XW...........|
00000130  8d 2d 94 32 74 70 92 b4  f6 56 d9 55 2c 66 40 e7  |.-.2tp...V.U,f@.|
00000140  77 a5 f5 a7 6c 88 eb 20  93 7c 23 fc ce 8e 11 34  |w...l.. .|#....4|
00000150  95 6d 32 3a 34 e4 6b 76  ea 83 04 c6 32 e0 59 17  |.m2:4.kv....2.Y.|
00000160  80 19 46 eb 02 4f 8a c9  a7 9b 31 d5 ad da 37 82  |..F..O....1...7.|
00000170  92 08 bf e8 4a e2 e1 46  b0 c8 2e 68 5e 2d a8 85  |....J..F...h^-..|
00000180  31 fb d0 6b b7 6d 86 d4  21 b5 59 2b 6f 1e 59 ad  |1..k.m..!.Y+o.Y.|
00000190  be 67 64 90 63 e2 10 94  4c 07 f5 be 1a 04 1a 81  |.gd.c...L.......|
000001a0  3c ae 53 36 cf 77 62 ba  73 af fc a7 22 4c 89 9f  |<.S6.wb.s..."L..|
000001b0  10 a1 4b e6 89 82 85 5b  cf cb e8 a0 37 27 f3 3d  |..K....[....7'.=|
000001c0  84 a8 dd a8 b4 29 33 c1  3a a0 36 e7 4d 9a 68 bf  |.....)3.:.6.M.h.|
000001d0  70 2e 34 38 69 90 0a 5f  77 4e 86 d6 76 7b 99 dd  |p.48i.._wN..v{..|
000001e0  55 f4 11 d4 0b 35 51 9b  20 eb 04 71 fe 93 19 1a  |U....5Q. ..q....|
000001f0  71 5f aa 10 3e a3 f5 df  41 dc 8c f0 66 24 09 50  |q_..>...A...f$.P|
00000200  96 f9 42 a5 2b 7a 66 43  c2 f9 41 16 91 70 05 55  |..B.+zfC..A..p.U|
00000210  bc f3 3b a4 58 24 b0 7f  22 99 98 f5 65 39 84 e1  |..;.X$.."...e9..|
00000220  a9 a6 7f e1 bf b1 33 91  40 8c f2 72 f2 3f 72 03  |......3.@..r.?r.|
00000230  45 9c c3 03 c5 cd 9a 0c  15 5b 12 ca 75 a9 32 fe  |E........[..u.2.|
00000240  e2 2f 66 14 e3 85 8c 06  e2 dc a0 d9 e4 21 40 0f  |./f..........!@.|
00000250  c6 ba 73 18 a7 20 b1 5e  d6 5a 3d 96 17 7d bf 05  |..s.. .^.Z=..}..|
00000260  76 b7 a6 d2 96 a1 6d fc  c3 dd ac 12 d6 c1 0d a7  |v.....m.........|
00000270  e4 42 16 c8 6a f9 53 6d  c0 cc 8b 01 f3 bf 45 d6  |.B..j.Sm......E.|
00000280

Your task

Download the partial code garbled_circuit_py.txt.
Implement a function eval() in the file so that the code works as shown below.


>>> import garbled_circuit
>>> garbled_circuit.eval("ex1")
key for wire 4: b'wire key:  \xb7X\x0cU\x8d;4\xc4l\xfdV\x16o\x87\x0c\x08S\x9dM4#'
key for wire 5: b'wire key:  (Hr\xd6\x16\xda\x94\xbf\x9fy[\xc3\xf1{\\\x07JO\x18\xdc\xab'
key for wire 6: b'wire key:  \xf6\xde\xf9,\xdd\x96\x07;\xcd?\x89\x89R%\x13\x05\x89\xd2\x16k-'
key for wire 7: b'wire key:  \x0ca\xac\xa2$0\xb2\xac^P,T(\xb8J6/\x06\xcb\xc3\xb3'
key for wire 8: b'wire key:  ^\xc7\xc0\xec\x11\x12\xc4\xd0\xfcv\x01\x9e\xa4\x1c\x0b(D\xb5^\xf4\xa7'
output is  0
>>> garbled_circuit.eval("ex2")
key for wire 4: b"wire key:  7!\xc1\xb8\xaa2]\xc4\x92\xfb\x8ba/r\xeeV\x81k'\xa1\xa8"
key for wire 5: b'wire key:  \x0fD\x19X\xea\xee\xd7\x96AX\xcb\x9f\xdf\x16l\xb8\xe1\xf3\x9a\x1f7'
key for wire 6: b"wire key:  \x85\x91\r\x1f\x00_qo}\xd5Vw\xdf?\x02\xb8'\x1a\xa7v\xb3"
key for wire 7: b'wire key:  F!YW\x9b\x1c*\xa4\xd3\x14Z\xe8\xc6\xad\xc5\x18~b\xe6MG'
key for wire 8: b'wire key:  \x8e7\xee\xaf\xe2\x8c\xc6WI\xee\x06\x89\xc5\xae\x1f\xd2\xf9C\xf5{C'
output is  0
>>> garbled_circuit.eval("ex3")
key for wire 4: b'wire key:  \xaf[\xcbO\x1c\xa7-\x83H\x91\x18\xac\xe9\x8ce>9\x907w\xa8'
key for wire 5: b'wire key:  \xf4c\xe0\xa4\xf21\xc5\xaf\xc6\xcc_\xf7\xcb\xa4\xcf;\xc4\xd0\xe5\xfc\xc6'
key for wire 6: b'wire key:  N\xf6N_\x03^\x88\xfarX\xf5\x18\xfe\xaeWZR\xbb\x96?\x81'
key for wire 7: b'wire key:  \xe5\x17\x02l\x9b!\xa63\xcd&\r$y\x1c\xd3a\xfe%8\x06\xcf'
key for wire 8: b'wire key:  \x91l!7K\xfc\x02U\xce\xee(\x1b\xbf\x90\xd8\x97\x1fq15\x9a'
output is  1

Note: Your function should print out the keys exactly as above.

Submit

You must pass all the test cases for part 1 in the submit server.

[40pts] Part 2: Garbled Circuit Creation

Your Task

In garbled_circuit.py, add a function create_gc() that works as follows:

The function create_gc() should return two objects:

wires: 9x2 array of bytes objects (with each key being 32 bytes long). wires[i][b] will contain the wire key for wire i and bit b.
gc: 5x4 array of ciphertexts (with each ciphertext being 32 bytes long). gc[g] is a garbled table for wire number 4+g (Note that the number 4 comes from the fact that the first 4 wires are the inputs).

Note: Since the keys are randomly sampled, your code execution will have different keys. That's fine.

Storing them into files

You can follow the scripts given on the right.

Note that the created files must be evaluated correctly when running eval() function you wrote.
In the right example,
we have x = [0, 1, 1, 0].
That is, Alice's input is 1 (i.e., 01), and Bob's input is 2 (i.e., 10). So, the circuit evaluates false (0).


>>> wires, gc = garbled_circuit.create_gc()

>>> for i in range(9):
...   for b in range(2): print("[%d][%d]"%(i,b), wires[i][b])
...
[0][0] b'wire key:  \xb6\xba\xd7o\x17\xceP!1\xbcu\xaaH{\x1c\xb2\xef\x08\x81Q\xce'
[0][1] b'wire key:  Y{\x80\xeft\x0b"\xd3b\xd0\xe8o\n\x9e(\xf8\xe1$_\x9dC'
[1][0] b'wire key:  \xc2\x01\xe3 z\x0e\x10\xe5@\x19S\xf0\xe0nK\xb3\xb7!{\x0f)'
[1][1] b'wire key:  \x88\xb1+\xb7\xcd@\x88\xca\xaas\x83\xad\x9f\xeb\x96\xad\xe1\x03\xc7\xd9\xcf'
[2][0] b"wire key:  O`\x95\x9e\xc1\xfc'\xd9\xd6[{\xef\xe8b\x8c\x99\xba\xe9\xa4\\\x08"
[2][1] b'wire key:  \x03\x0f\x82!tZ`\xf5Z5?\xe5\xc7\xed>&\xaa\x00\x8esw'
[3][0] b'wire key:  \x14_C\x1b\xe27\x11\ns\xa45;-\xbc[#\x92\xe9&\xc9\xda'
[3][1] b'wire key:  \t2\xa0\xa9\x9a\xc1\xab\xd0\xbft\xec\xe5\xe9\x9d;\x0c\xe4\xa9P\xa0\x15'
[4][0] b'wire key:  \xf6\xa91<\x12\xa8\xf9\xc6\x14M\x07\xf3O\xa8}U\xe9\x90\x81\x046'
[4][1] b'wire key:  \x82\xd6\xa1\xd2\xb9\xd9\xba\x97P\xb5\x82Y\x04\xfd{|~\xcdX\xea)'
[5][0] b'wire key:  \xfe\xb1F\xf6\xcd\x15\xc2\x937\x922D\xbb\x08\x1f\xd0N\xa5\xec3}'
[5][1] b'wire key:  \x94\xe0\x9f\xb1\x85\x96NF2i\xddn\xedR\xd8\xee<`ji`'
[6][0] b'wire key:  w\xe9!\xa7\xbc\x9d\x10\r|hu\x88\xd72\xc7\xd1\x07\xf1\x8f\xac\xb8'
[6][1] b'wire key:  \xca\xd6g.\xe3\xa5H\xe2\x9c\x93\x18<\x9c\x99f=\xe1N\xbd\xb1\xf1'
[7][0] b'wire key:  \x1c\r\x85\xfaX\x1f\xa0/ \xa8\x1b\xdc\xf4\xfaU8\x17\x02\xd0b8'
[7][1] b'wire key:  \xd7\xda\xa9\xc6\xef\xcax\xa5\xad\x9dZ\xce\xc3\xd1\xfd\xf9\xef\x1b\x02\x9aw'
[8][0] b'wire key:  \x0b\xcbY~\xae\x7f\x84\xb7D\x9c\xce\xc2,;ZV\xe9\x91\xd1\xa2\x83'
[8][1] b'wire key:  0\x8b\xe2\x1f\x9aFuDu.\x08\xcd\x9c\xb8fw\x0c\\\xa9\x80\xf8'

>>> x = [0, 1, 1, 0]
>>> input_keys = [ wires[i][x[i]] for i in range(4) ]
>>> fin = open("ex4-inkeys.bin", "wb")
>>> for k in input_keys: fin.write(k)
...
32
32
32
32

>>> fout = open("ex4-outkeys.bin", "wb")
>>> fout.write(wires[8][0]); fout.write(wires[8][1])
32
32

>>> fgc = open("ex4-gc.bin", "wb")
>>> for gate in range(5):
...   for i in range(4):
...      fgc.write(gc[gate][i])
...
32
(omitted) 
32
>>> fin.close(); fout.close(); fgc.close();
>>> garbled_circuit.eval("ex4")
key for wire 4: b'wire key:  \xf6\xa91<\x12\xa8\xf9\xc6\x14M\x07\xf3O\xa8}U\xe9\x90\x81\x046'
key for wire 5: b'wire key:  \xfe\xb1F\xf6\xcd\x15\xc2\x937\x922D\xbb\x08\x1f\xd0N\xa5\xec3}'
key for wire 6: b'wire key:  \xca\xd6g.\xe3\xa5H\xe2\x9c\x93\x18<\x9c\x99f=\xe1N\xbd\xb1\xf1'
key for wire 7: b'wire key:  \x1c\r\x85\xfaX\x1f\xa0/ \xa8\x1b\xdc\xf4\xfaU8\x17\x02\xd0b8'
key for wire 8: b'wire key:  \x0b\xcbY~\xae\x7f\x84\xb7D\x9c\xce\xc2,;ZV\xe9\x91\xd1\xa2\x83'
output is  0

Submit

You must pass all the test cases for part 2 in the submit server.

[15pts] Part 3: Writing a Lab Report

Please explain and show your work. Write a lab report by using the provided template (check the lab ground rules). The writing quality of the lab report matters.

For each part, briefly explain the ideas of your work in the lab report.

~/bin/submit -c=IT432 -p=lab07 lab_report.docx garbled_circuit.py