上海科技大学知识管理系统

Private information retrieval (PIR) allows a client to retrieve any block xi from a database x = x1 xn such that i remains hidden from the database servers. PIR •protocols with unconditional privacy and sublinear (in n) communication complexity can be constructed assuming multiple honest-but-curious servers. This assumption however cannot be guaranteed in many real life scenarios such as using cloud servers as database servers. In this paper, we consider an information-theoretic PIR with result verification (PIR-RV) model where the servers may be dishonest (i.e., cheating) and provide incorrect answers but the client can detect the existence of cheating servers. We construct a 2-server PIR-RV protocol with communication complexity O(n1/2 log p) where p is a parameter and controls the probability that the client fails to detect. Our idea may be extended to construct k-server PIR-RV protocols for k ≥ 3. © 2022 IEEE.