A survey of single-database private information retrieval: techniques and applications <s> Single-Database PIR <s> We describe schemes that enable a user to access k replicated copies of a database (k/spl ges/2) and privately retrieve information stored in the database. This means that each individual database gets no information on the identity of the item retrieved by the user. For a single database, achieving this type of privacy requires communicating the whole database, or n bits (where n is the number of bits in the database). Our schemes use the replication to gain substantial saving. In particular, we have: A two database scheme with communication complexity of O(n/sup 1/3/). A scheme for a constant number, k, of databases with communication complexity O(n/sup 1/k/). A scheme for 1/3 log/sub 2/ n databases with polylogarithmic (in n) communication complexity. <s> BIB001 </s> A survey of single-database private information retrieval: techniques and applications <s> Single-Database PIR <s> We establish the following, quite unexpected, result: replication of data for the computational private information retrieval problem is not necessary. More specifically, based on the quadratic residuosity assumption, we present a single database, computationally private information retrieval scheme with O(n/sup /spl epsiv//) communication complexity for any /spl epsiv/>0. <s> BIB002 </s> A survey of single-database private information retrieval: techniques and applications <s> Single-Database PIR <s> We present a single-database computationally private information retrieval scheme with polylogarithmic communication complexity. Our construction is based on a new, but reasonable intractability assumption, which we call the φ-Hiding Assumption (φHA): essentially the difficulty of deciding whether a small prime divides φ(m), where m is a composite integer of unknown factorization. <s> BIB003 </s> A survey of single-database private information retrieval: techniques and applications <s> Single-Database PIR <s> We propose a generalisation of Paillier's probabilistic public key system, in which the expansion factor is reduced and which allows to adjust the block length of the scheme even after the public key has been fixed, without losing the homomorphic property. We show that the generalisation is as secure as Paillier's original system. We construct a threshold variant of the generalised scheme as well as zero-knowledge protocols to show that a given ciphertext encrypts one of a set of given plaintexts, and protocols to verify multiplicative relations on plaintexts. We then show how these building blocks can be used for applying the scheme to efficient electronic voting. This reduces dramatically the work needed to compute the final result of an election, compared to the previously best known schemes. We show how the basic scheme for a yes/no vote can be easily adapted to casting a vote for up to t out of L candidates. The same basic building blocks can also be adapted to provide receipt-free elections, under appropriate physical assumptions. The scheme for 1 out of L elections can be optimised such that for a certain range of parameter values, a ballot has size only O(log L) bits. <s> BIB004 </s> A survey of single-database private information retrieval: techniques and applications <s> Single-Database PIR <s> We show that general one-way trapdoor permutations are sufficient to privately retrieve an entry from a database of size n with total communication complexity strictly less than n. More specifically, we present a protocol in which the user sends O(K2) bits and the server sends n - cn/K bits (for any constant c), where K is the security parameter of the trapdoor permutations. Thus, for sufficiently large databases (e.g., when K = nƐ for some small Ɛ) our construction breaks the information-theoretic lower-bound (of at least n bits). This demonstrates the feasibility of basing single-server private information retrieval on general complexity assumptions. ::: ::: An important implication of our result is that we can implement a 1-out-of- n Oblivious Transfer protocol with communication complexity strictly less than n based on any one-way trapdoor permutation. <s> BIB005 </s> A survey of single-database private information retrieval: techniques and applications <s> Single-Database PIR <s> We study the problem of single database private information retrieval, and present a solution with only logarithmic server-side communication complexity and a solution with only logarithmic user-side communication complexity. Previously the best result could only achieve polylogarithmic communication on each side, and was based on certain less well-studied assumptions in number theory [6]. On the contrary, our schemes are based on Paillier’s cryptosystem [16], which along with its variants have drawn extensive studies in recent cryptographic researches [3, 4, 8, 9], and have many important applications [7, 8]. <s> BIB006 </s> A survey of single-database private information retrieval: techniques and applications <s> Single-Database PIR <s> We propose a one-round 1-out-of-n computationally-private information retrieval protocol for l-bit strings with low-degree polylogarithmic receiver-computation, linear sender-computation and communication Θ(klog2n+llogn), where k is a possibly non-constant security parameter. The new protocol is receiver-private if the underlying length-flexible additively homomorphic public-key cryptosystem is IND-CPA secure. It can be transformed to a one-round computationally receiver-private and information-theoretically sender-private 1-out-of-n oblivious-transfer protocol for l-bit strings, that has the same asymptotic communication and is private in the standard complexity-theoretic model. <s> BIB007 </s> A survey of single-database private information retrieval: techniques and applications <s> Single-Database PIR <s> We present a single-database private information retrieval (PIR) scheme with communication complexity ${\mathcal O}(k+d)$, where k ≥ log n is a security parameter that depends on the database size n and d is the bit-length of the retrieved database block. This communication complexity is better asymptotically than previous single-database PIR schemes. The scheme also gives improved performance for practical parameter settings whether the user is retrieving a single bit or very large blocks. For large blocks, our scheme achieves a constant “rate” (e.g., 0.2), even when the user-side communication is very low (e.g., two 1024-bit numbers). Our scheme and security analysis is presented using general groups with hidden smooth subgroups; the scheme can be instantiated using composite moduli, in which case the security of our scheme is based on a simple variant of the “Φ-hiding” assumption by Cachin, Micali and Stadler [2]. <s> BIB008
PIR was introduced by Chor, Goldreich, Kushilevitz and Sudan BIB001 in 1995 in the setting where there are many copies of the same database and none of the copies are allowed to communicate with each other. In the same paper, Chor at. al. BIB001 showed that single-database PIR does not exist (in the information-theoretic sense.) Nevertheless, two years later, (assuming a certain secure public-key encryption) Kushilevitz and Ostrovsky BIB002 presented a method for constructing single-database PIR. The communication complexity of their solution is O(2 √ log n log log N ) which for any > 0 is less then O(n ). Their result relies on the algebraic properties Goldwasser-Micali Public-Key encryption scheme  . In 1999, Cachin, Micali and Stadler BIB003 demonstrated the first single database PIR with polylogarithmic communication, under the so-called φ-hiding number-theoretic assumption. Chang BIB006 , and Lipmaa BIB007 showed O(log 2 n) communication complexity PIR protocol (with a multiplicative security parameter factor), using a construction similar to the original BIB002 but replacing the Goldwasser-Micali homomorphic encryption with the Damgård, M. Jurik variant of the Pailler homomorphic encryption BIB004 . Gentry and Ramzan BIB008 also showed the current best bound for communication complexity of O(log 2 n) with an additional benefit that if one considers retrieving more then one bit, and in particular many consecutive bits (which we call blocks) then ratio of block size to communication is only a small constant. The scheme of Lipmaa BIB007 has the property that when acting on blocks the ratio of block size to communication actually approaches 1, yet the parameters must be quite large before this scheme becomes an advantage over that of BIB008 . In general, the issue of amortizing the cost of PIR protocol for many queries has received a lot of attention. We discuss it separately in the next subsection. All the works mentioned above exploit some sort of algebraic properties, often coming from homomorphic public-key encryptions. In BIB005 work, Kushilevitz and Ostrovsky have shown how to construct Single Database PIR without the use of any algebraic assumptions, and instead relying on the existence of one-way trapdoor permutations. However, the use of the more general assumption comes with a performance cost: they show how to achieve (n − O( n k − k 2 )) communication complexity, and additionally, the protocol requires more than one round of interaction. In this survey, we give the main techniques and ideas behind all these constructions (and in fact, show a generic construction from any homomorphic encryption scheme with certain properties) and attempt to do so in a unified manner.