One extra bit of download ensures perfectly private information retrieval

By Nihar B. Shah, K. V. Rashmi, Kannan Ramchandran. 2014

211 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Computer Networks and Communications, Information Retrieval & Search, 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 Artificial Intelligence

In Computer Networks and Communications

In Information Retrieval & Search

In Privacy & Security

Citations in the corpus

ON-OFF Privacy with Correlated Requests (2019, neutral): “[5]–[9]).”
Staircase-PIR: Universally Robust Private Information Retrieval (2018, background): “Given the increasing size of stored files, the recent body of work measures the communication cost by the amount of information downloaded by the user, assuming the queries are too small compared to the downloaded files [12], [17]– [23] which is the assumption we adopt in this paper.”
Lifting Private Information Retrieval from Two to any Number of Messages (2018, methodology): “When the data is coded and stored on a large number of servers (exponential in the number of messages), it was shown in [9] that downloading one extra bit is enough to achieve privacy.”
The Capacity of Private Information Retrieval From Coded Databases (2016, background): “PIR problem, little research exists for coded PIR with a few exceptions: [13] which has initiated the work on coded databases and has designed an explicit erasure code and PIR algorithm that requires only one extra bit of download to provide perfect privacy.”
The Capacity of Private Information Retrieval (2016, background): “In general, for arbitrary N and K, the best previously known achievable rate for PIR, reported in [29], is 1− 1 N .”
Robust private information retrieval on coded data (2017, background): “It was shown in [9] that downloading one extra bit is enough to achieve privacy, if the number of servers is exponential in the number of files.”
Private Information Retrieval With Side Information (2017, background): “Recently, there has been a renewed interest in PIR for the case in which the data is stored on the servers using erasure codes, which result in better storage overhead compared to the traditional replication techniques [11]–[18].”
Private information retrieval with side information: The single server case (2017, background): “Recently, there has been a renewed interest in PIR for the case in which the data is stored on the servers using erasure codes, which result in better storage overhead compared to the traditional replication techniques [11]–[18].”
The Capacity of Robust Private Information Retrieval With Colluding Databases (2016, background): “There is also much recent work in the distributed storage setting [24], [32]–[34] (the databases form a distributed”
The Capacity of Private Computation (2017, background): “ain linearly independent ones, so that H(W 1,W 2,··· ,WM) = H(Wd1,Wd2,··· ,WdK) = KL. 4 Proof: For Theorem 2, the achievability is identical to the symmetric PIR3 scheme of Theorem 1 in [3] (see also [9,10]), where the M functions are viewed as the messages in the symmetric PIR problem and common ra”
Private Information Retrieval from Coded Databases with Colluding Servers (2016, background): “While [11] effectively answered the question on how low the communication cost of a cPIR scheme can be, it highlighted another cost parameter that should not be neglected in the era of big data, namely the storage overhead.”
Polynomial Batch Codes for Efficient IT-PIR (2016, background): “The culmination of these efforts includes two recent PIR protocols—one computationally private [37] and the other information-theoretically private [47]—that achieve optimal downstream rate.”
Robust Private Information Retrieval from Coded Systems with Byzantine and Colluding Servers (2018, background): “The authors in [8] show that downloading one extra bit is enough to achieve privacy, if the number of servers is exponential in the number of files.”
The Capacity of Private Information Retrieval from Byzantine and Colluding Databases (2017, background): “Recently, the PIR problem is revisited by information theorists [6]–[9].”