Welcome to the resource topic for 2015/1061
Title:
On Basing Private Information Retrieval on NP-Hardness
Authors: Tianren Liu, 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.
ePrint: https://eprint.iacr.org/2015/1061
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .