On Quantum Advantage in Information Theoretic Single-Server PIR

Dorit Aharonov, Zvika Brakerski, Kai-Min Chung +3

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]$ wit…