Garbled Circuits and Secure Function Evaluation

An important and recurring problem in cryptography is the problem of secure function evaluation (SFE). For simplicity, we just consider the 2-party setting. In the 2-party setting, the two agents, Alice and Bob, each have some private input {x} and {y}, respectively, and they want to compute some function of their inputs {f(x,y)} without revealing their inputs. The SFE problem was first introduced by Andrew Yao [1] in 1982 where he introduced what has come to be known as the millionaire problem.

Millionaire Problem. Alice and Bob are millionaires and are interested in knowing who is richer. However, they wish to do so without revealing their actual wealth.

If we view the above problem through the SFE lens, then {x} and {y} would coincide with Alice’s and Bob’s wealth, respectively. The function {f(x,y)} they want to compute would be the comparator function:

\displaystyle f(x,y)=\mathbb{I}\left\{ x>y\right\} =\begin{cases} 1 & x>y\\ 0 & \mathrm{otherwise}. \end{cases}

Note that {\mathbb{I}\{\mathrm{predicate}\}} denotes an indicator function that evaluates to 1 if the predicate is satisfied and 0 otherwise.

More generally, we can take {f(x,y)=(f_{a}(x,y),f_{b}(x,y))}, and at the conclusion of the protocol, Alice learns {f_{a}(x,y)} and Bob learns {f_{b}(x,y)}. Alice and Bob should not learn anything about the other’s input except what is explicitly leaked by the result. Observe that the millionaire problem described above is just a special case where

{f_{a}(x,y)=\mathbb{I}\{x>y\}=f_{b}(x,y)}.

Moreover, observe that we can take {f_{a}(x,y)=\perp}, where {\perp} denotes the null function. In other words, following the SFE protocol, Alice does not learn anything about Bob’s input, whereas Bob learns the value of {f_{b}(x,y)}.

One elegant construction of an SFE protocol is through garbled circuits. In this model, we will use a Boolean circuit to model the function {f}. A Boolean circuit consists of a series of logic gates: AND, OR, NOT, and so on. In our setup, a logic gate takes several input bits (0s and 1s) and produces a single output bit.  We can characterize the operation of a logic gate by writing down a truth table, that is, the gate’s output bit for each assignment to its inputs. As an example, consider an AND gate with two inputs. The output of an AND gate is 1 if both of its inputs is 1, and 0 otherwise. Thus, the truth table for an AND gate will look like the following:

Input 1 Input 2 Output
0 0 0
0 1 0
1 0 0
1 1 1

Similarly, we can write down truth tables for OR gates, NOT gates, and so on. Then, given a function {f(x,y)}, we can construct a Boolean circuit that evaluates {f}. A Boolean circuit consists of a series of logic gates with wires connecting the inputs and outputs of the different gates. From complexity theory, we know that if there exists a polynomial-time algorithm for computing {f}, then there exists a polynomial-sized circuit that evaluates {f}. Thus, the circuit model is quite flexible and allow us to efficiently model many functions of interest.

Thus, given a function {f}, we can construct a circuit that evaluates {f}. The final ingredient we need to obtain SFE is a way of evaluating the circuit without revealing any information about the inputs. The idea here is to take a circuit for {f}, and construct a garbled circuit {\mathcal{C}} that can be used to securely evaluate {f}. In particular, we seek a circuit that may be evaluated without revealing any information about the input or intermediate bits. To do so, we transform the circuit as follows:

  1. Observe that each wire in the circuit will carry a single bit. Then, for each wire {w}, we associate two random values {k_{w}^{0}} and {k_{w}^{1}} with the wire, depending on the bit carried by the wire. In other words, if the wire is carrying a 0, we assign it the value {k_{w}^{0}} and if the wire is carrying the bit 1, we assign it the value {k_{w}^{1}}. Note that because {k_{w}^{0}} and {k_{w}^{1}} are chosen uniformly at random, given {k_{w}^{b}} for {b\in\{0,1\}} does not yield information on whether {b=0} or {b=1}.
  2. Having scrambled the values of each wire, we still need a way to evaluate each gate. Recall that the behavior of a logic gate is entirely specified by its truth table. Thus, we prescribe a method for constructing a garbled truth table for each gate in our circuit. Consider a logic gate with input wires {w_{1},\ldots,w_{n}} and output wire {z}. As before, let {b_{1},\ldots,b_{n}} be the bits carried by the wires {w_{1},\ldots,w_{n}}, respectively. Then, let {h(b_{1},\ldots,b_{n})} denote the operation of the logic gate, that is, {z=h(b_{1},\ldots,b_{n})}. For notational convenience, we will write {k_{i}} to denote {k_{w_{i}}^{b_{i}}}, that is, the value of the {i^{\mathrm{th}}} wire if it is carrying bit {b_{i}}. Then, let {h'} denote the operation of our garbled gate. One candidate definition for {h'} is to simply yield {k_{z}^{h(b_{1},\ldots,b_{n})}}, that is the value of the output wire carrying the corresponding output bit:

    \displaystyle h'\left(k_{1},\ldots k_{n}\right)=k_{z}^{h(b_{1},\ldots,b_{n})}.

    Thus, we can simply construct a table mapping each assignment {\left(k_{1},\ldots,k_{n}\right)} to the corresponding value {k_{z}^{h(b_{1},\ldots,b_{n})}}. However, in the SFE setting, the circuit evaluator should only learn the value of {k_{z}^{h(b_{1},\ldots,b_{n})}} that corresponds to his particular set of inputs and nothing else about the circuit. Given a fixed set of input bits, the evaluator should only be able to extract one set of intermediate and output values from the circuit. If both possible values of a given wire was known, the evaluator can evaluate the circuit using different intermediate states, and in doing so, potentially learn additional information about the hidden inputs to the circuit. We want the evaluator to obtain one of {k_{z}^{0}} or {k_{z}^{1}} depending on the value of {h(b_{1},\ldots,b_{n})}. To do this, we treat {k_{1},\ldots,k_{n}} as encryption keys and encrypt the value of {k_{z}^{h(b_{1},\ldots,b_{n})}} using {k_{1},\ldots,k_{n}}:

    \displaystyle h'\left(k_{1},\ldots,k_{n}\right)=\mathsf{Enc}_{k_{1}}\left(\mathsf{Enc}_{k_{2}}\left(\cdots\left(\mathsf{Enc}_{k_{n}}\left(k_{z}^{h(b_{1},\ldots,b_{n})}\right)\right)\right)\right).

    In the above, {\mathsf{Enc}_{k}(m)} refers to the encryption of a message {m} using key {k}. In words, we successively encrypt the value of {k_{z}^{h(b_{1},\ldots,b_{n})}} with keys {k_{1},\ldots,k_{n}}. Observe that in this case, if we are given the input values {k_{1},\ldots,k_{n}}, then we can look up {h'(k_{1},\ldots,k_{n})} in the truth table to obtain an encryption of {k_{z}^{h(b_{1},\ldots,b_{n})}} with respect to keys {k_{1},\ldots,k_{n}}. Since we have the keys {k_{1},\ldots,k_{n}}, we can now decrypt this ciphertext to obtain {k_{z}^{h(b_{1},\ldots,b_{n})}}. Moreover, because we only have the keys {k_{1},\ldots,k_{n}}, we can only decrypt the ciphertext encrypting {k_{z}^{h(b_{1},\ldots,b_{n})}}, and in particular, we are not able to learn any information about the other value of the output wire {z}.

  3. For the output wires {w_{\mathsf{output}}} of the circuit, we set {k_{w_{\mathsf{output}}}^{b}=b}. Specifically, the value of an output wire carrying a given bit is just the value of the bit itself. Thus, when the evaluator decrypts the output wires on the circuit, he obtains the bits corresponding to the output of the circuit.

The above description is a bit abstract, so let’s consider a concrete example and construct the garbled equivalent of the AND gate from before. First, we assign values for each of the input and output wires. Let {k_{1}^{b}} and {k_{2}^{b}} for {b\in\{0,1\}} be the values corresponding to the two input wires. Let {k_{3}^{b}} be the value corresponding to the output wire. Then, using our construction above, the truth table for the garbled AND gate will be the following:

Input 1 Input 2 Output
{k_{1}^{0}} {k_{2}^{0}} {\mathsf{Enc}_{k_{1}^{0}}\left(\mathsf{Enc}_{k_{2}^{0}}\left(k_{3}^{0}\right)\right)}
{k_{1}^{0}} {k_{2}^{1}} {\mathsf{Enc}_{k_{1}^{0}}\left(\mathsf{Enc}_{k_{2}^{1}}\left(k_{3}^{0}\right)\right)}
{k_{1}^{0}} {k_{2}^{0}} {\mathsf{Enc}_{k_{1}^{1}}\left(\mathsf{Enc}_{k_{2}^{0}}\left(k_{3}^{0}\right)\right)}
{k_{1}^{1}} {k_{2}^{1}} {\mathsf{Enc}_{k_{1}^{1}}\left(\mathsf{Enc}_{k_{2}^{1}}\left(k_{3}^{1}\right)\right)}

Observe that given the inputs, we are able to compute just a single output bit. In practice, we randomly permute the entries in the table, so the table does not leak any information about the computation performed by a given gate. This concludes the construction of a garbled circuit. What remains is to show how we can use these garbled circuits to perform SFE. Recall our previous setup: Alice and Bob each have an input {x} and {y} and would like to securely evaluate some function {f(x,y)=\left(f_{a}(x,y),f_{b}(x,y)\right)} without revealing their private input. We arbitrarily designate Alice as the sender and Bob as the receiver. The protocol then proceeds as follows:

  1. Alice generates some secret key {s} and constructs a garbled circuit {\mathcal{C}} for the function {\tilde{f}(x,y)=\left(\mathsf{Enc}_{s}(f_{a}(x,y)),f_{b}(x,y)\right)}. Alice sends the garbled circuit {\mathcal{C}} along with her garbled inputs to Bob.
  2. Next, in order to evaluate the circuit, Bob needs to obtain the values corresponding to his input. However, since Alice constructed the circuit, only she knows what which values correspond to which bits. Thus, Bob must obtain the keys corresponding to his input from Alice, but without revealing to Alice the value of his input. We can accomplish this using a 1-out-of-2 oblivious transfer (OT) protocol. In 1-out-of-2 OT, Alice holds two keys {k_{0}} and {k_{1}}, and Bob holds a bit {b\in\{0,1\}}. At the end of the OT protocol, Bob learns the value of {k_{b}} and Alice learns nothing. I will defer the discussion of 1-out-of-2 oblivious transfer protocols to a future post. For now, it is sufficient to assume that such a protocol exists. Then, for each bit of his input, Bob engages in a 1-out-of-2 OT protocol withe Alice to learn the value corresponding to his particular bit. In this way, for each of his input wires {w}, Bob learns the value {k_{w}^{b}} where {b} is the value of that particular input bit.
  3. Since Bob now has all of the garbled inputs to {\mathcal{C}}, he evaluates {\mathcal{C}} and obtains the result {\left(\mathsf{Enc}_{s}(f_{a}(x,y)),f_{b}(x,y)\right)}. Thus, Bob learns the value of {f_{b}(x,y)}. He sends {\mathsf{Enc}_{s}(f_{a}(x,y))} to Alice.
  4. Alice decrypts {\mathsf{Enc}_{s}(f_{a}(x,y))} to obtain the result {f_{a}(x,y)}.

At the end of the above protocol, observe that Alice learns the value of {f_{a}(x,y)} and Bob learns the value of {f_{b}(x,y)}. Alice does not have access to the internal state of the garbled circuit (she does not evaluate {\mathcal{C}}), so she does not learn any information about Bob’s input. From Bob’s perspective, the circuit is garbled, so Bob does not learn any information regarding Alice’s input. Finally, we note that while Bob learns {\mathsf{Enc}_{s}(f_{a}(x,y))}, this does not leak any information about {f_{a}(x,y)} by semantic security of the underlying encryption scheme.

Note that the above protocol is only secure against honest-but-curious adversaries. In particular, we assume that Alice and Bob follow the protocol as described but may inspect the messages that are sent between them in order to learn something about the other’s input or response. In particular, we do not protect against malicious adversaries that may send malformed or malicious messages. Naturally, there are constructions that are secure even against malicious adversaries, but that’s a topic for a later time.

[1] Andrew Yao. Protocols for Secure Computations. FOCS 1982.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s