Secure 2PC

In this lab, we will consider a Millionaire problem, in which Alice and Bob wants to decide who is richer. Well, we are going to sovle 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.

Note: garbled_circuit.py from the last lab

In this lab, you will use garbled_circuit.py that you wrote from the last lab.

[40pts] Part 1: Oblivious Transfer

Finish the activity in Class 20 by filling out code in ot.py. You must pass the test case for part 1 in the submission server.

[45pts] Part 2: Yao's Protocol

Download bob.py, which includes the program for Bob in Yao's protocol.

Your Task

Write code alice.py that implement Alice's part in Yao's protocol. Inspect bob.py carefully to see how the data transfer takes place.

You have to understand every detail in the program bob.py. If you have something unclear to you, google for it!

Bob first listens at port 8000.
Alice connects to Bob (with TCP) and sends GC, outkeys, Alice keys.
Then, Alice and Bob runs OT protocol twice for Bob keys.
Bob should evaluate the GC using the overall input keys and prints out the output.
The input of Bob is given by the command line arguments. The same goes for Alice.

Note:

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

Sample run

Note:

Execute bob.py first.
Below, Alice's input is 3 (11), and Bob's input is 2 (10). So, the output is 1.

$ python3 bob.py 1 0
key for wire 4: b"wire key:  \x0e\\^.\x04\xcf\x9f;\xd7V\xceJ#N\x0c\x9d'l\xee[\xf3"
key for wire 5: b'wire key:  \xc0\xc9}\xdfi"\x11P\x90\xec\xb2\xef?\xe5\xcf\xe6\xb32\x82F2'
key for wire 6: b'wire key:  \xbf\x18j\xf1\x99\xc1\x8d\xa1\xb0\x93\x84\x1e\xf2\xe0\x9b>S\x9eS\xa2\xa3'
key for wire 7: b'wire key:  \x9d\x1eY*\xbdT\xd3\x1d\x9b|\xd7M2\xbe+\x8a\xa8<\x8d\xef}'
key for wire 8: b'wire key:  \x05\xbf5\xd8\xb2\xdeu\x8e\x1e\xa6\xb0\xd4\xdc6N\x90\xfa\xbe\xb6q\x8a'
output is  1

$ python3 alice.py 1 1

Another sample run

$ python3 bob.py 1 1
key for wire 4: b'wire key:  3\x03H!\xb1B\xb2\x18\xa3\xc7\xa6\x94A\x15uU\x942\x0e\x14\x88'
key for wire 5: b'wire key:  \xb0\xa7\xd4\x82\xe86\x9f;f\xb8f\n\x95j\x8f)N@V\x14"'
key for wire 6: b'wire key:  \xcc\x00\xc3\xd2\xd5\xd0\x0bO\xb0\xb5\x1c\xc2\xdb.\xcd\xefIS\xdf\xa0\x8a'
key for wire 7: b'wire key:  M\xb2\x9d\xadO|\x987\x9c\x0c\xab\xffcc\xe4\x86(TQ\x8a}'
key for wire 8: b'wire key:  \xb2!Ji\x0c\xdcxw\xee{\xf1\xd8\x0cW\x97\x1f\xfa\xc9\xbf\x81i'
output is  0

$ python3 alice.py 1 1

Submit

Execute Yao's protocol at least three times with different inputs, and give screenshots in your report.

[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 garbled_circuit.py ot.py alice.py lab_report.docx