Paper 2023/297

Authenticated private information retrieval

Simone Colombo, École Polytechnique Fédérale de Lausanne (EPFL)
Kirill Nikitin, Cornell Tech
Henry Corrigan-Gibbs, Massachusetts Institute of Technology
David J. Wu, The University of Texas at Austin
Bryan Ford, École Polytechnique Fédérale de Lausanne (EPFL)

This paper introduces protocols for authenticated private information retrieval. These schemes enable a client to fetch a record from a remote database server such that (a) the server does not learn which record the client reads, and (b) the client either obtains the "authentic" record or detects server misbehavior and safely aborts. Both properties are crucial for many applications. Standard private-information-retrieval schemes either do not ensure this form of output authenticity, or they require multiple database replicas with an honest majority. In contrast, we offer multi-server schemes that protect security as long as at least one server is honest. Moreover, if the client can obtain a short digest of the database out of band, then our schemes require only a single server. Performing an authenticated private PGP-public-key lookup on an OpenPGP key server's database of 3.5 million keys (3 GiB), using two non-colluding servers, takes under 1.2 core-seconds of computation, essentially matching the time taken by unauthenticated private information retrieval. Our authenticated single-server schemes are 30-100$\times$ more costly than state-of-the-art unauthenticated single-server schemes, though they achieve incomparably stronger integrity properties.

Note: This version adds an overview of the proof strategy, fixes the proofs of Lemma 26 and Theorem 28, and corrects some typos.

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. Major revision. USENIX Security Symposium 2023
Private information retrieval
Contact author(s)
simone colombo @ epfl ch
2024-02-26: last of 2 revisions
2023-02-27: received
See all versions
Short URL
Creative Commons Attribution


      author = {Simone Colombo and Kirill Nikitin and Henry Corrigan-Gibbs and David J. Wu and Bryan Ford},
      title = {Authenticated private information retrieval},
      howpublished = {Cryptology ePrint Archive, Paper 2023/297},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.