2026-08-14T00:27:36Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:27104 2026-08-12T06:00:27Z ddc:004 open_access

Adaptive Garbled Circuits and Garbled RAM from Non-Programmable Random Oracles Barnum, Cruz Heath, David Kolesnikov, Vladimir Ostrovsky, Rafail Adaptive Garbling Garbled RAM Random Oracle Model 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Cruz Barnum and David Heath and Vladimir Kolesnikov and Rafail Ostrovsky 2026 Is Part Of LIPIcs, Volume 385, 7th Conference on Information-Theoretic Cryptography (ITC 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ITC.2026.11 urn:nbn:de:0030-drops-271048 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITC.2026.11 eng https://creativecommons.org/licenses/by/4.0/legalcode