Theme Song: Nerdy Love

In this assignment, you'll implement oblivious transfer and garbled circuits to allow two parties to jointly compute a function without learning the other party's inputs.

Background Knowledge

In this assignment, you'll implement a simple version of Yao's garbled circuits using a simple version of oblivious transfer. This assignment leaves a lot of room for optimizations, which we leave to the reader to explore. However, in your final submission, do not submit with any optimizations as it will not be compatible with the autograder.

We highly recommend reading the first few pages of The Simplest Protocol for Oblivious Transfer for OT, and A Gentle Introduction to Yao's Garbled Circuits and Faster Secure Two-Party Computation Using Garbled Circuits for garbled circuits. It will help immensely in understanding the mathematics of this assignment.

Oblivious Transfer

A foundational building block in secure multi-party computation is oblivious transfer (OT), which allows a receiver to select a message from a sender without the sender learning which message they selected, nor the receiver learning more than the message they selected. At first glance, OT seems impossible to achieve, but as we will see, we can use basic primitives that we've seen already to build a simple yet secure protocol for 1-out-of-2 OT.

We present an implementation of OT based on the Diffie-Hellman key exchange. The protocol proceeds as follows:

Architecture simple OT

Yao's Garbled Circuits

Yao's garbled circuits allow two parties to jointly compute over a boolean circuit without learning any intermediate values or the other party's inputs. This is an immensely useful primitive as it allows two parties to jointly compute any function securely. We'll describe a secure two-party computation protocol that uses garbled circuits (without any optimization) and our OT implementation above, along with some other primitives we've been interacting with.

All of our circuits are specified using Bristol Format, which consists of three types of gates: AND, XOR, and NOT. We provide parsers to ease development. We highly recommend reading up on the format, should you need to debug a particular circuit or wish to write your own.

We present a simple construction of garbled circuits. The garbler and evaluator are the two parties. The protocol proceeds as follows:

Yaos Encryption

Some Resources

The following papers are incredibly useful for gaining a full understanding of protocols like ours:

Putting it all together

The following diagram explains how the protocol works together.

Yaos Overall

We don't give a detailed protocol description as it doesn't differ meaningfully from the base protocol described above.

Assignment Specification

Please note: you may NOT change any of the function headers defined in the stencil. Doing so will break the autograder; if you don't understand a function header, please ask us what it means and we'll be happy to clarify.


You will primarily need to edit src/drivers/ot_driver.cxx, src/pkg/garbler.cxx, and src/pkg/evaluator.cxx. The following is an overview of relevant files:

The following roadmap should help you organize concerns into a sequence:

Some tips:

Oblivious Transfer

Implement oblivious transfer. Once you do so, your clients will be able to transfer one of two values obliviously.

Cryptographic functions:

Garbled Circuit Generation

Implement garbled circuit generations. Once you do so, a valid garbled circuit will be generated, ready to be evaluated.

Cryptographic functions:

Application functions:

Garbled Circuit Evaluation

Implement garbled circuit evaluation. Once you do so, your two parties will be able to perform generic 2PC. Hooray!

Cryptographic functions:

Application functions:

Support Code

Read the support code header files before coding so you have a sense of what functionality we provide. This isn't a networking class, nor is it a software engineering class, so we try to abstract away as many of these details as we can so you can focus on the cryptography.

The following is an overview of the functionality that each support code file provides.

Libraries: CryptoPP

You may find the following wiki pages useful during this assignment:

Getting Started

To get started, get your stencil repository here and clone it into the devenv/home folder. From here you can access the code from both your computer and from the Docker container.


To build the project, cd into the build folder and run cmake ... This will generate a set of Makefiles building the whole project. From here, you can run make to generate a binary you can run, and you can run make check to run any tests you write in the test folder.


You may write tests in any of the test/**.cxx files in the Doctest format. We provide test/test_provided.cxx, feel free to write more tests in this file directly. If you want to add any new test files, make sure to add the file to the cmake variable, TESTFILES, on line 7 of test/CMakeLists.txt so that cmake can pick up on the new files. Examples have been included in the assignment stencil. To build and run the tests, run make check in the build directory. If you'd like to see if your code can interoperate with our code (which is what it will be tested against), feel free to download our binaries here - we try to keep these up to date, so if you're unsure about the functionality of our binaries, please ask us on Ed!