[LV15] On Basing Private Information Retrieval on NP-Hardness

Authors: Tianren Liu, Vinod Vaikuntanathan | Venue: TCC 2015 | Source

Abstract

The possibility of basing the security of cryptographic objects on the (minimal) assumption that $\mathcal{NP}\subseteq \mathcal{B}\mathcal{PP}$ 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 $\mathcal{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 $\mathcal{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 $\mathcal{SZ}\mathcal{K}$ oracle. Our result is tight in terms of both the correctness and the privacy parameter of the PIR scheme.

BibTeX

Copy

@Inproceedings{TCC:LiuVai16,
  author = {Tianren Liu and Vinod Vaikuntanathan},
  title = {On Basing Private Information Retrieval on {NP}-Hardness},
  pages = {372--386},
  editor = {Eyal Kushilevitz and Tal Malkin},
  booktitle = {TCC~2016-A: 13th Theory of Cryptography Conference, Part~I},
  volume = {9562},
  series = {Lecture Notes in Computer Science},
  address = {Tel Aviv, Israel},
  month = {jan~10--13},
  publisher = {Springer Berlin Heidelberg, Germany},
  year = {2016},
  doi = {10.1007/978-3-662-49096-9_16},
}