Paper 2023/1527
Adaptive Garbled Circuits and Garbled RAM from Non-Programmable Random Oracles
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)
- 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
-
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} }