Adaptive Garbled Circuits and Garbled RAM from Non-Programmable Random Oracles
Cruz Barnum, David Heath, Vladimir Kolesnikov, Rafail Ostrovsky
Abstract:
Garbled circuit techniques secure in the adaptive setting - where inputs are chosen after a garbled program is sent - are motivated by practice, but they are difficult to achieve. Prior adaptive garbling is either impractically expensive or encrypts the garbled program with the output of a programmable random oracle (PRO). This latter approach introduces a strong model and incurs computational overhead.
We present a simple framework for proving adaptive security of garbling schemes in the non-programmable random oracle (NPRO) model. NPRO is a milder model than PRO, and it is close to the assumption required by the widely used Free XOR extension. Our framework is applicable to a number of existing GC techniques, which are proved adaptively secure without modification (and hence incurring no overhead).
As our main application, we construct and prove adaptively secure a garbling scheme for tri-state circuits, a model that captures both Boolean circuits and RAM programs (Heath et al., Crypto 2023). For TSC C, our garbling of C is at most |C|⋅ λ bits long, for security parameter λ. This implies both an adaptively secure garbled Boolean circuit scheme, and an adaptively secure garbled RAM scheme where the garbling of a T-step RAM program has size O(T ⋅ log³ T ⋅ log log T ⋅ λ) bits.
Our scheme is concretely efficient: its Boolean circuit handling matches the performance of half-gates, and it is adaptively secure from NPRO.
comment:
ITC 2026: 11:1-11:21
Fetch PDF file of the paper