Improved upper bounds on information-theoretic private information retrieval (extended abstract)
Yuval Ishai, Eyal Kushilevitz · 1999
Private Information Retrieval (PIR) schemes allow a user to retrieve the i-th bit of an n-bit database x, replicated in k servers, while keeping the value of i private from each server. A t-private PIR scheme protects the user's privacy from any collusion of up to t servers. The main cost measure for such schemes is their communication complexity. We introduce a new technique for the construction of information-theoretic (i.e., unconditionally secure) PIR schemes, providing a non-trivial linear-algebraic generalization of previous techniques. Using this technique, we improve and simplify known upper bounds on the communication complexity of PIR schemes in the information-theoretic setting. In the case of 1-private PIR, we give a simple k-server scheme with complexity O(k 3 n 1=(2k\\Gamma1) ), improving the best known construction whose complexity also grows linearly in n 1=(2k\\Gamma1) for any fixed k, but depends exponentially on k. Our improvements are more significant for t-pri...