Paper 2022/081

Single-Server Private Information Retrieval with Sublinear Amortized Time

Henry Corrigan-Gibbs, Alexandra Henzinger, and Dmitry Kogan

Abstract

We construct new private-information-retrieval protocols in the single-server setting. Our schemes allow a client to privately fetch a sequence of database records from a server, while the server answers each query in average time sublinear in the database size. Specifically, we introduce the first single-server private-information-retrieval schemes that have sublinear amortized server time, require sublinear additional storage, and allow the client to make her queries adaptively. Our protocols rely only on standard cryptographic assumptions (decision Diffie-Hellman, quadratic residuosity, learning with errors, etc.). They work by having the client first fetch a small "hint" about the database contents from the server. Generating this hint requires server time linear in the database size. Thereafter, the client can use the hint to make a bounded number of adaptive queries to the server, which the server answers in sub-linear time--yielding sublinear amortized cost. Finally, we give lower bounds proving that our most efficient scheme is optimal with respect to the trade-off it achieves between server online time and client storage.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
A major revision of an IACR publication in Eurocrypt 2022
Keywords
Private Information Retrieval
Contact author(s)
ahenz @ csail mit edu
henrycg @ csail mit edu
dkogan @ cs stanford edu
History
2022-03-15: revised
2022-01-23: received
See all versions
Short URL
https://ia.cr/2022/081
License
Creative Commons Attribution
CC BY

BibTeX

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