On the Access Complexity of PIR Schemes

04/08/2018
by   Yiwei Zhang, et al.
0

Private information retrieval has been reformulated in an information-theoretic perspective in recent years. The two most important parameters considered for a PIR scheme in a distributed storage system are the storage overhead and PIR rate. We take into consideration a third parameter, the access complexity of a PIR scheme, which characterizes the total amount of data to be accessed by the servers for responding to the queries throughout a PIR scheme. We use a general covering code approach as the main tool for improving the access complexity. With a given amount of storage overhead, the ultimate objective is to characterize the tradeoff between the rate and access complexity of a PIR scheme. In this paper we make a first step towards solving this problem by analyzing the rate and access complexity of several PIR schemes.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset