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
Signal runs Path ORAM for private contact discovery and achieves single-query latencies of 20–50 microseconds and ~200k qps on one machine; a reworked ORAM implementation reports 20x–100x speedups over prior deployments. Two-party ORAM (PicoGRAM) shows ~30–40 ms online and 300–600 ms end-to-end. For PIR the Piano client-preprocessing scheme serves a 100 GB / 1.6B-record DB with ~12 ms server compute (72 ms total on a 16 ms RTT) using only PRFs and sqrt(n) work and storage.
AI-written summary · about
chapters (17)
- 0:00Introduction
- 2:34Access pattern leakage matters
- 6:28ORAM vs PIR differences
- 9:46Deployments and trusted hardware
- 14:51ORAM performance state
- 21:58How tree-based ORAMs work
- 24:03ORAM construction intuition
- 33:57Path ORAM explained
- 36:07Practical ORAM in memory
- 37:56Generic ORAM not needed
- 39:43Classical PIR limitations
- 43:20Piano client preprocessing PIR
- 54:32Piano summary and limits
- 57:42RAM model MPC and garbled RAM
- 1:00:12Open questions for schemes
- 1:03:25Future directions for ORAM/PIR
- 1:07:03Q&A
related talks
01h 15mOblivious RAM I
58mPrivate information retrieval at 30: Achievements, disappointments, and open problems
35mOblivious RAM for MPC
01h 04mDoubly Efficient Private Information Retrieval
01h 06mOblivious RAM II
43mSingle-Server Private Information Retrieval with Sublinear Amortized Time
59mDoubly Efficient Private Information Retrieval and Fully Homomorphic RAM Computation from Ring LWE
35mLower-Bounds on Public-Key Operations in PIR