Protecting data privacy in private information retrieval schemes

Private information retrieval (PIR) schemes allow a user to retrieve the it h bit of an ri-bit data string x, replicated in k greater than or equal to 2 databases (in the information-theoretic setting) or in k greater than or equal to 1 databases (in the computational setting), while keeping the valu e of i private. The main cost measure for such a scheme is its communicatio n complexity. In this paper we introduce a model of symmetrically-private i nformation retrieval (SPIR), where the privacy of the data. as well as the privacy of the user, is guaranteed. That is, in every invocation of a SPIR protocol, the user learns only a single physical bit of x and no other info rmation about the data. previously known PIR schemes severely fail to meet this goal. We show how to transform PIR schemes into SPIR schemes (with inf ormation-theoretic privacy), paying a constant factor in communication comp lexity. To this end, we introduce and utilize a new cryptographic primitive , called conditional disclosure of secrets, which we believe may be a usefu l building block for the design of other cryptographic protocols. In partic ular, we get a k-database SPIR scheme of complexity O(n(1/t(2k-1))) for eve ry constant k greater than or equal to 2 and an O(log n)-database SPIR sche me of complexity O(log(2) n . log log n) Ail our schemes require only a sin gle round of interaction, and art resilient to any dishonest behavior of th e user. These results also yield the first implementation of a distributed version of ((n)(1))-OT (1-out-of-n oblivious transfer) with information-the oretic security and sublinear communication complexity. (C) 2000 Academic P ress.