Paper 2014/082

Garbled RAM Revisited, Part I

Craig Gentry, Shai Halevi, Mariana Raykova, and 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.

Note: A merged version of this work and Part II appears in Eurocrypt 2014

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
A major revision of an IACR publication in EUROCRYPT 2014
Keywords
Secure ComputationOblivious RAMGarbled RAMGarbled Circuits
Contact author(s)
danwichs @ gmail com
History
2014-02-05: revised
2014-02-05: received
See all versions
Short URL
https://ia.cr/2014/082
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2014/082,
      author = {Craig Gentry and Shai Halevi and Mariana Raykova and Daniel Wichs},
      title = {Garbled RAM Revisited, Part I},
      howpublished = {Cryptology ePrint Archive, Paper 2014/082},
      year = {2014},
      note = {\url{https://eprint.iacr.org/2014/082}},
      url = {https://eprint.iacr.org/2014/082}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.