IBE ⇒ garbled RAM

Free reduction · standard model · GHL+14

Statement

If IBE exists, there is a garbled RAM scheme with $\mathrm{poly}(\lambda )\cdot \mathrm{polylog}(n)$ overhead for databases of $n$ words — GHL+14.

Notes

• The construction resolves a circularity in LO13, whose garbled RAM from one-way functions has a security proof relying on a circular use of Yao garbled circuits and PRFs — GHL+14.
• The Eurocrypt 2014 paper merges two parts: Part I, by Gentry, Halevi, Raykova and Wichs, gives the IBE construction, and Part II, by Lu and Ostrovsky, avoids the circularity from one-way functions alone with overhead $\mathrm{poly}(\lambda )\cdot \min (t,n^{\epsilon })$ for any constant $\epsilon >0$, where $t$ is the running time — GHL+14.
• Known garbled RAM realizations before GLO15 use the underlying primitives in a non-black-box way; GLO15 build garbled RAM from one-way functions used only as a black box (OWF ⇒ garbled RAM (black-box)) — GLO15.