Fairplay: Secure Two-Party Computation

Fairplay describes a protocol by which two parties can securely evaluate a function with the same guarantees as if they were using a trusted 3rd-party. This makes it possible to answer questions like the Millionaire's Problem without using a trusted 3rd-party. The Millionaire's Problem is: of two people, determine who has more money, without either of them learning exactly how much money the other person has.

Activity

This activity involves an extremely simplified version of the Millionaire's Problem. Alice and Bob are the millionaires, and they each have just 1-bit inputs. The expected behavior of the circuit is given in the truth table.

In this activity, you will play the part of Alice in the protocol. This means that Bob has given you an encrypted binary circuit and his and your inputs to that circuit. The encryption protocol has been simplified, and as a side-effect, you must use trial and error to decrypt the gates. You will know the gate has been successfully decrypted when an English word is revealed (or a binary digit, in the case of Alice's outputs).

You will only be able to (successfully) decrypt one output from each gate. To compute an output, enter the gate's number and the x and y keys into the hasher. Then, use this hashed value output to decrypt one of the outputs from the truth table.

For example, consider a gate number 42, which only has a single input. Given the input key "fridge", you should get the value "f68607aa93bbe88e769b5e6d136337fe48485fab" from the hasher. This gate has two encrypted outputs, "000c000c0040000700580051" and "000e0059004c0052005f0050". Try decrypting these with the result from the hasher. You should only be able to decrypt one of them.

Alice's Input: pepper
Bob's Input: toyota

Evaluate the encrypted circuit to find:

1. Your output (should be either "0....." or "1....."). This indicates whether you have more money than Bob.
2. Bob's output (should be an English word, though you won't know whether it corresponds to 0 or 1). This indicates whether Bob has more money than you.