Paper 2026/1297

Breaking the $\Omega(|C|\kappa)$ Barrier on Garbled Circuit Size in the Random Oracle Model

Abstract

In this paper, we study garbled circuits in the random oracle model against a computationally unbounded adversary with $T$ queries to a (programmable) random oracle. From Yao's garbled circuits (SFCS 1986) to Three-Halves (CRYPTO 2021), the garbled circuit size has been reduced from $8|C|(\log T+\kappa)$ bits to $1.5|C|(\log T+\kappa)$ bits for achieving a statistical error of $2^{-\kappa}$, where $|C|$ is the circuit size and $\kappa$ is the statistical security parameter. However, no known result achieves $o(|C|\kappa)$ bits of garbled circuit size by now, and it is widely believed that a garbled circuit must have $\Omega(|C|\kappa)$ bits in the random oracle model. In this work, we present the first garbling scheme that achieves $o(|C|\kappa)$ bits of garbled circuit size in the random oracle model. In particular, for a circuit $C$ of size $|C|$ and depth $D$, the achieved garbled circuit size is $O(|C|\log T+D\kappa^2\log T)$ bits. This breaks the long-standing $\Omega(|C|\kappa)$ barrier on the garbled circuit size. We extend our garbling scheme to a maliciously secure two-party computation protocol with communication of $O(|C|\log T+D(\log T+\kappa)^2\log T+{\sf poly}(\kappa,\log T))$ bits against any $T$-query adversary assuming parallel oblivious transfers and a (programmable) random oracle. The protocol only requires 1 OT round and 3 one-way communication rounds. If only requiring one of the two parties to have output, a similar communication complexity can be achieved for constructing a non-interactive secure computation (NISC) protocol, which only relies on the preprocessing of bit-OT correlations and a random oracle. Compared to a concurrent work on NISC by Ishai et al. (EUROCRYPT 2026) in the same setting, we achieve a better amortized communication cost per gate at the cost of an additional term related to the circuit depth. The NISC protocol with a similar communication cost can also be constructed from a (slightly stronger version of) semi-malicious 2-round OT protocol.