Garbled Circuits is a cryptographic protocol that allows two parties to compute a function of their inputs, while keeping their inputs secret. The protocol is quite simple, however some of the optimizations (specifically half gates), are not as intuitive. Here I attempt to describe the half gate optimization.
Garbled Circuits
Lets say we have two parties which have secret bits $a$ and $b$, and want to compute a singular gate $G(a, b)$. Our gate $G$ can be represented as a lookup table
| $G(0, 0)$ | $G(0, 1)$ | ||
| $G(1, 0)$ | $G(1, 1)$ |
Say we generate two keys $k_0$ and $k_1$ for each value the input can take on and generate a new table by encrypting each value.
| $E(k_0^a || k_0^b) \oplus G(0, 0)$ | $E(k_0^a || k_1^b) \oplus G(0, 1)$ | ||
| $E(k_1^a || k_0^b) \oplus G(1, 0)$ | $E(k_1^a || k_1^b) \oplus G(1, 1)$ |
Now say we have keys $k_{a}^a$ and $k_{b}^b$. Then it is impossible to learn the values of $a$ and $b$ from these keys. However, we can still evaluate $G$ by decrypting the table via the keys.
Currently, knowing the position of the decryption still reveals the values of $a$ and $b$. Therefore we must shuffle the table to hide the positions.
But how do we find the position of the value we want to decrypt (other than trying all four)? We can concatenate a pointer bit to each key to distinguish between the rows.
So if we have $k^a || 0$ and $k^b || 1$, then we know that the two keys we have correspond to the entry at $(0, 1)$. The two keys can be anything, but we know the position of the encrypted value.
This value, $k^a || p^a$, is known as a wire label.
Now to evaluate a gate $G$, one party $P_1$ constructs this garbled gate $G'$. They send the garbled gate $G'$ over to $P_2$, along with the label $k^a || p^a$ corresponding $P_1$'s choice of input ($0/1$).
However, how does $P_1$ send $P_2$ the labels for $P_2$'s inputs? $P_1$ cannot learn anything about $P_2$'s inputs, and yet must send them to $P_2$.
Definition (Oblivious Transfer). An Oblivious Transfer protocol consists of two parties, the sender $\mathcal{S}$ and reciever $\mathcal{R}$. The sender has two secrets $m_0$ and $m_1$, and the receiver has a bit $b \in {0, 1}$.
Then an Oblivious Transfer protocol satisfies the following:
- The receiver obtains $m_b$ but nothing else.
- The sender does not learn anything (including what $b$ is).
Though Oblivious Transfer seems counterintuitive, there exist multiple ways to construct it. Here the details on OT do not matter, but it is important to know that it exists.
$P_1$ can then do an oblivious transfer with $P_2$ to send the keys necessary to evaluate the gate.
To extend this to any function, what we can do is instead of encrypting the result, we give the output of the gate two keys as well. Instead of encrypting the output, we instead encrypt the keys to the output, so $P_2$ will only learn the output key after decrypting the matching table value.
| $E(k_0^a || k_0^b) \oplus k_{G(0, 0)}^c$ | $E(k_0^a || k_1^b) \oplus k_{G(0, 1)}^c$ | ||
| $E(k_1^a || k_0^b) \oplus k_{G(1, 0)}^c$ | $E(k_1^a || k_1^b) \oplus k_{G(1, 1)}^c$ |
Now, since $P_2$ has the output key from that gate, they can then continue and use that key to evaluate the next gate. Therefore, by repeating this process for every single gate until the end, $P_2$ can evaluate the whole boolean function (where finally at the end we have a garbled gate mapping to the output).
Optimizations
Row Reduction
So is there any way to optimize this any further? Currently every gate requires $4$ ciphertexts to send. Garbled row reduction allows us to reduce this.
Note that each key $k^c$ does not necessarily need to be completely random. Consider the following table:
| $E(k_0^a || k_1^b) \oplus k_{G(0, 1)}^c$ | $E(k_0^a || k_0^b) \oplus k_{G(0, 0)}^c$ | ||
| $E(k_1^a || k_1^b) \oplus k_{G(1, 1)}^c$ | $E(k_1^a || k_0^b) \oplus k_{G(1, 0)}^c$ |
If we set $k^c_{G(0, 1)} = E(k_0^a || k_1^b)$, then the first row is always zero.
Now for every gate, one row will always be zero, and does not need to be sent. Therefore, we now only send $3$ ciphertexts.
FreeXOR
FreeXOR allows the evaluator instead to compute XOR gates without having to perform any decryption or store any table.
Instead of generating two random keys $k_0^a$ and $k_1^a$, we instead generate $k_0^a$ and compute $k_1^a = R \oplus k_0^a$, where $R$ is a single random value for all gates.
Therefore, for all gates, the labels satisfy the property that $k_0^a \oplus k_1^a = R$.
Now, instead of generating random output keys $k_0^c$ and $k_1^c$, we set them to the following:
$$k_0^c = k_0^a \oplus k_0^b$$ $$k_1^c = k_0^a \oplus k_0^b \oplus R$$
Now notice that our output keys satisfy the same property. Instead of sending an encrypted table over to the evaluator, now $P_2$ can just evaluate $k^a \oplus k^b$ to get the output wire label $k^c$.
Half Gates
Now the hard part: Can we apply any more optimizations, and how?
We would like to compute $a \wedge b = c$. We can rewrite this as following: $$ a \wedge b = c$$ $$a \wedge (r \oplus r \oplus b) = c$$ $$ (a \wedge r) \oplus (a \wedge (r \oplus b)) = c$$
Let us notate $p = a \wedge r$ and $q = a \wedge (r \oplus b)$.
Now say the sender generates a random bit $r$ and transforms the original gate to the following. Note that this is now an XOR gate with some additional complexity. If we know how to evaluate the left and the right, we can use FreeXOR to evaluate the full gate.
Left side
We want to evaluate $a \wedge r$, where the sender knows $r$. To do this, the generator creates the following table:
| $E(k_0^a) \oplus k_0^p$ | ||
| $E(k_1^a) \oplus k_0^p \oplus r\cdot R$ |
The table values are still shuffled with the pointer bit.
Now, if $a = 0$, then the evaluator will decrypt the first row, getting $k_0^p$, as $0 \wedge r = 0$.
If $a = 1$, then the evaluator will decrypt the second row, getting $k_0^p \oplus r\cdot R$. If $r = 0$, then the output will be $0$. If $r = 1$, then the output will be $k_0^p \oplus R$. Now note that this is equal to $k_1^p$.
Now, by the row reduction technique, we can decrease the size of this by setting $k_0^p$ equal to $E(k_0^a)$. Therefore, this only takes 1 sent ciphertext!
Now the evaluator is able to find $k^p$ for the left side. But how do we evaluate the right side?
Right side
We want to evaluate $q = a \wedge (r \oplus b)$.
| $E(k_0^{r \oplus b}) \oplus k_0^q$ | ||
| $E(k_1^{r \oplus b}) \oplus k_0^q \oplus k_0^a$ |
Say the evaluator knows $r \oplus b$. If this is zero, decrypting the first row of this table evaluates to $k_0^q$. If this value is 1, then we get $k_0^q \oplus k_0^a$.
Now, we can get the output label by XORing this with the label for $a$. If $a = 0$, we get $k_0^q \oplus k_0^a \oplus k_0^a = k_0^q$. If $a = 1$, then we get $k_0^q \oplus k_0^a \oplus (k_0^a \oplus R) = k_0^q \oplus R$. Note that this is equal to $k_1^q$.
But how does the evaluator know $r \oplus b$?
The sender can convey $r \oplus b$ to the evaluator by setting $r$ as the pointer bit when $b = 0$. Therefore, if the evaluator has the label when $b = 0$, they get the pointer bit $r = r \oplus 0$. If they have the label when $b = 1$, then they get the pointer bit $1 - r = r \oplus 1$.
So if the sender sets $r$ as the pointer bit when $b = 0$, the pointer bit that the evaluator gets is equal to $r \oplus b$.
Together
And so, we are able to evaluate the full AND gate by applying FreeXOR on the two outputs from both sides!
We see that we only need one row for each side (due to row reduction), and so we have a total of $2$ rows instead of $4$ usually needed.
Typically circuits only need to use XOR and AND, and since XOR gates are also free, we will only need $2 \cdot |A|$ ciphertexts for any circuit, where $A$ is the set of AND gates.
Conclusion
Half Gates improve quite a bit on standard garbled circuits. Interestingly, it was shown in [ZRE14] that the half gate optimization is optimal for a class of "linear" garbling schemes, by representing garbling and evaluation as linear algebra. Due to this, most garbled circuits in practice typically use this technique along with FreeXOR to minimize cost and allow larger circuits to be evaluated.