Garbling XOR Gates “For Free” in the Standard Model

Yao’s Garbled Circuit (GC) technique 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). Kolesnikov and Schneider (ICALP 2008) 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 proven in the random oracle model. Despite some partial progress (Choi et al., TCC 2012), 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:

–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; and

–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 non-trivial: There exists an encryption scheme which achieves both RK security and KDM security but breaks completely at the presence of combined RK-KDM attacks.