Private information retrieval (PIR) allows a client to retrieve any block xifrom a database x = x1xnsuch 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 ${\mathcal{O}}({n^{1/2}}{\text{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.Private information retrieval (PIR) allows a client to retrieve any block xifrom a database x = x1xnsuch 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 ${\mathcal{O}}({n^{1/2}}{\text{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.

IEEE International Symposium on Information Theory (ISIT)Jun 26, 202211 citations

{\mathcal{O}}({n^{1/2}}{\text{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.