Suppose you and your friend, both fabulously wealthy, wish to find out which is the wealthiest. However, since you don't entirely trust your "friend", you don't want her to find out exactly how much money you have. Your friend, likewise, wishes to keep her exact wealth secret from you.
This scenario poses an interesting dilemma. Can you and your friend devise a protocol to determine who is wealthier without revealing your respective wealth to the other?
This problem—Yao's Millionaire Problem—was posited by computer scientist Andrew Yao in the mid-1980s. While specific solutions exist for the specific case of securely comparing two integers, the more general problem defines an interesting subfield in cryptography: how can two or more parties jointly evaluate a function over all their inputs, whilst keeping each party's input a secret from the others? The goal of **secure computation ****is to find good answers to this question.
In this document we will learn about the garbled circuit, which is one of the earliest general protocols for secure computation. Despite being around since the 1980s, cryptographic protocols based on this primitive are still widely employed today. The vanilla protocol itself is quite simple; therefore it serves as an excellent starting point for the study of secure computation. We will first learn about the basic garbled circuit protocol with no frills attached, and then cover some common optimizations to the protocol.
We will learn about garbled circuits by running through a simple example with two parties, Alice and Bob.
We introduce the problem of secure computation informally in the foregoing section. Let us now define it more rigorously for two parties. In our scenario, suppose Alice has binary inputs $a_1,\ldots, a_m$ and Bob has binary inputs $b_1,\ldots, b_n$. Alice and Bob wish to jointly evaluate some function $f(a_1,\ldots,a_m,b_1,\ldots,b_n)$, but Alice wishes to keep $a_1,\ldots, a_m$ secret from Bob, and Bob wishes to keep $b_1,\ldots, b_n$ secret from Alice. We assume that there is no trusted third party that can compute $f$ on Alice and Bob's behalf; therefore, Alice and Bob must find a way to do this on their own.
To accomplish our goal using garbled circuits, $f$ must first be transformed into an acyclic boolean circuit. Once is this done, one party is designed as the garbler*,* while the other is designated as the evaluator. At a very high level, the garbled circuits protocol proceeds as follows:
Without loss of generality, let Alice henceforth be the garbler and Bob be the evaluator.
In proper secure computation, both Alice and Bob are able to privately contribute inputs to $f$. In our discussion, we will start with a simplified protocol in which only Alice contributes input, while Bob only evaluates. We will then show how we can easily amend our protocol to allow Bob to contribute input as well.
In the following example, we will evaluate the function $f(a,b,c,d) = a \land b \land c \land d$, where $a,b,c,d\in \{0,1\}$. This function is the logical conjunction of four boolean variables—we expect $f$ to return $1$ if $a=b=c=d = 1$, and $0$ otherwise.
Recall that we will first define a garbled circuits protocol in which Alice, the garbler, possesses all input, while Bob, the evaluator, only evaluates. We will learn how to allow Bob to contribute input later.