Private Information Retrieval
In cryptography, a private information retrieval (PIR) protocol allows a user to retrieve an item from a server in possession of a database without revealing which item she is retrieving. PIR is a weaker version of 1-out-of-n oblivious transfer, where it is also required that the user should not get information about other database items.
One trivial, but very inefficient way to achieve PIR is for the server to send an entire copy of the database to the user. In fact, this is the only possible protocol that gives the user information theoretic privacy for their query in a single-server setting. There are two ways to address this problem: one is to make the server computationally bounded and the other is to assume that there are multiple non-cooperating servers, each having a copy of the database.
The problem was introduced in 1995 by Chor, Goldreich, Kushilevitz and Sudan in the information-theoretic setting and in 1997 by Kushilevitz and Ostrovsky in the computational setting. Since then, very efficient solutions have been discovered. Single database (computationally private) PIR can be achieved with constant (amortized) communication and k-database (information theoretic) PIR can be done with communication.
Read more about Private Information Retrieval: Advances in Computational PIR, Advances in Information Theoretic PIR, Relation To Other Cryptographic Primitives
Famous quotes containing the words private and/or information:
“Make-believe is the avenue to much of the young child’s early understanding. He sorts out impressions and tries out ideas that are foundational to his later realistic comprehension. This private world sometimes is a quiet, solitary
world. More often it is a noisy, busy, crowded place where language grows, and social skills develop, and where perseverance and attention-span expand.”
—James L. Hymes, Jr. (20th century)
“Knowledge is of two kinds. We know a subject ourselves, or we know where we can find information upon it.”
—Samuel Johnson (1709–1784)