Paper 2023/1527

Adaptive Garbled Circuits and Garbled RAM from Non-Programmable Random Oracles

Cruz Barnum, University of Illinois Urbana-Champaign
David Heath, University of Illinois Urbana-Champaign
Vladimir Kolesnikov, Georgia Institute of Technology
Rafail Ostrovsky, University of California, Los Angeles
Abstract

Garbled circuit techniques that are secure in the adaptive setting -- where inputs are chosen after the garbled program is sent -- are motivated by practice, but they are notoriously difficult to achieve. Prior adaptive garbling is either impractically expensive or encrypts the entire garbled program with the output of a programmable random oracle (PRO), a strong assumption. We present a simple framework for proving adaptive security of garbling schemes in the non-programmable random oracle (NPRO) model. NPRO is a milder assumption 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. As our main application of the framework, we construct and prove adaptively secure a garbling scheme for tri-state circuits, a recently proposed circuit model that captures both Boolean circuits and RAM programs (Heath et al., Crypto 2023). For a given TSC $C$, our garbling of $C$ is at most $|C|\cdot \lambda$ bits long, where $\lambda$ is the security parameter. This implies both an adaptively secure garbled Boolean circuit scheme, as well an adaptively secure garbled RAM scheme where the garbling of $T$ steps of a RAM program has size $O(T \cdot \log^3 T \cdot \log \log T \cdot \lambda)$ bits. Our scheme is concretely efficient: its Boolean circuit handling matches the performance of half-gates, and it is adaptively secure from NPRO.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Preprint.
Keywords
Adaptive GarblingGarbled RAMMulti-Party ComputationNon-Programmable Random Oracles
Contact author(s)
cruzjb2 @ illinois edu
daheath @ illinois edu
kolesnikov @ gatech edu
rafail @ cs ucla edu
History
2024-09-30: last of 2 revisions
2023-10-06: received
See all versions
Short URL
https://ia.cr/2023/1527
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2023/1527,
      author = {Cruz Barnum and David Heath and Vladimir Kolesnikov and Rafail Ostrovsky},
      title = {Adaptive Garbled Circuits and Garbled {RAM} from Non-Programmable Random Oracles},
      howpublished = {Cryptology {ePrint} Archive, Paper 2023/1527},
      year = {2023},
      url = {https://eprint.iacr.org/2023/1527}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.