Paper 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.

Metadata
Available format(s)
PDF
Publication info
Published by the IACR in TCC 2016
Keywords
Private Information RetrievalNP-hardnessReductions
Contact author(s)
vinodv @ mit edu
liutr @ mit edu
History
2015-11-03: last of 2 revisions
2015-10-30: received
See all versions
Short URL
https://ia.cr/2015/1061
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2015/1061,
      author = {Tianren Liu and Vinod Vaikuntanathan},
      title = {On Basing Private Information Retrieval on NP-Hardness},
      howpublished = {Cryptology ePrint Archive, Paper 2015/1061},
      year = {2015},
      note = {\url{https://eprint.iacr.org/2015/1061}},
      url = {https://eprint.iacr.org/2015/1061}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.