International Association
for Cryptologic Research

The possibility of basing the security of cryptographic objects on the (minimal) assumption that $\\comp{NP} \\nsubseteq \\comp{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 $\\comp{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 $\\comp{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 $\\comp{SZK}$ oracle. Our result is tight in terms of both the correctness and the privacy parameter of the PIR scheme.