CONCRETE-EFFICIENT GARBLING OF 3-INPUT GATES IN MINICRYPTFrom $3\lambda$ to $2.5\lambda$ Bits for 3-Input Gates

Abstract

Garbled circuits are a central technique for secure computation: a garbler encodes a Boolean circuit so that an evaluator can compute the circuit on encoded inputs while learning nothing beyond the prescribed output. Their practical cost is dominated by communication, so a long line of work has sought to shrink the data associated with each gate. In the current state of the art, free-XOR makes XOR gates communication-free, while a 2-input AND gate costs $1.5\lambda + O(1)$ bits, where $\lambda$ is the security parameter.

This work asks whether better concrete efficiency is possible by departing from the usual fan-in-2 representation. Any 3-input,1-output Boolean gate can be implemented with two AND gates and free XOR gates, at a worst-case cost of $3\lambda + O(1)$ bits. We instead directly garble every such gate using $2.5\lambda + O(1)$ bits. The construction is compatible with free-XOR, hides the gate being evaluated, and can be incorporated into existing efficient garbled-circuit systems.

Security is established in the random oracle model and, as in prior free-XOR constructions, under the circular correlation-robust hash assumption. For security parameters $\lambda \geq 48$, the resulting gate-hiding construction improves on previous approaches without increasing the evaluator's asymptotic workload.

Biography

Luojian Wei is a Ph.D. candidate at the Center on Frontiers of Computing Studies (CFCS) at Peking University, advised by Tianren Liu. His research spans cryptography, including secure multi-party computation, unclonable cryptography, and obfuscation.