International Association
for Cryptologic Research

The possibility of basing the security of cryptographic objects on the (minimal) assumption that $\\NP \\nsubseteq \\BPP$ is at the very heart of

complexity-theoretic cryptography. Unfortunately, most known results along these lines are negative, showing that, assuming widely believed complexity-theoretic conjectures, there are no reductions from an $\\NP$-hard problem to the task of breaking certain cryptographic schemes. For example, the work of Brassard (FOCS 1979) showed that one-way permutations cannot be based on $\\NP$-hardness; Akavia, Goldreich, Goldwasser and Moshkovitz (STOC 2006) and Bogdanov and Brzuska (TCC 2015) showed that size-verifiable one-way functions cannot be based on $\\NP$-hardness; and Bogdanov and Lee (CRYPTO 2013) showed that even simple homomorphic encryption schemes cannot be based on $\\NP$-hardness.

We make progress along this line of inquiry by showing that single-server private information retrieval schemes cannot be based on $\\NP$-hardness, unless the polynomial hierarchy collapses.

Our result is tight in terms of both the correctness and the privacy parameter of the PIR scheme.