Yes, There is an Oblivious RAM Lower Bound!
summary
Shows a concrete lower bound: any online oblivious RAM that hides access patterns against a polynomial-time adversary must incur Ω(log n / m) bandwidth overhead (specializing to Ω(log n) when client memory m is constant), even allowing arbitrary bit-level tricks and client memory up to n^{1−ε}. Proof uses cell-probe interval counting and an encoding argument, building specific alternating write-then-read red/blue sequences whose indistinguishability forces many distinct probes, so the total probe cost sums to the claimed bound.
AI-written summary · about
chapters (11)
- 0:00Intro
- 0:41Oblivious RAM, Model (2/2)
- 4:48Bandwidth Overhead
- 5:52Upper Bounds
- 7:03Lower Bounds: log(N)
- 8:572016: log(N)???
- 12:39Proof
- 20:34Theorem
- 24:34Summary
- 25:47Open Problem
- 26:51Conclusion
related talks
30mUsing Data-Oblivious Algorithms for Private Cloud Storage Access
33mObfuscation with Constant Multiplicative Size Overhead
15mH2O2RAM: A High-Performance Hierarchical Doubly Oblivious RAM
28mIndistinguishability Obfuscation for Turing Machines with Unbounded Memory
21mWhen Oblivious is Not: Attacks against OPAM
31mRemote Memory-Deduplication Attacks
27mDifferentially Oblivious Turing Machines
34mCapacity Inversion and MPC over Elastic Noisy Channels