References & Further Reading
References
- H. Sun and S. A. Jafar, The Capacity of Private Information Retrieval, 2017
The headline result of this chapter. Settles the 22-year-old open problem of PIR capacity with both achievability and matching converse. Should be read in full.
- B. Chor, O. Goldreich, E. Kushilevitz, and M. Sudan, Private Information Retrieval, 1995
The original PIR paper. Introduced the problem formulation and the first sub-trivial-rate construction. Foundational reference.
- A. Beimel, Foundations of Cryptography: Private Information Retrieval, 2007
Survey of pre-Sun-Jafar PIR results, including computational PIR, multi-server PIR, and PIR-related cryptographic primitives. Useful background context.
- R. Tajeddine and S. El Rouayheb, Private Information Retrieval from MDS Coded Data in Distributed Storage Systems, 2018
Coded-storage PIR: when files are MDS-coded across databases instead of replicated. Forward reference to Chapter 14 §14.1.
- H. Sun and S. A. Jafar, The Capacity of Private Information Retrieval with Colluding Databases, 2018
$T$-colluding PIR: privacy against collusion of $T$ databases. Forward reference to Chapter 14 §14.2.
- Q. Wang and M. Skoglund, Symmetric Private Information Retrieval from MDS Coded Distributed Storage, 2019
Symmetric PIR (two-sided privacy). Forward reference to Chapter 14 §14.3.
- Y.-P. Wei, K. Banawan, and S. Ulukus, Cache-Aided Private Information Retrieval with Unknown and Uncoded Prefetching, 2019
Cache-aided PIR with unknown caches. Forward reference to Chapter 15.
- K. Wan, D. Tuninetti, and G. Caire, Fundamental Limits of Caching for Demand Privacy Against Colluding Users, 2021
CommIT-group cache-aided coded-caching with demand privacy. Tagged in Chapter 15 as the primary commit_contribution; forward referenced here.
- E. Kushilevitz and R. Ostrovsky, Replication is Not Needed: Single Database, Computationally-Private Information Retrieval, 1997
Computational PIR with a single database. Different threat model (computational vs. information-theoretic) but related engineering goal. Useful contrast.
- S. Yekhanin, Private Information Retrieval, 2010
Accessible survey of PIR for a CS-broad audience. Good complement to Beimel's more technical survey.
- N. Raviv and I. Tamo, Private Information Retrieval is Graph-Based Replication Systems, 2018
Graph-theoretic perspective on PIR with partially-replicated storage. Useful for understanding the storage-vs-rate trade-offs.
- R. Freij-Hollanti, O. W. Gnilke, C. Hollanti, and D. Karpuk, Private Information Retrieval from Coded Databases with Colluding Servers, 2017
Combined coded-storage + $T$-colluding PIR. Relevant for Chapter 14's joint extensions.
Further Reading
Resources for going deeper into PIR, its extensions, and the underlying information theory.
Sun-Jafar capacity result, full treatment
Sun & Jafar, IEEE Trans. Inf. Theory, 2017
The headline paper. Reading the full proof (especially the converse via induction) is essential for understanding why $(1 + 1/N + \\cdots + 1/N^{K-1})^{-1}$ is the right answer.
PIR survey for theoretical CS
Yekhanin, *Private Information Retrieval*, CACM 2010
Accessible introduction with broad context beyond information-theoretic PIR. Useful for placing PIR among other privacy primitives (oblivious RAM, secure multi-party computation).
Coded computing for PIR
Tajeddine & El Rouayheb, IEEE T-IT 2018
Bridges PIR with the coded-computing framework of Part II. Useful for understanding the algebraic kinship between PIR and coded matrix multiplication.
Modern PIR — recent advances
Banawan & Ulukus, *Private Information Retrieval and Beyond*, monograph in preparation
Comprehensive treatment of post-Sun-Jafar PIR developments: $T$-colluding, SPIR, coded-storage, cache-aided, side- information variants.
Computational PIR (single-database)
Kushilevitz & Ostrovsky, *Replication is Not Needed*, FOCS 1997
The computational-PIR alternative. Relevant for production deployments where the non-colluding-databases assumption is unacceptable.