CANS 2024の採択論文に当研究所研究員が共著者として協力しました

研究成果の発表

2024年9月

Multi-Query Verifiable PIR and Its Application

学会・研究会：23rd International Conference on Cryptology And Network Security (CANS) 2024
著者：Ryuya Hayashi (AIST), Junichiro Hayata (DTCY), Keisuke Hara (AIST),
Kenta Nomura, Masaki Kamizono (DTCY), Goichiro Hanaoka (AIST)
https://2024.cansconference.org/home（外部サイト）

論文概要

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 at the same time. 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 · |a| + |π|), where n is the number of queries, |a| is the APIR communication size, and |π| 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.