Welcome to the resource topic for 2019/232
Title:
On Quantum Advantage in Information Theoretic Single-Server PIR
Authors: Dorit Aharonov, Zvika Brakerski, Kai-Min Chung, Ayal Green, Ching-Yi Lai, Or Sattath
Abstract:In (single-server) Private Information Retrieval (PIR), a server holds a large database DB of size n, and a client holds an index i \in [n] and wishes to retrieve DB[i] without revealing i to the server. It is well known that information theoretic privacy even against an honest but curious'' server requires $\Omega(n)$ communication complexity. This is true even if quantum communication is allowed and is due to the ability of such an adversarial server to execute the protocol on a superposition of databases instead of on a specific database (input purification attack’'). Nevertheless, there have been some proposals of protocols that achieve sub-linear communication and appear to provide some notion of privacy. Most notably, a protocol due to Le Gall (ToC 2012) with communication complexity O(\sqrt{n}), and a protocol by Kerenidis et al. (QIC 2016) with communication complexity O(\log(n)), and O(n) shared entanglement. We show that, in a sense, input purification is the only potent adversarial strategy, and protocols such as the two protocols above are secure in a restricted variant of the quantum honest but curious (a.k.a specious) model. More explicitly, we propose a restricted privacy notion called \emph{anchored privacy}, where the adversary is forced to execute on a classical database (i.e. the execution is anchored to a classical database). We show that for measurement-free protocols, anchored security against honest adversarial servers implies anchored privacy even against specious adversaries. Finally, we prove that even with (unlimited) pre-shared entanglement it is impossible to achieve security in the standard specious model with sub-linear communication, thus further substantiating the necessity of our relaxation. This lower bound may be of independent interest (in particular recalling that PIR is a special case of Fully Homomorphic Encryption).
ePrint: https://eprint.iacr.org/2019/232
Talk: https://www.youtube.com/watch?v=QpYdZQKRr2A
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 .