# How OR gates are garbled in recent optimizations techniques like free XOR, Half Gates?

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.

## 1 Answer

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.

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