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 |