Private Information Retrieval and Oblivious RAM
Talkat Cryptography 10 Years Later: Obfuscation, Proof Systems, and Secure Computation Boot Camp 2025 · 2025-05-19..05-23·
summary
Survey condenses two concrete systems and their numbers: a tree/Circuit-ORAM implementation (used by Signal via a TEE but optimized to 20–50 microseconds per lookup, 200K qps on one machine, 6 servers reported vs a naïve linear-scan 500-server baseline) and a client-preprocessing PIR called Piano that uses only PRFs and achieves roughly sqrt(n) client space / compute / bandwidth, with 12 ms server compute and ~72–100 ms end-to-end in 16 ms ping networks (compute ~1000x faster than classical PIR).
AI-written summary · about
chapters (17)
- 0:00Introduction
- 0:21ORAM and PIR applications
- 7:22Security definitions
- 10:31Industry adoption limits
- 15:31ORAM and PIR implementations
- 20:28Linear scan impractical
- 23:06ORAM construction evolution
- 28:03Path ORAM explained
- 35:35ORAM deployment considerations
- 39:49Generic ORAM unnecessary
- 41:28PIR construction evolution
- 45:20Piano PIR preprocessing
- 56:35Piano query limits
- 59:42Piano performance
- 1:00:10RAM-model MPC overview
- 1:06:20Future directions
- 1:10:16Open questions and Q&A
related talks
01h 04mDoubly Efficient Private Information Retrieval
43mSingle-Server Private Information Retrieval with Sublinear Amortized Time
01h 06mOblivious RAM II
58mPrivate information retrieval at 30: Achievements, disappointments, and open problems
01h 15mOblivious RAM I
35mOblivious RAM for MPC
59mDoubly Efficient Private Information Retrieval and Fully Homomorphic RAM Computation from Ring LWE
34mPrivate Information Retrieval: Chasing Capacity with Algebraic Codes