## On the Security of the "Free-XOR" Technique

*Seung Geol Choi, Jonathan Katz, Ranjit Kumaresan, Hong-Sheng Zhou*

TCC 2012 [pdf] [bibtex]

This paper shows that a natural variant of correlation-robustness (IKNP03) does not suffice to prove the security of the free-XOR technique KS08.

With free-XOR, a garbled gate is constructed using ciphertexts of the form `⚠️{$H(A\|B\|T) \oplus C$}`

, where `⚠️{$A,B$}`

are incoming wire labels and `⚠️{$C$}`

is an outgoing wire label. When using free-XOR, wire labels on each wire are correlated via a secret and global offset `⚠️{$\Delta$}`

. Hence we encounter situations where ciphertexts take the form `⚠️{$H(A \oplus \Delta\|B \oplus \Delta\|T) \oplus C \oplus \Delta$}`

, where `⚠️{$A,B,C,T$}`

are all known and `⚠️{$\Delta$}`

is secret. The appearance of `⚠️{$\Delta$}`

both inside and outside of the call to `⚠️{$H$}`

require a stronger property of `⚠️{$H$}`

than simple correlation robustness. Indeed, a black-box separation between free-XOR security and correlation robustness is shown.

The authors propose a slightly stronger notion called **circular 2-correlation robustness**. A function `⚠️{$H$}`

satisfies this security definition if, for random choice of `⚠️{$\Delta$}`

, it is infeasible to distinguish the following oracle from a random function:

`⚠️{$\mathcal{O}_\Delta(A,B,T,b_1,b_2,b_3) = H(A \oplus b_1 \Delta \| B \oplus b_2 \Delta \| T) \oplus b_3 \Delta$}`

The authors prove that the free-XOR garbling scheme of KS08 is secure when instantiated using a circular 2-correlation robust function.

### See Also:

### Categories:

- Home page
- All papers, by:
- .. category
- .. author names
- .. publication date
- .. recently added
- .. recently updated

- Glossary
- About
- Just getting started in MPC?
- Guidelines
- Todo List

Search Papers

Bibliography Categories