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
-
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}
}