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?