On Basing Private Information Retrieval on NP-Hardness

Tianren Liu; Vinod Vaikuntanathan

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 N P ⊈ \comp B P P$ 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 N P$ -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 N P$ -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 S Z K$ 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 Retrieval NP-hardness Reductions
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: 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},
      url = {https://eprint.iacr.org/2015/1061}
}