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.
Category / Keywords: foundations / Secure Computation, Oblivious RAM, Garbled RAM, Garbled Circuits Original Publication (with major differences): IACR-EUROCRYPT-2014 Date: received 5 Feb 2014, last revised 5 Feb 2014 Contact author: danwichs at gmail com Available format(s): PDF | BibTeX Citation Note: A merged version of this work and Part II appears in Eurocrypt 2014 Version: 20140205:144735 (All versions of this report) Short URL: ia.cr/2014/082 Discussion forum: Show discussion | Start new discussion