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 , our garbling of is at most bits long, where 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 steps of a RAM program has size 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.