process a ciphertext directed to the user, leaving less work for the user to do. In our setting, the encrypter or evaluator plays the role of the server, postprocessing the ciphertext so as to leave less work for the decryption algorithm to do.

• Decrypte*(sk*, c*): Output LSB(c) XOR LSB(ëSi siziù).

Decryption works, since (up to small precision errors)

Si sizi = Si c • siyi = c/p mod 2.

To ensure that the rounding is correct despite the low precision, we need c to be closer (than the trivial p/2) to a multiple of p (say, within p/16). This makes Fe* smaller than Fe, since Fe is limited to functions where | f(a1, …, at)| < p/16 when the ai are N bits. This makes only a small difference.

The important point regarding Decrypte* is that we replace the multiplication of c and 1/p with a summation that contains only a nonzero terms. The bits of this summation can be computed by a polynomial of degree a • polylog(a), which e can handle if we set a to be small enough.

 

•;Adde* (pk*, c 1, c 2): Extract c1 and c2 from c 1 and c 2. Run c ¬ Adde(pk, c1, c2). The output ciphertext c consists of c, together with the result of postprocessing c with y® • Multe*(pk*, c 1, c 2) is analogous.

5. 3. how to add numbers

To see that e can handle the decryption function plus an additional gate when a is set small enough, let us consider the computation of the sum Si sizi. In this sum, we have b numbers a1, …, ab, each ai expressed in binary (ai,0, …, ai, −) with  = O(log a), where at most a of the ai’s are nonzero (since the Hamming weight of s is a). We want to express each bit of the output as a polynomial of the input bits, while minimizing the degree of the polynomial and the number of monomials.

Our approach to the problem is to add up the column of LSBs of the numbers—computing the Hamming weight of this column—to obtain a number in binary representation. Then, we add up the column of penultimate bits, etc. Afterward, we combine the partial results. More precisely, for j Î [0, −], we compute the Hamming weight bj, represented in binary, of (a1,j, …, ab,j). Then, we add up the  + 1 numbers b0, …, 2−b− to obtain the final correct sum.

Conveniently, the binary representation of the Hamming
weight of any vector x® Î {0, 1}t is given by
(e2 ëlog tû (x1, ..., xt) mod 2, ..., e20 (x1, ..., xt) mod 2)

where ei(x1, …, xt) is the ith elementary symmetric polynomial over x1, …, xt. These polynomials have degree at most t. Also, we know how to efficiently evaluate the elementary symmetric polynomials. They are simply coefficients of the polynomial p(z) = Õt i= 1 (z – xi). An important point is that, in our case, we only need to evaluate the polynomials up to degree a, since we know a priori that each of the Hamming weights is at most a. We saw in Section 3. 3 that we can handle elementary symmetric polynomials in t variables of degree up to about l/log t = W(l/log l) for our suggested parameters. We can set a to be smaller than this.

104 CommunICAtIonS of the ACm | MArCh 2010 | VoL. 53 | no. 3

The final step of computing the sum of the bj’s does not require much computation, since there are only  + 1 = O(log a) of them. We get that a ciphertext encrypting a bit of the overall sum has noise of at most N • a • g(log a) bits for some polynomial g of low degree. If the final sum modulo 2 is (b¢0, b¢– 1,. ..) in binary, then the rounding operation modulo 2 is simply b¢0 XOR b¢– 1. With the additional XOR operation in decryption, and possibly one more gate, the noise after evaluating the decryption function plus a gate has at most N • a • h(log a) bits for some polynomial h.

The scheme e becomes bootstrappable when this noise has at most log(p/16) = P − 4 bits. For example, this works when a = l/polylog(l), N = l, and P = l2.

5. 4. Security of the transformed scheme

The encryption key of e contains a hint about the secret p. But we can prove that e is semantically secure, unless either it is easy to break the semantic security of e (which implies that the approximate gcd problem is easy), or the following sparse (or low-weight) subset sum problem (SSSP) is easy: given a set of b numbers y® and another number s, find the sparse (a-element) subset of y® whose sum is s.

The SSSP has been studied before in connection with server-aided cryptosystems. If a and b are set appropriately, the SSSP is a hard problem, as far as we know. In particular, if we set a to be about l, it is hard to find the sparse subset by “brute force,” since there are (ba) » b a possibilities. If the sparse subset sum is much closer to 1/p than any other subset sum, the problem yields to a lattice attack. But these attacks fail when we set b large enough (but still polynomial in l) so that an exponential (in l) number of subset sums are as close to 1/p as the sparse subset. Concretely, we can set b = l5 • polylog(l).

6. ConCLuSIonS

We now know that FHE is possible. We already have the scheme presented here, the lattice-based scheme by Gentry, 2, 3 and a recent scheme by Smart and Vercauteren. 7

There is still work to be done toward making FHE truly practical. Currently, all known FHE schemes follow the blueprint above: construct a bootstrappable somewhat homomorphic encryption scheme e, and obtain FHE by running Evaluatee on e’s decryption function. But this approach is computationally expensive. Not only is the decryption function expressed (somewhat inefficiently) as a circuit, but then Evaluatee replaces each bit in this circuit with a large ciphertext that encrypts that bit. Perhaps someone will find a more efficient blueprint.

The scheme presented here, while conceptually simpler, seems to be less efficient than the lattice-based scheme. To get 2l security against known attacks—e.g., on the the approximate gcd problem—ciphertexts are l5 • polylog(l) bits, which leads to l10 • polylog(l) computation to evaluate the decryption function. The lattice-based scheme with comparable security has l6 • polylog(l) computation. This is high, but not totally unreasonable. Consider: to make RSA 2l-secure against known attacks—in particular, against the number field sieve factoring algorithm— you need to use an RSA modulus with approximately l3