Overview

Private information retrieval

Protocols that let a client fetch one entry of a public database held by one or more servers without revealing to the servers which entry it wants.

What it is

A database of $N$ entries sits on one or more servers. A client wants entry $i$ and must not reveal $i$ to any server. Downloading the whole database is always private; private information retrieval (PIR) asks for less communication and, in later work, for less server computation. The problem is due to .

Two independent choices define a setting: how many servers hold copies of the database, and what kind of privacy is required. Information-theoretic privacy means each server's view is independent of $i$ , even for an unbounded server. Computational privacy means no efficient server can tell two indices apart, under a hardness assumption.

	Information-theoretic privacy	Computational privacy
One server	Impossible: privacy forces sending about the whole database ()	From hardness assumptions, first quadratic residuosity (), today mostly LWE or Ring-LWE
Two or more servers that do not collude	$O (N^{1/3})$ bits with two servers (), subpolynomial with matching-vector codes (, )	Lightweight schemes from one-way functions with distributed point functions ()

Core notions

What is measured

Communication: bits exchanged per query; the trivial solution sends $N$ entries.
Rate: entry size divided by response size; rate near 1 means the answer is barely longer than the entry.
Online server work: computation per query. Without preprocessing it is at least linear in $N$ , because a server that skips an entry learns that it was not requested ().
Server storage: what the server keeps besides the database, such as an encoded copy of it.
Client state: what a client keeps between queries, such as a hint about the database or a secret key.

Preprocessing, the way around linear work

None: the server stores only the database and reads all of it for every query.
Client-specific state: each client fetches a private hint once and then queries in sublinear time (); hints go stale when the database changes.
Client-independent hint: one public hint serves every client and makes the online step fast, though still linear ().
Silent: the server prepares alone and clients download nothing ahead of the query ().
Server public preprocessing: the server encodes the database once and then answers anyone in sublinear time while clients keep nothing; this is doubly efficient PIR, or DEPIR ().

Main approaches

Matching-vector codes: replicated databases queried through matching-vector codes give subpolynomial communication with three or more servers () and with two (), with information-theoretic privacy.
Distributed point functions: compact secret shares of a point function give lightweight two-server PIR with computational privacy ().
Homomorphic query compression: the client encrypts a selection vector under (Ring-)LWE and one server computes the inner product homomorphically (, ).
Matrix–vector protocols with a shared hint: LWE-based schemes whose online step runs at memory speed (), and successors that drop the hint (, , , ).
Client preprocessing with sublinear online time: pseudorandom sets give about $N$ server time per query, with two servers () or one (, , , ).
Server preprocessing (DEPIR): polylogarithmic online time after $O (N^{1 + ε})$ preprocessing under Ring-LWE (), and an information-theoretic multi-server variant ().

Notation used in the comparison table

Parameters below occur in efficiency or security bounds. Each meaning is scoped to its stated regime. Measured quantities are named in words; protocol objects are defined where used. Source aliases do not equate different regimes.

Symbol	Meaning	Regime	Paper aliases
N	Number of addressable database records.	Index PIR; bit-database results require one-bit records.	writes n; writes n; writes N; writes n; writes n; writes n
d	Record or retrieved-block length in bits.	Block/record PIR.	writes d; writes b
k	Number of servers.	Replicated multi-server PIR.	writes ℓ
λ	Computational security parameter.	Computational PIR.	writes k; writes κ
ε	Fixed positive exponent/slack parameter.	Preprocessing or sublinear-work tradeoffs.	writes ε
c	Fixed positive exponent in the barely-sublinear online-work target.	No-reference-string DEPIR open problem.	No paper spelling asserted.
s	Size of each index set in a client hint built from pseudorandom sets.	Client-specific preprocessing with set-based hints.	writes s
m	Number of database operations (additions, deletions, edits) in one update batch.	Updatable PIR.	writes m
κ	Statistical security parameter: failure and leakage probabilities are 2^−κ.	Client-preprocessing PIR with statistical correctness terms.	No paper spelling asserted.
Q	Number of queries a client answers from one offline phase, before its hint is refreshed.	Client preprocessing with amortized costs.	No paper spelling asserted.
n	Dimension of the LWE secret.	LWE- and Ring-LWE-based PIR.	No paper spelling asserted.
q	Ciphertext modulus of the LWE or Ring-LWE encryption.	LWE- and Ring-LWE-based PIR.	No paper spelling asserted.
ℤ_q	Integers modulo q; \(	\mathbb{Z}_q	\) is the size of one in bits.	LWE-based PIR.	No paper spelling asserted.
R_q	One element of the polynomial ring modulo q; \(	\mathcal{R}_q	\) is its size in bits.	Ring-LWE-based PIR.	No paper spelling asserted.
M	The composite modulus of a number-theoretic scheme (quadratic residuosity, Φ-hiding, Paillier).	Number-theoretic PIR.	No paper spelling asserted.
ℤ_M	Residues modulo M, and ℤ_M² modulo M²; \(	\cdot	\) is the size of one in bits.	Number-theoretic PIR.	No paper spelling asserted.

Costs in the comparison table are recorded per role: what the client sends, keeps and computes, and what one server sends, keeps and computes.

Role	Meaning	Regime	Paper names
Client	The party that wants record i and keeps any hint or key between queries.	Every PIR row.	No paper name asserted.
Server	A party holding the database or a replica; each figure is one server's.	Every PIR row.	No paper name asserted.

This topic covers index PIR for public databases: one server or several non-colluding servers, information-theoretic or computational privacy, and every preprocessing model above. Keyword, symmetric and batch PIR, ORAM, private writes, verifiability, and quantum or coded-storage PIR are outside it unless a covered result depends on them.

New to the area? Start here

Benny Chor, Oded Goldreich, Eyal Kushilevitz, Madhu Sudan · Journal of the ACM 45(6); preliminary FOCS 1995
Eyal Kushilevitz, Rafail Ostrovsky · FOCS 1997
Amos Beimel, Yuval Ishai, Tal Malkin · CRYPTO 2000
Niv Gilboa, Yuval Ishai · EUROCRYPT 2014
Henry Corrigan-Gibbs, Dmitry Kogan · EUROCRYPT 2020
Alexandra Henzinger, Matthew M. Hong, Henry Corrigan-Gibbs, Sarah Meiklejohn, Vinod Vaikuntanathan · USENIX Security 2023