Paper 2023/1528

Unmodified Half-Gates is Adaptively Secure - So is Unmodified Three-Halves

Abstract

Circuit garbling is a crucial cryptographic tool in many practical privacy-preserving applications due to two features: efficiency - it can be constructed in the random permutation model, allowing hardware acceleration; adaptivity - the majority of the communication can be transmitted offline before inputs are known. However, existing adaptive garbling schemes can only be proven in the random oracle model at best, leading to 20$\times$ slowdown. In this work, we apply analysis often used for symmetric-key primitives to adaptive garbling and show that two practically deployed selective-secure schemes, half-gates and three-halves, already satisfy adaptive security without any modification to their implementations or security assumptions. We show how to bound an adaptive advantage via an adversary-dependent statistical distance and analyze this distance by adapting the H-coefficient technique to remove this adversary dependence. For real-life systems, our result solves the security concern about the heuristic of using the two schemes with offline communication. As a byproduct, we discuss when we can further offload the decoding information of garbled outputs to the offline phase, leading to a separation result.