A survey of single-database private information retrieval: techniques and applications <s> A Brief Description of the Protocol <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> BIB001 </s> A survey of single-database private information retrieval: techniques and applications <s> A Brief Description of the Protocol <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> BIB002
We now have enough information for a basic understanding of how and why the PIR protocol of BIB001 works. First, we will begin with the "how". Continuing with our preceding notation, suppose that X = {x i } n i=1 is our database, with each x i ∈ {0, 1}, and again, suppose that the index of interest to U is i * . The protocol executes the following steps, involving a database DB and a user U. 1. U sends a random seed for a publicly known prime sequence generator to DB, the primes being of intermediate size  . 2. U computes p i * , the i * -th prime in the sequence based on the random seed. 3. U finds a composite number m that φ-hides p i * , and sends m to DB. In particular, we have that m at random, and computes R ∈ Z * m as follows: 5. U receives R from DB as the response, and determines that x i * = 1 if and only if R ∈ H p i * . These steps are essentially the entire protocol at a high level. However, it may not be immediately obvious that the statement R ∈ H p i * has much to do with the statement x i * = 1. But using the 3 facts we established early on, it isn't too hard to see that these are in fact equivalent with very high probability. From our first fact, we know that ϕ pi ∈ Aut(G) whenever i = i * with overwhelming probability, since the only way for this to not be the case is if p i | φ(m). However, due to the fact that there are at most only a logarithmic number of prime divisors of φ(m) out of many choices, this event will be extremely unlikely BIB002 . So, all of the ϕ pi are automorphisms, except for ϕ p i * . From our next fact, we know that with very high probability r ∈ H p i * , where r ∈ Z * m was the element randomly chosen by DB. Since the map is at least p i * to 1, the entire group is at least p i * times the size of H p i * . So, if we were to pick an element at random from Z * m , there is at best a 1 p i * chance that it will be in H p i * . So, in the length of our primes p i , there is an exponentially small probability that a random r will be in H p i * . Finally, we noted that the subgroups H pi are characteristic subgroups, and hence our fixed by every automorphism of Z * m . In particular, H p i * Z * m . So, all of the  Revealing a large prime dividing φ(m), (p > 4 √ m) enables one to factor m, so the primes must be chosen to be small. BIB002 According to the prime number theorem, there are approximately which is negligibly small as the length of m in bits (i.e., log m, the security parameter) increases. automorphisms {ϕ pi } i =i * will preserve this group: things outside will stay outside, and things inside will stay inside, and of course ϕ p i * moves every element into H p i * . I.e., We can trace the path that r takes to become R and see what happens: We have that the element r begins outside of the subgroup H p i * and then r is moved by many maps, all of which come from the set depending on whether or not x i = 1. But what is important is that all of these maps are automorphisms, which therefore fix H p i * . So, no matter what the configuration of the first i * − 1 elements of the database, r will have not moved into H p i * at this point. Next, we conditionally apply the map ϕ p i * depending on whether or not x i * = 1, which conditionally moves our element into H p i * . This is followed by the application of more automorphisms, which as we have seen have no effect on whether or not the response R will be in H p i * . So, since H p i * is fixed by every automorphism, the only chance that r has to move from outside H p i * to inside H p i * is if the map ϕ p i * is applied, which happens if and only if x i * = 1. Hence, we have that (with overwhelming probability) R ∈ H p i * if and only if x i * = 1. The privacy this protocol can be proved directly from the Φ-Hiding assumption, although it may be more pleasant to think of this in terms of the indistinguishability of the subgroup H pi to a party not knowing the factorization of m. Now, let us take a look back and examine the communication to see why this was useful. The challenge of creating PIR protocols is usually to minimize the amount of communication. A PIR protocol with linear communication is quite trivial to construct: just transfer the entire database. This is of course not very useful. The PIR protocol we have described above, however, has nearly optimal communication. The database's response is a single element R ∈ Z * m which has size proportional to the security parameter alone (which must be at least logarithmic in n), and the user's query has the size of the security parameter, and the random input to a prime sequence generator, which could also be as small as logarithmic in n. So, we have constructed a PIR protocol with only logarithmic communication, which is of course optimal: If DB wants to avoid sending information proportional to the size of the database, then U must somehow communicate information about what index is desired, which requires at least a logarithmic amount of communication. However, with the recommended parameters for security, the total communication is approximately O(log 8 n).