A survey of single-database private information retrieval: techniques and applications <s> Basic Protocols from Homomorphic Encryption <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> BIB001 </s> A survey of single-database private information retrieval: techniques and applications <s> Basic Protocols from Homomorphic Encryption <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> BIB002 </s> A survey of single-database private information retrieval: techniques and applications <s> Basic Protocols from Homomorphic Encryption <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> BIB003 </s> A survey of single-database private information retrieval: techniques and applications <s> Basic Protocols from Homomorphic Encryption <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> BIB004
In what follows, we will provide a sequence of examples of PIR from homomorphic encryption, each becoming slightly more refined and efficient. Let us suppose that the i * position of the database is desired by a user U. Keeping the notation established above, let G, G be groups which correspond to the plaintext and ciphertext of our homomorphic cryptosystem (resp.) and let g ∈ G be a non-identity element. As a first attempt at a PIR protocol, a user U could send queries of the form Then, the database can respond with using additive notation for the operation of G (and of G from this point forward) and using · to represent the Z-module action. Now U can recover the desired database bit as follows, computing and hence U determines x i * = 1 if and only if D(R) = g. Or, in the case where the discrete log is easy in G, U would compute x i * as the log of D(R) to the base g (just by division, in the case of an additive group of integers). This protocol is clearly correct, but it is also easily seen to be private. The only information received by DB during the protocol was an array of ciphertexts, which by our assumptions on the cryptosystem, each come from (computationally) indistinguishable distributions, and hence contain no information that can be efficiently extracted. For a formal proof, one can apply a standard hybrid argument. However, although our protocol is both correct and private, it unfortunately requires the communication of information proportional in size to the entire database in order to retrieve a single database element. This could have just as easily been done by sending the entire database to the user, which would also maintain the user's privacy. Setting k = log |G | as a security parameter, the user must communicate O(nk) bits. Fortunately, this can be modified into a more communication-efficient protocol without much effort. To begin, one can organize the database as a square, X = {x ij } √ n i,j=1 , and if the (i * , j * ) position of the database is desired, the user can send a query of the form defined just as before (we will ignore the j * index for reasons that will become clear shortly). Then, the database can compute R j = √ n i=1 x ij · q i for each j and send {R j } √ n j=1 back to the user as the query response. Now as we've seen, from D(R j ), U can recover {x i * j } √ n j=1 just as before. In particular, U can compute x i * j * (even though much more information is actually received). Note that the total communication involved in the protocol has now become non-trivially small: it is now proportional to √ n for each party as opposed to the O(n) communication required by our original proposal and the trivial solution of communicating the entire database to U. However, we can make further improvements still. Let be an injective map such that for all y ∈ G , each component of φ(y) is less than ord(g). I.e., one can think of the map as φ : G → Z l ord(g) . Any such map with dowe only require that both φ and φ −1 are efficiently, publicly computable. Note that in general, we will always have l > 1 since ord(g) ≤ |G| and |G| < |G |, the latter inequality following from the fact that the encryption scheme is always probabilistic (D is never injective, but of course is always surjective). Again, note that we do not ask for any algebraic conditions from the map φ; it can be any easily computed injective set map. (For example, we could just break down a binary representation of elements of G into sufficiently small blocks of bits to obtain the map φ.) Now, we can refine our query, where q i * and p j * are set to encryptions of g, but all others encrypt id G . Then, the database will initially proceed as before, computing but then further computing where φ(R j ) t represents the t-th component of φ(R j ). This is sent as the query response to U. To recover the desired data, U computes for every t ∈ [l] BIB001 and of BIB003 . Both are simply special cases of what has been described above: The work of BIB001 is based upon the cryptosystem of  , which is homomorphic over the group Z 2 , having ciphertext group Z N for a large composite N . In this case, it is simply the binary representation of a group element that plays the role of the map φ : G → Z l . I.e., we have l = k, the security parameter, and φ : Z N → Z k takes an element h ∈ Z N and maps it to a sequence of k integers, each in {0, 1} corresponding to a binary representation of h. The work of BIB003 is also a special case of this construction. Here, the protocol is based upon the cryptosystem of  , and we have G = Z N and G = Z * N 2 , hence we can greatly reduce the parameter l in comparison to the work of BIB001 . In this case, it is easy to see that we only need l = 2, which is in fact minimal, as we have discussed before. The author of BIB003 uses the map φ : Z * N 2 → Z N defined by the division algorithm, dividing by N to obtain a quotient and remainder of appropriate size. Roughly speaking, (and using C-programming notation) he uses the map x → (x/N, x%N ). However, as we have seen before, this is not necessary-any map could have been used (appropriately partitioning bits, etc.). Note also that since the discrete log in G is not hard (as we have defined it) we do not need to restrict our database to storing bits. Database elements could be any numbers in Z N . These quite generic methods also capture the work of BIB004 , as long as the appropriate cryptosystem is in place. Consider a "length-flexible" cryptosystem, for example, that of Damgård and Jurik BIB002 . Such a cryptosystem has the property that given a message of arbitrary length, and given a fixed public key, one can choose a cryptosystem from a family of systems based on that key, so that the message fits in one ciphertext block regardless of the key and the message length. Using this, we can further reduce the database's communication in our PIR protocol, using essentially the very same generic technique described above. We'll demonstrate the following: What the Damgård and Jurik system affords us is the following: instead of having only one plaintext and ciphertext group G, G , we now have a countable family at our disposal: all of which correspond to a single public key. These groups are realized by , and hence we have natural inclusion maps of G i → G i+1 . This, along with the observation that G i is cyclic for all i, are essentially the only important facts regarding this system that we'll utilize. So, G i is always cyclic, and we have a natural (although not algebraic) map This is all we need to modify our generic method. We will just replace the map φ with the maps ψ i , and accordingly, we will modify our query so that the vector for the i-th dimension encrypts id Gi in all positions except for the index of interest, which will encrypt a generator of G i . With only these minor substitutions to the abstract construction, the protocol will follow exactly as before. This will give us a protocol with communication complexity for the user U of and for the database, we require only