Private Information Retrieval with Sublinear Online Time
Private Information Retrieval with Sublinear Online Time
Henry Corrigan-Gibbs,Dmitry Kogan
2020 · DOI: 10.1007/978-3-030-45721-1_3
IACR Cryptology ePrint Archive · 147 Citations
TLDR
The first protocols for private information retrieval that allow fast (sublinear-time) database lookups without increasing the server-side storage requirements are presented and it is proved that the protocols are optimal in terms of the trade-off they achieve between communication and running time.