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