## CryptoDB

### Paper: On Quantum Advantage in Information Theoretic Single-Server PIR

Authors: Dorit Aharonov Zvika Brakerski Kai-Min Chung Ayal Green Ching-Yi Lai Or Sattath DOI: 10.1007/978-3-030-17659-4_8 Search ePrint Search Google In (single-server) Private Information Retrieval (PIR), a server holds a large database ${\mathtt {DB}}$ of size n, and a client holds an index $i \in [n]$ and wishes to retrieve ${\mathtt {DB}}[i]$ without revealing i to the server. It is well known that information theoretic privacy even against an “honest but curious” server requires $\varOmega (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 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).
##### BibTeX
@article{eurocrypt-2019-29386,
title={On Quantum Advantage in Information Theoretic Single-Server PIR},
booktitle={Advances in Cryptology – EUROCRYPT 2019},
series={Advances in Cryptology – EUROCRYPT 2019},
publisher={Springer},
volume={11478},
pages={219-246},
doi={10.1007/978-3-030-17659-4_8},
author={Dorit Aharonov and Zvika Brakerski and Kai-Min Chung and Ayal Green and Ching-Yi Lai and Or Sattath},
year=2019
}