Abstract:
A private information retrieval scheme enables a user to privately recover an item from a public accessible database. In this paper we present a private information retrieval scheme for k replicated databases. The scheme is information-theoretically secure against coalitions of databases of size t <= k-1. It improves the communication complexity of the scheme described in [Ishai and Kushilevitz, 1999] for coalitions of size k\2 <= t <= k-1.