**
Garbled RAM Revisited
**

*
Craig Gentry,
Shai Halevi,
Steve Lu,
Rafail Ostrovsky;
Mariana Raykova,
Daniel Wichs
*

**
Abstract:
**

The notion of * garbled random-access machines* (garbled RAMs) was introduced by Lu and Ostrovsky (Eurocrypt 2013).
It can be seen as an analogue of Yao's garbled circuits, that allows a user to garble a RAM program directly, without performing the expensive step of converting it into a circuit.
In particular, the size of the garbled program and the time it takes to create and evaluate it are only proportional to its running time on a RAM rather than its circuit size.
Lu and Ostrovsky gave a candidate construction of this primitive based on pseudo-random functions (PRFs).

The starting point of this work is pointing out subtle circularity hardness assumption in the Lu-Ostrovsky construction. Specifically, the construction requires a complex“circular„ security assumption on the underlyingYao garbled circuits and PRFs. We then proceed to a abstract, simplify and generalize the main ideas behind the Lu-Ostrovsky Constructions. Our first construction breaks the circularity by replacing the
PRF-based encryption in the Lu-Ostrovsky construction by *Identity-based encryption (IBE)*. The result retains the same asymptotic performance characteristics of the original Lu-Ostrovsky construction, namely overhead of Ο(poly(Κ)poly log(n) (with Κ the security parameter and n the data size). Our second construction breaks the circularity assuming only te existence of one way functions, but with overhead
Ο(poly(Κ)n^{ε} ) for any constant ε > ο, This construction works by adaptively “revoking” the PRF at selected points, and using a delicate recursion argument to get successively better performance characteristics. It remains as an interesting open problem to achieve an overhead of
poly( Κ)polylog(n) assuming only the existence of one-way functions.

**comment:**
EUROCRYPT 2014 PP: 405-422

Fetch PDF file of the paper

Back to Publications List |