Robust Private Information Retrieval with Optimal Server Computation
Yi-Sheng Su · 2022 IEEE Information Theory Workshop (ITW) · 2022
Private information retrieval (PIR) schemes allow a user to retrieve entries of a database without revealing the index of the desired item. The focus of this paper lies on constructions of PIR schemes with optimal computational complexity for the servers, which play a crucial part in fast retrieval. This paper first proposes a generic construction of t-private PIR schemes using circulant permutation matrices (CPMs), which can protect the user’s perfect privacy from any collusion of up to t servers. Then this paper takes Byzantine and unresponsive servers into account in the t-private PIR schemes using CPMs and proposes a generic construction of t-private robust PIR schemes using CPMs. The proposed constructions of PIR schemes enjoy the advantages of optimal computational complexity for the servers, competitive user computational complexity, acceptable communication complexity, low memory space for storing all possible queries for the user, and low encoding complexity upon encoding the database.