# On Basing Private Information Retrieval on NP-Hardness Authors: Tianren Liu, Vinod Vaikuntanathan URL: https://eprint.iacr.org/2015/1061 ## Abstract The possibility of basing the security of cryptographic objects on the (minimal) assumption that $\mathcal{NP} \subseteq \mathcal{BPP}$ is at the very heart of complexity-theoretic cryptography. Most known results along these lines are negative, showing that assuming widely believed complexity-theoretic conjectures, there are no reductions from an $\mathcal{NP}$-hard problem to the task of breaking certain cryptographic schemes. We make progress along this line of inquiry by showing that the security of single-server single-round private information retrieval schemes cannot be based on $\mathcal{NP}$-hardness, unless the polynomial hierarchy collapses. Our main technical contribution is in showing how to break the security of a PIR protocol given an $\mathcal{SZK}$ oracle. Our result is tight in terms of both the correctness and the privacy parameter of the PIR scheme.