Private information retrieval at 30: Achievements, disappointments, and open problems
summary
Survey of PIR’s 30-year arc: communication shrinks via private polynomial evaluation and homomorphic tools (communication ≈ n^{1/D}), and the derivatives trick halves needed servers by using Hermite interpolation. The big practical barrier is computation: Beimel–Ishai–Malkin forces linear server work if the database is stored raw, so fixes include skewed-popularity correctness, batching/online preprocessing (offline linear, online ≈ √n via parity hints), or encoding the DB (multi-server codes or ring‑LWE + Kedlaya‑Umans gives polylog queries but enormous precompute; e.g. ~$10B for 400MB). Open points: practical single‑server DEPIR and better lower bounds.
AI-written summary · about
chapters (7)
- 0:00Introduction and logistics
- 1:08PIR communication fundamentals
- 21:30The computational bottleneck
- 24:54Circumventing computation bounds
- 30:05Advanced PIR techniques
- 45:09Doubly efficient PIR
- 51:06Applications and future outlook
related talks
01h 04mDoubly Efficient Private Information Retrieval
43mSingle-Server Private Information Retrieval with Sublinear Amortized Time
59mDoubly Efficient Private Information Retrieval and Fully Homomorphic RAM Computation from Ring LWE
01h 14mPrivate Information Retrieval and Oblivious RAM
01h 11mPrivate Information Retrieval and Oblivious RAM
34mPrivate Information Retrieval: Chasing Capacity with Algebraic Codes
27mMetadata-private data transfer
34mEfficient Robust Private Aggregation for DP