Single Database Private Information Retrieval with Logarithmic Communication

By Yan-Cheng Chang. 2004

195 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Computational Theory and Mathematics, Information Systems

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

In Information Systems

Citations in the corpus

PIR with Compressed Queries and Amortized Query Processing (2018, methodology): “On the other hand, CPIR protocols [4, 19, 22, 35, 40, 52, 53, 56, 57, 76] can be used with a database controlled by a single administrative domain (e.”
Breaking the O(n/sup 1/(2k-1)/) barrier for information-theoretic Private Information Retrieval (2002, result): “The difficulty of constructing an appropriate protocol P, to be used in the recursion, is in the somewhat contradicting goals of the above description.”
Single-Database Private Information Retrieval from Fully Homomorphic Encryption (2013, methodology): “For example, the PIR protocol of Kushilevitz and Ostrovsky [23] is based on the GoldwasserMicali homomorphic encryption E [22], in which Eðb1ÞEðb2Þ 1⁄4 Eðb1 b2Þ for any b1; b2 2 f0; 1g, while the PIR protocol of Chang [8] and Lipmaa [25] are based on the Damgard-Jurik homomorphic encryption E0 [11],”
A Fast Single Server Private Information Retrieval Protocol with Low Communication Cost (2014, methodology): “– Chang’s protocol [8] requires n modular multiplications and 2 log n modular expo-nentiations.”
Keyword Search and Oblivious Pseudorandom Functions (2005, methodology): “[4] (based on the Φ-hiding assumption) or the schemes of Chang [6] or Lipmaa [21] (based on the Paillier and Damg̊ard-Jurik cryptosystems, respectively).”
Public Key Encryption That Allows PIR Queries (2007, background): “[8, 10, 24]; and O( √ n log(3) n) for deleting messages.”
A Lattice-Based Computationally-Efficient Private Information Retrieval Protocol (2007, background): “In 2004, there was a rediscovery of Stern’s proposal [7], and a proposition by Lipmaa [8] which is basically Stern’s construction with the recently discovered length-flexible homomorphic encryption scheme of Damgärd and Jurik [9].”
On the Computational Practicality of Private Information Retrieval (2006, methodology): “We note that our results hold immediately for other mechanisms such as [24, 26, 49].”
An Oblivious Transfer Protocol with Log-Squared Communication (2005, background): “([Ste98, Cha04 ] erroneously claims that the communication of HomCPIRn ‘ ( ) is ( ) k.) While even in the optimal case, HomCPIRn ‘ ( ) has superpolylogarithmic communication, HomCPIR n ‘ ( ) is significantly more communication-efficient than CMSn ‘ for all relevant database sizes n 280.”
This Paper Is Included in the Proceedings of the 12th Usenix Symposium on Operating Systems Design and Implementation (osdi '16). Unobservable Communication over Fully Untrusted Infrastructure Unobservable Communication over Fully Untrusted Infrastructure (unknown): “We focus on computational PIR (CPIR) schemes [10] [28] [30] [57] [58] [73] [77] [135] that hide users' access patterns under cryptographic hardness assumptions.”
Polynomial Batch Codes for Efficient IT-PIR (2016, methodology): “In this approach, the client encrypts the vector e⃗i component-wise using a semantically secure, additively homomorphic encryption scheme [11] (for instance, Paillier [44] or Damgård and Jurik’s generalization thereof [19]),1 and then it sends the encrypted vector to the database server.”
Robust Information-Theoretic Private Information Retrieval (2002, background): “Other single-server protocols with polylogarithmic communication complexities, based on different hardness assumptions, were presented in [21], [45], and [33].”