2
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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.)

| improve this answer | |
$\endgroup$
  • $\begingroup$ thanks for Your reply. Yes, I think under the simplest situation such as only evaluating an AND gate, a generator half-gate is enough. But when it comes to a group of circuits, and when there is an AND gate in the middle, no one knows the semantic value of both inputs on the two wires. so the assumption made here is fair and pratical, we do need another gate to make a whole AND gate. $\endgroup$ – Wang Linger Oct 15 '19 at 3:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.