Private Information Retrieval: Chasing Capacity with Algebraic Codes
summary
Presents a coding-theory approach that frames queries as codewords and uses a star product of storage and query codes to turn responses into decodable codewords plus controlled “errors.” Proves an asymptotic PIR capacity and shows a finite-file capacity bound holds under a technical full support-rank condition, explains a two-file counterexample that violates that condition, and gives constructive schemes with drastically smaller sub-packetization and extensions to adversaries, stragglers, algebraic-geometry codes and quantum communication.
AI-written summary · about
chapters (10)
- 0:00Introduction
- 1:52What is PIR
- 3:15PIR research history
- 5:48PIR toy example
- 9:46PIR collusion protection
- 11:41PIR capacity and rate
- 13:28PIR conjectures and counterexamples
- 22:43Star product PIR scheme
- 27:00Full support-rank criterion
- 30:12PIR extensions
related talks
01h 04mDoubly Efficient Private Information Retrieval
58mPrivate information retrieval at 30: Achievements, disappointments, and open problems
01h 14mPrivate Information Retrieval and Oblivious RAM
43mSingle-Server Private Information Retrieval with Sublinear Amortized Time
39mGilbert and Varshamov meet Johnson: List Decoding Nearly-Optimal Binary Codes
01h 09mNoisy Connections: A Survey of Interactive Coding and Its Borders with Other Topics
35mLower-Bounds on Public-Key Operations in PIR
04mError-Correcting Codes: Theory and Practice