OWF ⇒ garbled RAM (black-box)

Fully-black-box reduction · standard model · GLO15

Statement

If one-way functions exist, there is a garbled RAM scheme with polylogarithmic overhead that uses the one-way function only as a black box — GLO15.

Notes

• A garbled RAM from one-way functions came first, with strictly polylogarithmic overhead in space and time and a persistent garbled database, but it uses the one-way function in a non-black-box way — GLOS15, GLO15.
• The earlier construction of LO13 from one-way functions has a security proof that relies on a circular use of Yao garbled circuits and PRFs; IBE removes the circularity (IBE ⇒ garbled RAM) — GHL+14.
• GLO15 also give the first constant-round secure RAM computation protocol that uses one-way functions only as a black box, in the OT-hybrid model — GLO15.