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 by another circuit 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 (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 proved 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: