Welcome to the resource topic for 2014/082
Title:
Garbled RAM Revisited, Part I
Authors: Craig Gentry, Shai Halevi, 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 a subtle yet difficult-to-overcome issue with the Lu-Ostrovsky construction, that prevents a proof of security from going through. Specifically, the construction requires a complex “circular” use of Yao garbled circuits and PRFs. As our main result, we show how to remove this circularity and get a provably secure solution using identity-based encryption (IBE). We also abstract out, simplify and generalize the main ideas behind the Lu-Ostrovsky construction, making them easier to understand and analyze. In a companion work to ours (Part II), Lu and Ostrovsky show an alternative approach to solving the circularity problem. Their approach relies only on the existence of one-way functions, at the price of higher overhead. Specifically, our construction has overhead \poly(k)\polylog(n) (with k the security parameter and n the data size), while the Lu-Ostrovsky approach can achieve overhead \poly(k)n^\eps for any constant \eps>0. It remains as an open problem to achieve an overhead of \poly(k)\polylog(n) assuming only the existence of one-way functions.
ePrint: https://eprint.iacr.org/2014/082
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 .