Yao's Garbled circuit: Does Bob ever see the circuit?

Question

I asked a question about whether the circuit structure for Yao's garbled circuit needs to be rearranged. I understand from Yehuda Lindell's response that the circuit structure itself does not need to be changed or garbled, only the gate ciphertexts need to be garbled.

New question: does this mean it is safe for Bob to be able to know the structure of the circuit? He should not be able to know the values on the wire, but is it fine for him to know for example which gates are AND gates?

It seems to me that this would not be safe. Here is my reasoning:

Let us say gate $g_s$ is an AND gate in the circuit with input wires $w_i$ and $w_j$ and output wire $w_k$. Based on this summary if $g_s$ is an AND gate, Alice has computed the following values:

$$X_s^{0,0} = K_i^0 \oplus K_j^0 \oplus K_k^0$$ $$X_s^{0,1} = K_i^0 \oplus K_j^1 \oplus K_k^0$$ $$X_s^{1,0} = K_i^1 \oplus K_j^0 \oplus K_k^0$$ $$X_s^{1,1} = K_i^1 \oplus K_j^1 \oplus K_k^1$$

She has shuffled and renamed these values $X_s^1,X_s^2,X_s^3,X_s^4$ and sent them to Bob. $K_i^0$ is the key for $w_i$ when it's value is 0 and so on.

Bob also has access to hashes of the two keys for each wire, though he does not know which key represents that wire being 0 and which represents 1.

Say Bob has $K_i^{v_i}$ and $K_j^{v_j}$ where $v_i,v_j\in\{0,1\}$ are the values of the wires $w_i,w_j$.

Say Bob calculates $K_j^{v_j}\oplus X_s^{0,0}\oplus X_s^{0,1}=K_j^{v_j}\oplus K_j^0\oplus K_j^1 = K_j^{1-v_j}$

He will still not know whether key $K_j^{1-v_j}$ is $K_j^0$ or $K_j^1$, but he will then have both keys for wire $w_j$.

Now, he may not know which two $X_s$ values are $X_s^{0,0}$ and $X_s^{0,1}$. But he can try all 6 combinations. Since Alice has given him $AUTH(K_j^{1-v_j})$ (where AUTH is a trapdoor function) Bob can apply this function to all 6 values and see which one matches the value that Alice gave him.

In the same way Bob could find the key of $K_i^{1-v_i}$.

Bob still does not know which keys represent 0s and which represent 1s. But he does know it is an AND gate, so if he calculates the value of the output wire key value for all 4 combinations of the input wire key values. For three of these, the output key will be $K_k^0$ and one of these will be $K_k^1$. So Bob will know which key represents 0 and which represents 1.

As far as I understand, Bob has also not deviated from the algorithm, since he can still compute what he is meant to compute and send Alice the output. So Bob is still honest-but-curious.

So it seems that if an honest-but-curious Bob knows what types of gates the circuit has he could discover which keys represent 0 and which represent 1.

Is there a flaw in this reasoning?

Thanks in advance.

Answer 1

That summary, on which you are basing your understanding, seems bogus to me. Clearly the same $K_i^b$ values are being used as one-time pad keys, but are being used more than once. This is a major red flag.

Here's an even simpler attack: if you XOR together all 4 ciphertexts $X_s^{i,j}$ you will get $\Delta = K_k^0 \oplus K_k^1$. Since the functionality of the construction ensures that Bob will learn at least one of the values $K_k^v$, he can learn the other via $K_k^{1-v} = \Delta \oplus K_k^v$. As you point out, learning both wire labels is a violation of the privacy property.

While it is possible to use something like one-time pad for garbled circuits (see for example this paper of Kolesnikov), it requires much more care, and is not typically used in practice.

Better to think of a garbled gate as a random permutation of the following 4 ciphertexts:

$ \qquad \textsf{Enc}_{A_0,B_0}(C_0), \quad \textsf{Enc}_{A_0,B_1}(C_0), \quad \textsf{Enc}_{A_1,B_0}(C_0), \quad \textsf{Enc}_{A_1,B_1}(C_1)$

where $\textsf{Enc}$ is a legitimate encryption scheme. (I like to use $A_0,A_1$ as wire labels on the left input wire, $B_0,B_1$ for wire labels on the right input wire, and $C_0,C_1$ for output wire labels) In particular, knowing $Y$ and $\textsf{Enc}_K(Y)$ shouldn't allow you to solve for $K$ as it does in one-time pad.

To answer your bigger question about hiding the circuit. It is not required that the circuit be hidden from Bob. The standard setting of two-party computation has the parties first agreeing on a function to compute. The inputs to the function are to be hidden, but not the function itself. Furthermore, most practical garbled circuit constructions use the "Free XOR" optimization, and this requires Bob to behave differently for XOR gates vs AND gates (hence he must know the type of each gate).