Two-Server Private Information Retrieval with Result Verification
- Resource Type
- Conference
- Authors
- Ke, Pengzhen; Zhang, Liang Feng
- Source
- 2022 IEEE International Symposium on Information Theory (ISIT) Information Theory (ISIT), 2022 IEEE International Symposium on. :408-413 Jun, 2022
- Subject
- Communication, Networking and Broadcast Technologies
Privacy
Protocols
Databases
Information retrieval
Complexity theory
Servers
Information theory
- Language
- ISSN
- 2157-8117
Private information retrieval (PIR) allows a client to retrieve any block x i from a database x = x 1 x n 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 ${\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.