Single-Server Private Information Retrieval with Sublinear Amortized Time
summary
Gives concrete constructions: under DDH/QR/DCR/LWE a single-server PIR achieves n^{3/4} amortized server time with client storage n^{3/4} and supports ~n^{1/4} adaptive queries; using gate-by-gate FHE the scheme improves to √n server time and √n client storage for √n queries. Builds a generic compiler (permute + q chunks) from single-query sublinear PIR and an FHE sorting-network circuit, achieves malicious security, and proves a lower bound S·T ≥ n so the FHE tradeoff is essentially optimal.
AI-written summary · about
chapters (6)
- 0:00Introduction
- 0:23Adaptive PIR Construction
- 29:42Optimality and Trade-offs
- 31:18FHE Based Scheme
- 36:27Lower Bounds
- 38:50Conclusion and Future Work
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
01h 11mPrivate Information Retrieval and Oblivious RAM
34mPrivate Information Retrieval: Chasing Capacity with Algebraic Codes
34mEfficient Robust Private Aggregation for DP
41mTalk by Elaine Shi (Carnegie Mellon University)