On the Security of the "Free-XOR" Technique

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:

KMR14

Categories:

Garbling