Paper 2019/1075

Private Information Retrieval with Sublinear Online Time

Henry Corrigan-Gibbs and Dmitry Kogan

Abstract

We present the first protocols for private information retrieval that allow fast (sublinear-time) database lookups without increasing the server-side storage requirements. To achieve these efficiency goals, our protocols work in an offline/online model. In an offline phase, which takes place before the client has decided which database bit it wants to read, the client fetches a short string from the servers. In a subsequent online phase, the client can privately retrieve its desired bit of the database by making a second query to the servers. By pushing the bulk of the server-side computation into the offline phase (which is independent of the client's query), our protocols allow the online phase to complete very quickly—in time sublinear in the size of the database. Our protocols can provide statistical security in the two-server setting and computational security in the single-server setting. Finally, we prove that, in this model, our protocols are optimal in terms of the trade-off they achieve between communication and running time.

Note: This version fixes one typographical error.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
A major revision of an IACR publication in Eurocrypt 2020
Keywords
Private Information Retrieval
Contact author(s)
henrycg @ cs stanford edu
dkogan @ cs stanford edu
History
2022-03-28: last of 4 revisions
2019-09-23: received
See all versions
Short URL
https://ia.cr/2019/1075
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2019/1075,
      author = {Henry Corrigan-Gibbs and Dmitry Kogan},
      title = {Private Information Retrieval with Sublinear Online Time},
      howpublished = {Cryptology ePrint Archive, Paper 2019/1075},
      year = {2019},
      note = {\url{https://eprint.iacr.org/2019/1075}},
      url = {https://eprint.iacr.org/2019/1075}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.