Private Information Retrieval

Protocols letting a client read one item of a database without revealing which, and the communication, computation and storage they need.

Status	Statement	Tags
	Balanced Root-n Preprocessing PIR The client-space-times-bandwidth product is settled up to n^{o(1)} by the source’s own matching bounds. What is open is whether client space, bandwidth and per-query server computation can all sit at O~(n^{1/2}) simultaneously; the best known point has client space and server computation O~(n^{2/3}). 4 open	Private Information Retrieval Time Space Tradeoffstight-bound
	AVPs Are Lengthy Posed as Hypothesis 1.2 and offered both as a working hypothesis and as an ambitious target. Theorem 1.3 proves it implies super-polynomial lower bounds on sd-PIR, general secret sharing and fully-decomposable randomized encodings – for none of which a super-linear lower bound is currently known. The source adapts counting-based arguments to the model but does not reach the best-known bound for any primitive. 4 open	Garbled Circuits Private Information Retrieval Proof Size Lower Bounds Randomized Encodingslower-boundbarrier (ai)
	SK-DEPIR from One-Way Functions Stated by the source as its own conjecture and proved for two-round passive-server schemes. Its main theorem – that any crypto oracle can be stripped out of a SK-DEPIR and replaced by a one-way function – is stated conditionally on this, so the conjecture is the single remaining hypothesis between that compiler and a clean statement that no idealized generic primitive helps. 4 open	Black Box Separations One Way Functions Private Information Retrievalimpossibility
	Arithmetic Two-Server PIR Optimality O(n^{1/3}) is achieved by arithmetizing the classical two-server schemes. The source states that whether it can be improved – let alone brought to sub-polynomial – is unknown, and supplies a linear-algebraic characterization of exactly what an improvement would require. 5 open	Arithmetic Cryptography Private Information Retrievaltight-bound
	Polylog Shuffle PIR, Negligible Error Settled in three neighbouring corners: O(n^gamma) communication with inverse-polynomial error and polynomially many queries; polylogarithmic communication with n^{O(log n)} queries; and negligible error with O(n/log n) communication. The polylogarithmic-and-negligible corner with polynomially many queries is open, and is ruled out for inner-outer constructions with an additive inner layer by the source’s own Theorem 6.5. 5 open	Private Information Retrieval Shuffle Modelcharacterizationadaptation (ai)
	Hold-Out Soundness, Dirty Coordinates The source’s distinguishing attack is unconditional and proved. Its decryption attack is heuristic, and this is the unproved step: completeness on clean coordinates is its Claim 6.2, while soundness on dirty ones is supported only by a heuristic dimension count and small-parameter experiments. 5 open	Code Based Cryptography Private Information Retrievalcharacterization