This is the archived website of SI 486H from the Spring 2016 semester. Feel free to browse around; you may also find more recent offerings at my teaching page.

Problem 87

Run a garbled circuit using openssl

Due: April 19
Points: 2

The circuit

The image below shows you Bob's view of a garbled circuit, where you see the encrypted gates, all the wires, and how they're connected. Note that Bob doesn't actually know the operation of each gate, just how to evaluate them if he has a value for each input wire.

And here are the encrypted truth tables for each gate.




Encryption and decryption

For this problem, you are going to use the openssl command-line utility (which is installed on all the lab machines and generally can be found on any typical Linux installation) for the encryption and decryption. Specifically, you are going to use the "blowfish" symmetric cipher and base64 encoding of ciphertexts. All valid wire values will be 6-digit numbers.

To perform the double-encryption of each truth table entry, I used the following command:

echo "OUTPUT_WIRE" | openssl bf -k INPUT_WIRE_2 | openssl bf -nopad -k INPUT_WIRE_1 -a

where OUTPUT_WIRE is the output value getting encrypted, and INPUT_WIRE_1 and INPUT_WIRE_2 are the input wire values. Remember that each wire value is a 6-digit number that either means true or false (but only Alice knows which is which).

(Note: the bf command means to use the blowfish cipher, -k is for inputting the encryption key on the command line, nopad says not to add any extra padding on the second encryption, and -a says to print the output in base64 encoding so you don't have to deal with funky characters on the command line.)

To reverse this process, you would do something like

echo "CIPHERTEXT" | openssl bf -d -k INPUT_WIRE_1 -nopad -a | openssl bf -d -k INPUT_WIRE_2

The result will either be the correct output wire value, or you'll get some error like "bad magic number" or "bad decrypt" indicating that it didn't work. Remember, with garbled circuits, exactly ONE of the decryptions will work and the rest will not.

Wire values

You each have some different input wire values to use in order to perform the computation. They have been emailed out to you. If you have any questions, ask Dr. Roche.

Your task

Simple: Just run the garbled circuit on your emailed wire values. Give me the values of both intermediate wires (\(w_5\) and \(w_6\)) as well as the output from the entire circuit (which will be either 0 or 1).