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.