Multi-query Verifiable PIR and Its Application

Private information retrieval (PIR) allows a client to obtain records from a database without revealing the retrieved index to the server. In the single-server model, it has been known that (plain) PIR is vulnerable to selective failure attacks, where a (malicious) server intends to learn information of an index by getting a client's decoded result. Recently, as one solution for this problem, Ben-David et al. (TCC 2022) proposed verifiable PIR (vPIR) that allows a client to verify that the queried database satisfies certain properties. However, the existing vPIR scheme is not practically efficient, especially when we consider the multi-query setting, where a client makes multiple queries for a server to retrieve some records either in parallel or in sequence. In this paper, we introduce a new formalization of multi-query vPIR and provide an efficient scheme based on authenticated PIR (APIR) and succinct non-interatctive arguments of knowledge (SNARKs). More precisely, thanks to the nice property of APIR, the communication cost of our multi-query vPIR scheme is O(n center dot |a| + |pi|), where n is the number of queries, |a| is the APIR communication size, and |p| is the SNARK proof size. That is, the communication includes only one SNARK proof. In addition to this result, to show the effectiveness of our multi-query vPIR scheme in a real-world scenario, we present a practical application of vPIR on the online certificate status protocol (OCSP) and provide a comprehensive theoretical evaluation on our scheme in this scenario. Especially in the setting of our application, we observe that integrating SNARK proofs (for verifiability) does not significantly increase the communication cost.