Oblivious RAM II
summary
Describes two concrete advances and what they actually build: an OnionORAM that achieves constant communication per access by shaving the usual log N factor at the cost of polylogarithmic block size (likely polylog³ N) and using additively homomorphic crypto (Damgård–Jurik / somewhat homomorphic); client and server work remain polylog N, rounds stay constant (responses ≈ 2·B). Active security uses Merkle trees for metadata plus small verification chunks (security‑parameter many) and ECC. The garbled‑RAM construction gives non‑interactive, reusable RAM execution where garbling and evaluation cost the RAM runtime; circularity in keys is resolved via identity‑based encryption or other fixes, writes use time‑stamped identities, and fully succinct variants require indistinguishability obfuscation and long proofs.
AI-written summary · about
chapters (11)
- 0:00Traditional ORAM Model
- 2:12ORAM (Server Computation)
- 11:49Recall: Tree ORAM
- 19:33Eviction in Tree ORAM
- 34:03Part II. Garbled RAM (no interaction)
- 45:17Let's try to prove security...
- 45:51Use security of 2nd garbled circuit
- 52:05How to allow writes?
- 54:03Private and Verifiable Output
- 55:38Part III: Succinct Garbled RAM
- 56:42State of the Art
related talks
28mNew Advances in Secure RAM Computation
35mOblivious RAM for MPC
01h 14mPrivate Information Retrieval and Oblivious RAM
01h 03mBeyond Boolean Circuits in Garbled Circuits
01h 11mPrivate Information Retrieval and Oblivious RAM
59mDoubly Efficient Private Information Retrieval and Fully Homomorphic RAM Computation from Ring LWE
25mEgalitarian Computing
51mObfuscation via GGH15 Encodings, 10 Years Later