5
$\begingroup$

I am a research student and I have been studying garbled circuits, specifically its optimization techniques. However, in every research paper i have encountered, the researchers have only shown how to garble an AND gate and XOR gates. The circuits do contain OR (or don't they?), my question is how an OR gate will be garbled in Half gates and Free XOR techniques scenario? Any help in this regard would be highly appreciated.

$\endgroup$
5
$\begingroup$

Usually, only AND gates and XOR gates are considered in garbled circuit schemes, because they form a complete basis for boolean circuit - id est, any boolean circuit can be written only with XOR gates and AND gates. In particular, you can implement an OR gate with a single AND gate and only XOR gates, using the fact that $a \text{ OR } b = \text{not }((\text{not } a) \text{ AND } (\text{not } b))$, and $\text{not } x = 1 \text{ XOR } x$. Therefore, with the latest scheme which garbles AND gates with two ciphertexts, and where XOR gates are for free, garbling an OR gate uses only two ciphertexts, exactly as an AND gate.

$\endgroup$
2
  • 2
    $\begingroup$ You can also write $a | b = a \oplus b \oplus (a \wedge b)$. ;) $\endgroup$
    – Biv
    Feb 28 '17 at 11:59
  • $\begingroup$ Right, it's even simpler that way :) $\endgroup$ Feb 28 '17 at 12:38

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.