Breaking the O(n/sup 1/(2k-1)/) barrier for information-theoretic Private Information Retrieval

By Amos Beimel, Yuval Ishai, Eyal Kushilevitz, Jean-François Raymond. 2002

237 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Computational Theory and Mathematics

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 Computational Theory and Mathematics

Citations in the corpus

PIR with Compressed Queries and Amortized Query Processing (2018, background): “1 In IT-PIR schemes [15, 33, 36, 37, 46] the database is replicated across several non-colluding servers.”
The Capacity of Private Information Retrieval (2016, background): “Since the download cost is the reciprocal of the rate, Theorem 1 equivalently characterizes the optimal download cost per message bit as ( 1 + 1/N + 1/N2 + · · ·+ 1/NK−1 ) bits.”
Private Information Retrieval From MDS Coded Data in Distributed Storage Systems (2016, background): “Replication-based PIR: PIR was ﬁrst introduced in the seminal papers of Chor et al. in [2], [3] followed by a signiﬁcant amount of research in this area [4]–[8], [11], [12].”
Reducing the Servers Computation in Private Information Retrieval: PIR with Preprocessing (2000, background): “Subsequently to this work, the communication complexity of information-theoretic PIR has been improved in [9], where it was shown that for every constant k there is k-server protocol with communication complexity O(nc log log k/k log k) (c is some constant independent of k).”
Robust Information-Theoretic Private Information Retrieval (2002, methodology): “6 k-out-of−` 2n 2 log log k k log k ` log ` Generic + [58, 48, 11] Cor.”
Share Conversion, Pseudorandom Secret-Sharing and Applications to Secure Computation (2005, background): “…instance, replicated shares yield the most eﬃcient information-theoretic private informa-346 tion retrieval protocols and locally decodable codes [5], the best round complexity for veriﬁable secret-sharing [18], and the simplest protocols for secure multiparty computation with respect to…”
Reducing the Servers’ Computation in Private Information Retrieval: PIR with Preprocessing (2004, background): “Subsequently to this work, the communication complexity of information-theoretic PIR has been improved in [ 9 ], where it was shown that for every constant k there is kserver protocol with communication complexity O(n c log log k/k log k ) (c is some constant”
A Survey on Private Information Retrieval (2004, background): “(f) Beimel et al. [12] have a scheme that uses n O (lg lg k/k lg k ) bits.”
Cryptography from Anonymity (2006, background): “In recent yea rs, there has been a significant body of work on improving the communication complexity of PIR, either in the above single-server scenario [41, 10, 42, 26] or using multiple servers [15, 3 ]. Given the low (and essentially optimal) communication complexity of the best known PIR protoc”
A Survey on Private Information Retrieval (Column: Computational Complexity) (2004, methodology): “Theorem 3.10. [9, 39, 10, 12 ] For all k, there is a k-DB O (k3n1/2k 1)-bit scheme.”