Paper 2023/297
Authenticated private information retrieval
, École Polytechnique Fédérale de Lausanne (EPFL)Abstract
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.
Metadata
- Available format(s)
-
PDF
- Category
- Cryptographic protocols
- Publication info
- Published elsewhere. Major revision. USENIX Security Symposium 2023
- Keywords
- Private information retrieval
- Contact author(s)
- simone colombo @ epfl ch
- History
- 2024-02-26: last of 2 revisions
- 2023-02-27: received
- See all versions
- Short URL
- https://ia.cr/2023/297
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2023/297,
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{https://eprint.iacr.org/2023/297}},
url = {https://eprint.iacr.org/2023/297}
}
