[LV15] On Basing Private Information Retrieval on NP-Hardness

Authors: Tianren Liu, Vinod Vaikuntanathan | Venue: TCC 2015 | Source

Abstract

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