Paper 2015/1061 Original: eprint.iacr.org/2015/1061 ↗
On Basing Private Information Retrieval on NP-Hardness
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
- Preprint.
- History
- 2015-11-03: last updated
- 2015-10-30: published
- Short URL
- https://ia.cr/2015/1061
- License
- https://creativecommons.org/licenses/by/4.0/
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}
}