## 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