half-gates in garble circuit

Question

Recently I've been reading papers about MPC protocol, but when I read the paper by Zahur, S., M. Rosulek, and D. Evans. 2015 Two Halves Make a Whole- Reducing Data Transfer in Garbled Circuits Using Half Gates. The researchers proposed the state-of-art technology of optimizing garbled circuit.

Their main idea is to divide the AND gate into two half-gates. \begin{align*} c &= a \land b \\ &= a \land (r+r+b) \\ &= (a \land r)+(a \land (r+b)) \end{align*}

As far as I can see, it seems that the generator half-gate is enough for an AND gate. based on the input value that the garbler has, it produce the garbled table: $H(B)+C,H(B+R)+C+aR$. the evaluator can calculate the output label based on the label of its own input $B$ or $B+R$, and that's it, that's all for an AND gate.

I don't see why the authors construct the gate by combining two half gates.

I don't really see the intuition behind this construction, after reading the book A Pragmatic Introduction to Secure Multi-Party Computation written by David Evans, he wrote:

It remains to show how the two half gates can be used to evaluate a gate vc = va ^ vb, in a garbled circuit, where neither party can know the semantic value of either input`.

As classical Yao circuit, two-party have their own input independently, why he assumes that they both know neither input?

Answer 1

As classical Yao circuit, two-party have their own input independently, why he assumes that they both know neither input?

Consider the circuit $(a_1 \oplus b_1) \land (a_2 \oplus b_2)$ where Alice's input is $a_1,a_2$ and Bob's input is $b_1,b_2$. The bits going into the AND gate are not known to either party, so you can't use one of the half-AND constructions.

Parties know their inputs to the circuit but not the input to every gate in the circuit. The bits going into an internal gate in the circuit can be influenced by both parties' inputs, so that neither knows the value in the clear. (You can indeed replace AND gates with half-AND gates at the input layer of a circuit.)