Doubly Efficient Private Information Retrieval
summary
Single‑server PIR that makes both client and server efficient uses a one‑time preprocessing and a new hardness conjecture: encode the n‑bit database via a Reed–Muller low‑degree extension, apply a secret permutation, and answer each query by probing about λ·√n code symbols (λ = security parameter) so the client decodes with polylog work while the server stores superlinear data and serves ~λ√n lookups. Constructions date to 2017, rest on a permute‑then‑query hardness assumption (indistinguishability of permuted low‑degree vs random samples); lower bounds show S·T ≥ N log N in some models.
AI-written summary · about
chapters (10)
- 0:00Start
- 4:46Public Key Cryptography Assumptions
- 9:48Pre-Processing on the Database
- 11:32Oblivious Ram
- 25:21Dream Data Structure
- 25:32What Is this Dream Data Structure
- 29:23The Syntax
- 41:10Low Degree Parametric Curves
- 49:14Security
- 54:59Open Questions
related talks
58mPrivate information retrieval at 30: Achievements, disappointments, and open problems
59mDoubly Efficient Private Information Retrieval and Fully Homomorphic RAM Computation from Ring LWE
01h 14mPrivate Information Retrieval and Oblivious RAM
35mLower-Bounds on Public-Key Operations in PIR
34mPrivate Information Retrieval: Chasing Capacity with Algebraic Codes
01h 11mPrivate Information Retrieval and Oblivious RAM
27mMetadata-private data transfer
34mEfficient Robust Private Aggregation for DP