Protecting data privacy in private information retrieval schemes

Abstract

Private Information Retrieval (PIR) schemes allow a user to retrieve the i-th bit of a data string 2, replicated in k 2 2 databnaes (in the information-theoretic setting) or k 2 1 databnses (in the computational setting), while keeping the value of i private, The main cost measure for such a scheme io its communication complexity.