Summary: A. Yao’s garbled circuit (GC) technique [How to generate and exchange secrets, IEEE 27th Ann. Symp. FOCS 1986, 162–167 (1986)] is a powerful cryptographic tool which allows to “encrypt” a circuit $$C$$ by another circuit $$\hat{C}$$ in a way that hides all information except for the final output. Yao’s original construction incurs a constant overhead in both computation and communication per gate of the circuit $$C$$ (proportional to the complexity of symmetric encryption). V. Kolesnikov and T. Schneider [ICALP 2008, Lect. Notes Comput. Sci. 5126, 486–498 (2008; Zbl 1155.94374)] introduced an optimized variant that garbles XOR gates “for free” in a way that involves no cryptographic operations and no communication. This variant has become very popular and has lead to notable performance improvements. The security of the free-XOR optimization was originally proved in the random oracle model. Despite some partial progress [S. G. Choi et al., TCC 2012, Lect. Notes Comput. Sci. 7194, 39–53 (2012; Zbl 1303.94075)], the question of replacing the random oracle with a standard cryptographic assumption has remained open. We resolve this question by showing that the free-XOR approach can be realized in the standard model under the learning parity with noise (LPN) assumption. Our result is obtained in two steps:
1.
We show that the random oracle can be replaced with a symmetric encryption, which remains secure under a combined form of related-key (RK) and key-dependent message (KDM) attacks.
2.
We show that such a symmetric encryption can be constructed based on the LPN assumption.
As an additional contribution, we prove that the combination of RK and KDM security is nontrivial in the following sense: There exists an encryption scheme which achieves RK security and KDM security separately, but breaks completely at the presence of combined RK-KDM attacks.

### MSC:

 94A60 Cryptography

### Citations:

Zbl 1155.94374; Zbl 1303.94075

TASTY; VMCrypt
Full Text: