Authenticated private information retrieval

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× more costly than stateof-the-art unauthenticated single-server schemes, though they achieve incomparably stronger integrity properties. Single server, point queries. Finally, we give two singleserver authenticated-PIR protocols: one from the learningwith-errors assumption, and one from the decisional-Diffie-Hellman assumption. Like many recent single-server PIR protocols [1, 4, 5, 52] , our schemes extend the classic Kushilevitz-Ostrovsky scheme based on additively homomorphic encryption [57, 75] . Our schemes incorporate additional randomness that the client uses to authenticate the server's response. The client verifies the server's reply using a short database digest that the client obtains via out-of-band means. Our schemes operate with single-bit records. We propose extensions for handling larger records, but they require increased PIR scheme N o. of ho ne st se rv er s ne ed ed M al ic io us Se le ct iv e-fa ilu re se cu re N o pu bl ic -k ey cr yp to gr ap hy R ec ov er y Multi-server schemes Robust PIR [11, 12] 1 ✗ ✗ ✓ ✓ Byzantine PIR [11, 12, 39, 49, 56] Table 2: Summary of PIR schemes that tolerate dishonest servers. The multi-server schemes assume k servers in total. Malicious indicates schemes that resist malicious adversaries, as opposed to merely faulty servers. Selective-failure secure indicates schemes designed to resist selective-failure attacks [55]. No public-key cryptography indicates schemes that require only fast symmetric primitives; singleserver schemes always require public-key operations [34]. Recovery indicates whether, in case of a server's misbehaviour, the client is able to recover the correct output or just aborts. municates with k > 1 database replicas; correctness holds if all k servers are honest and privacy holds if at least one server is honest. Multi-server PIR schemes traditionally offer information-theoretic privacy. In single-server PIR schemes (k = 1) [57], correctness holds if the single server is honest and privacy holds against a dishonest server. Single-server PIR schemes require a computationally-bounded server and public-key cryptographic operations [34]. In many applications, the database is a list of (keyword, value) pairs; the PIR client holds a keyword and wants the associated value. In this paper, we construct authenticated PIR schemes for integer-indexed arrays, and we use off-the-shelf methods [29, 48] to convert these schemes into authenticated keyword-based PIR schemes. Why integrity matters in PIR Standard PIR schemes give the client no integrity guarantees. If any one of the servers in a single-or multi-server scheme deviates from the protocol, the malicious server can-in many PIR protocols-completely control the output that the client receives. In other words, classic PIR protocols do not ensure correctness against even just one malicious server. This lack of integrity protection is extremely problematic in many applications of PIR: • Public-key server: If a client uses PIR to query a PGP or Signal key server for a contact's public keys, a malicious server could cause the client to fetch a false public key for which the adversary controls the secret key.