Welcome to the resource topic for 2023/1527
Title:
Adaptive Garbled Circuits and Garbled RAM from Non-Programmable Random Oracles
Authors: Cruz Barnum, David Heath, Vladimir Kolesnikov, Rafail Ostrovsky
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 much 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 GC techniques.
As our main goal and as an 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 the popular half-gates, and it is adaptively secure from NPRO.
ePrint: https://eprint.iacr.org/2023/1527
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .