Verifiable and Byzantine-robust Private Information Retrieval over Distributed Database
Xindi Ma, Yu He, Junying Zhang, Ning Xi, Di Lu, Pengbin Feng, Yulong Shen, Jianfeng Ma · 2024
Private Information Retrieval (PIR) protocols enable a user to retrieve a specific data item from a database while ensuring that no information about the requested item’s identity is revealed. To defend against Byzantine attacks in multi-server scenarios, we present a new Verifiable and Byzantine-robust Private Information Retrieval scheme (VBRPIR) on a database stored on n servers. Specifically, the database consists of m files of size l, which are encoded and stored, respectively, among n servers that may be colluding, Byzantine, and unresponsive. Differently from the erasure code-based scheme, we propose a new scheme based on a hash function and linear equations to verify answers and reconstruct the desired file from wrong answers, even in the extreme situation where all servers are Byzantine or unresponsive servers. Concretely, hash function is used to generate commitment of data stored on servers in offline stage, and the commitment is used to verify Byzantine server, based on the one-way property of hash function. Linear equations are also generated in the offline stage, used to reconstruct file when exists Byzantine or unresponsive server. The scheme achieves a download rate of $\frac{l}{2 n}$ for any number of files. We provide theoretical analysis and experimental results to illustrate the efficiency of our work. In the experimental setup of this paper, the time to retrieve a single file is within 1ms when there is at least one responsive and honest server. Even in the extreme case where all servers are Byzantine servers, the file can be retrieved within 2s.