Computationally Private Information Retrieval with Polylogarithmic Communication

By Christian Cachin, Silvio Micali, Markus Stadler. 1999

How researchers see this paper

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

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.”
Private Information Retrieval With Side Information (2017, background): “If computational (cryptographic) privacy is desired, then PIR schemes with lower communication overhead do exist [3], [4], but they do not offer information-theoretic privacy guarantees and usually have high computational complexity.”
Priced Oblivious Transfer: How to Sell Digital Goods (2001, background): “Assuming either a general homomorphic encryption [16, 17, 27] or a stronger number theoretic assumption [5], the asymptotic communication complexity of PIR can be made very small.”
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.”
Multi-query Computationally-Private Information Retrieval with Constant Communication Rate (2010, methodology): “Cachin, Micali and Stadler [2] gave the first CPIR-protocol for retrieving one bit out a database where the communication complexity is polylogarithmic in the database size.”
An Oblivious Transfer Protocol with Log-Squared Communication (2005, methodology): “Fix k = 1024 and s = 1. The difference between the communications of the linear Aiello-Ishai-Reingold CPIR AIRn ‘ [AIR01] (with communication 2(n + 1)k), the polylogarithmic CPIR CMSn ‘ [ CMS99 ] (with possibly overly optimistic setting = min(80; log2 n) and f = 4; whether the CMSn ‘ CPIR is actuall”
Efficient Computationally Private Information Retrieval from Anonymity or Trapdoor Groups (2010, background): “The work in [3, 15, 12, 6] demonstrated schemes with polylogarithmic communication complexity.”
Computationally Secure Oblivious Transfer (2004, methodology): “[11] where the communication complexity is poly-logarithmic in N .”
Revisiting the Computational Practicality of Private Information Retrieval (2011, background): “Several other single-server PIR schemes followed, each making some intractability assumption [2, 6, 20].”
Secure multi-party computation problems and their applications: a review and open problems (2001, methodology): “Studies [26, 8, 24, 23, 27, 30, 28, 19] have shown that one can design a protocol to solve the PIR problem with much better communication complexity than by using the general theoretical solutions.”
Robust Information-Theoretic Private Information Retrieval (2002, methodology): “A single-server protocol with a polylogarithmic communication complexity, based on a new number-theoretic intractability assumption called the � -hiding assumption, is presented in [ 19 ].”
Bandwidth Efficient PIR from NTRU (2014, methodology): “Other cPIR constructions include [28] which is based on the computational difficulty of deciding whether a small prime p divides φ(m) for any composite integer m of unknown factorization where φ() denotes Euler’s totient function.”
Efficient oblivious transfer protocols (2001, background): “Since in all known single-server PIR protocols [6, 22] the sender performs a huge number of operations”
Protocols for Secure Remote Database Access with Approximate Matching (2001, methodology): “Studies [19, 4, 16, 15, 20, 22, 21, 11] have shown that one can design a protocol to solve the PIR problem with much better communication complexity than by using the general theoretical solutions.”
Batch codes and their applications (2004, methodology): “In this case one can combine the single-server PIR protocol s of [20, 6] with our batch code constructions to get protocols that are “essentially optimal” with respect to both communication and computatio n.”
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.”
Public Key Encryption That Allows PIR Queries (2007, methodology): “A seemingly related concept is that of Private Information Retrieval (PIR) (e.g., [13] [23] [10]).”
Privacy preserving decision tree learning over multiple parties (2007, methodology): “On the other hand, in privacy preserving information retrieval , several methods has been introduced to preserve the privacy of the query poser by hiding the records retrieved from the data source [10] [12] [11] [19].”