No fully-black-box reduction from NP to one-round sublinear cPIR

Unconditional · against fully-black-box reductions · LV15

Statement

A probabilistic polynomial-time reduction from the NP-complete problem $\mathrm{SAT}$ to breaking the privacy of a one-round sublinear single-server PIR scheme, using the privacy adversary only as an oracle with polynomially many adaptively chosen queries, implies $\mathbf{NP}\subseteq \mathbf{coAM}$, equivalently $\mathbf{coNP}\subseteq \mathbf{AM}$ — LV15 — and hence a collapse of the polynomial hierarchy to its second level — BHZ87. LV15 prove it for single-round schemes whose answers are short enough relative to the database, and the result is tight in both the correctness and the privacy parameter — LV15; some bound on the answer is needed, since the trivial scheme, in which the server sends the whole database, is perfectly private — standard.

Notes

• The proof breaks the privacy of every such scheme efficiently given an $\mathbf{SZK}$ oracle — LV15.