Yao's Garbled Circuit- Why does Alice need to rearrange the circuit?

Question

My understanding of Yao's Garbled Circuit (based mostly on this summary) is as follows:

Alice creates a garbled circuit based on the function f to be computed. She then hard-codes her input into the circuit and rearranges the gates in such a way that Bob will not be able to figure out what the circuit does. She then assigns a pair of random keys, $K^0_i, K^1_i$ to each wire $w_i$. She sends Bob four (unlabeled, shuffled) values $X_s^a,X_s^b,X_s^c,X_s^d$ for each gate $g_s$. These $X_s$ values are chosen such that if Bob knows the keys $K_i^{v_i}$ and $K_j^{v_j}$ for the two input wires of $g_s$ with values $v_i$ and $v_j$ then he can calculate the key $K_k^{v_k}$. Specifically, he does this by taking the XOR of $K_i^{v_i}$ and $K_j^{v_j}$ and each $X_s$ value. One of these four results will be $K_k^{v_k}$, the others will be meaningless random bits. Alice gives Bob the values $AUTH(K_k^0),AUTH(K_k^1)$ for some one-way trapdoor hash function AUTH. Thus, Bob can figure out which of the four values is not random bits.

I don't understand why Alice needed to hard-code her input and rearrange the gates. Could she not have just given Bob the circuit as is and the keys to her inputs? Except for his own input wires and wires determined from them, Bob does not know whether the key on a wire represents the wire being in the state 0 or the state 1. So even if he knows the function he is computing (what the circuit does) he should not be able to figure out what the values are of this function.

I also realize from this question that the keys as well as the X values would have to be generated again for a second computation. But I don't see why the structure of the circuit itself needs to change.

Answer 1

Alice does not need to hard-code her input and does not need to shuffle the gates (it is only necessary to shuffle the ciphertexts inside each gate). Bob needs to hold a key on every input wire. For the input wires associated with Alice's input, she can just send the appropriate key (this reveals nothing since both the 0 and 1 values are just random).

Answer 2

I don't understand why Alice needed to hard-code her input and rearrange the gates. Could she not have just given Bob the circuit as is and the keys to her inputs?

Alice needs to hardcode her input because both parties must NOT learn each other's input values. The whole point of the Garbled Circuit is to devise a way where both parties will learn the wanted result without ever learning anything other than their own values. Thus, if Alice gave her inputs to Bob the whole protocol loses its point.

But, because without Alice's values there can be no computation, we need to find a way where Alice will add her values but Bob will understand nothing of them. Thus, Alice hardcodes her values into the system and shuffles the order so that Bob can understand nothing.

Since every boolean circuit can be expressed as a truth table, if Alice didn't shuffle the order, then - in a simple circuit - it should be relatively easy for Bob to guess Alice's values.

Check this example.