Single-Database Private Information Retrieval with Constant Communication Rate

By Craig Gentry, Zulfikar Ramzan. 2005

382 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

Private Stateful Information Retrieval (2018, methodology): “A more complex algorithm makes use of a private batched retrieval (PBR) scheme [7, 22, 26, 30].”
PIR with Compressed Queries and Amortized Query Processing (2018, methodology): “Related to CPIR, Groth et al. [48] extend Gentry and Ramzan’s [45] scheme to retrieve k elements at lower amortized network cost by having the client compute k discrete logarithms (with tractable but expensive parameters) on the server’s answer.”
Data-oblivious graph algorithms for secure computation and outsourcing (2013, background): “, [14, 15, 30, 11, 22, 31, 38] among others), where a server holds a database and a clients wants to a retrieve a record at a specific position with the goal that the server should not learn what record was accessed.”
Single-Database Private Information Retrieval from Fully Homomorphic Encryption (2013, methodology): “In the same setting, the database server in the PBR protocols [23], [25], [8], [14], needs about 17 hours to generate a response.”
Communication-Computation Trade-offs in PIR (2019, methodology): “We also consider the PIR protocol of Gentry and Ramzan [34], which has opposite cost characteristics with optimal communication and heavy computation, and present new”
A fast private information retrieval protocol (2008, background): “…has not as good communication performance as other existing protocols, but we show that practical usability of PIR schemes is not as dependent on communication performance as the literature suggests, and that a trade-off between communication and computation leads to much more versatile schemes.”
A Fast Single Server Private Information Retrieval Protocol with Low Communication Cost (2014, methodology): “Gentry et al [9] generalised Cachin et al’s approach and proposed a very communication efﬁcient PIR protocol.”
High-Speed Private Information Retrieval Computation on GPU (2008, methodology): “Similarly, Gentry and Ramzan’s scheme [10] is the outcome of the second known approach to obtain number-theory PIR schemes.”
Fully Homomorphic Encryption from Ring-LWE and Security for Key Dependent Messages (2011, methodology): “Our somewhat homomorphic encryption scheme can be used to construct a very efficient private information retrieval protocol [11, 18] with almost logarithmic communication complexity, and security under worst-case hardness assumptions.”
Polynomial Batch Codes for Efficient IT-PIR (2016, methodology): “We view these findings as a generalization and extension of Henry, Huang, and Goldberg’s multi-block IT-PIR queries [34], which are likewise constructed from ramp schemes.”
A Simpler Rate-Optimal CPIR Protocol (2017, methodology): “See [3,6] for a di↵erent approach that however results in rate that cannot be better than 1/4; see [3,6] for a discussion.”
A Lattice-Based Computationally-Efficient Private Information Retrieval Protocol (2007, background): “Some PIR schemes [10, 11] do a long pre-computation over the database contents before answering to the PIR queries.”
Optimal Rate Private Information Retrieval from Homomorphic Encryption (2015, methodology): “The CPIR protocol of Gentry and Ramzan [18] achieves rate (1)4 .”