Multiparty Computation

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