Key points are not available for this paper at this time.
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 users 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\1) ), improving the best known construction whose complexity also grows linearly in n 1= (2k\1) for any fixed k, but depends exponentially on k. Our improvements are more significant for t-pri. . .
Ishai et al. (Sat,) studied this question.