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