Cryptology ePrint Archive: Report 2015/1061

On Basing Private Information Retrieval on NP-Hardness

Tianren Liu and Vinod Vaikuntanathan

Abstract: 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.

Category / Keywords: Private Information Retrieval, NP-hardness, Reductions

Original Publication (in the same form): IACR-TCC-2016

Date: received 30 Oct 2015, last revised 2 Nov 2015

Contact author: vinodv at mit edu, liutr at mit edu

Available format(s): PDF | BibTeX Citation

Version: 20151103:054535 (All versions of this report)

Short URL:

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]