# half-gates in garble circuit

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?

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.