Private information retrieval

By Benny Chor, Eyal Kushilevitz, Oded Goldreich, Madhu Sudan. 1995

We describe schemes that enable a user to access k replicated copies of a database (k/spl ges/2) and privately retrieve information stored in the database. This means that each individual database gets no information on the identity of the item retrieved by the user. For a single database, achieving this type of privacy requires communicating the whole database, or n bits (where n is the number of bits in the database). Our schemes use the replication to gain substantial saving. In particular, we have: A two database scheme with communication complexity of O(n/sup 1/3/). A scheme for a constant number, k, of databases with communication complexity O(n/sup 1/k/). A scheme for 1/3 log/sub 2/ n databases with polylogarithmic (in n) communication complexity.

Subfields: Privacy & Security

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Privacy & Security

Citations in the corpus

Advances and Open Problems in Federated Learning (2019, background): “MPC approaches to PIR break down into two main categories: computational PIR (cPIR), in which a single party can execute the entire server side of the protocol [249], and information theoretic PIR (itPIR), in which multiple non-colluding parties are required to execute the server side of the protoco”
Preserving ON-OFF Privacy for Past and Future Requests (2019, methodology): “This is consistent with the wellknown result [3].”
ON-OFF Privacy with Correlated Requests (2019, background): “This is an immediate result in information-theoretic single-server private information retrieval [3].”
Private Stateful Information Retrieval (2018, background): “Private Information Retrieval (PIR) [18, 36] is a very important privacy-preserving primitive for accessing data held by untrusted servers.”
Staircase-PIR: Universally Robust Private Information Retrieval (2018, background): “[1], [2] and was followed up by a large body of work, e.”
PIR with Compressed Queries and Amortized Query Processing (2018, background): “1 In IT-PIR schemes [11, 28, 31, 32, 41] the database is replicated across several non-colluding servers.”
Lifting Private Information Retrieval from Two to any Number of Messages (2018, background): “um Distance Separable (MDS) code1. These servers could possibly collude to gain information about the identity of the user’s retrieved message. The PIR problem was ﬁrst introduced and studied in [1], [2] and was followed up by a large body of work (e.g. [3]–[8]). The model there assumes the database”
XPIR : Private Information Retrieval for Everyone (2016, neutral): “PIR was introduced by Chor, Goldreich, Kushilevitz, and Sudan in 1995 [2].”
The Capacity of Private Information Retrieval From Coded Databases (2016, background): “[1], the classical problem of private information retrieval (PIR) is introduced.”
The Capacity of Private Information Retrieval (2016, background): “1There is another line of research, where privacy needs to be satisfied only for computationally bounded databases [9], [8], [23].”
Riposte: An Anonymous Messaging System Handling Millions of Users (2015, methodology): “Our DPF constructions make extensive use of prior work on private information retrieval (PIR) [16], [17], [33], [37].”
Private Searching on Streaming Data (2005, background): “(In the setting of multiple, non-communicating databases, the PIR notion was introduced in [7].”
A Fast Single Server Private Information Retrieval Protocol with Low Communication Cost (2014, methodology): “With some modiﬁcations, we can extend the PIR protocol into a PBR protocol [3] or a symmetric PIR protocol [4].”
Parallel Coin-Tossing and Constant-Round Secure Two-Party Computation (2001, result): “As we have described, in this paper we establish the analogous result for the setting of two-party computation.”
Mixminion: design of a type III anonymous remailer protocol (2003, background): “Private Information Retrieval [21] may down the road allow clients to efficiently, securely, and privately download a subset of the directory.”
Controlling Access to Published Data Using Cryptography (2003, background): “More recent work has also addressed the client’s security [10]: how to preserve client privacy by not allowing the data owner to witness all their queries.”