3
$\begingroup$

In Brakerski and Vaikuntanathan's homomorphic encryption scheme, the relinearization function turns a 3-element cipher back to a 2-element cipher by using a set of public homomorphism keys (https://eprint.iacr.org/2011/405.pdf, see section titled "An Optimization to Reduce Ciphertext Size").

I do not understand the point of encrypting the base-t digits of $c_2$ instead of just encrypting $c_2$ as a whole. Can someone explain? For example, instead of publishing a large set of homomorphism keys encrypting $t^is^2$ (where s = secret key): $$hk_i = (a_i, b_i=-(a_is + te_i) + t^is^2)$$for each i, and making the untrusted server build $c_2s^2$ out of these components, you could just publish a single key $$hk = (a, b=-(as+te) + s^2)$$and have the relinearization operation be $$c_0^{relin}=c_0+c_2b$$ $$c_1^{relin}=c_1 + c_2a$$ and the decryption would yield $$m=c_0^{relin} + c_1^{relin}s$$$$=c_0+c_1s+c_2as + c_2b$$$$=c_0+c_1s + c_2s^2-tec_2$$which, taken mod t, gives the correct result of the homomorphic multiplication. Is there a problem with this much simpler way? Why decompose $c_2$ into digits?

$\endgroup$

1 Answer 1

3
$\begingroup$

The decomposition helps with the noise growth of your scheme.

You see, the decryption only works if you "error" (here the terms you denote by $e$) is small enough. If $t*e$ grows beyong the modulus (all the computations are done modulo some number, let's say $q$), the mod $t$ operation won't yield the message $m$, but $m$ + $t*e$ mod $q$.

Now when you're multiplying 2 ciphertexts, the errors get multiplied, and they also get multiplied by the plaintext. Hence, you need your plaintext to be small enough, so $s^2$ cannot be used directly for this reason. When you decompose it in binary, you will have a sum of $log(q)$, but each of those will have a much smaller noise, because they only get multiplied by at most $t$.

$\endgroup$
3
  • $\begingroup$ I don't understand. When you recombine all $t^i*s^2$ with their corresponding $c_2$ digits base-t, the error will grow to the same amount as if you only used a single key hk and built $c_2*s^2$ right off the bat, right? $\endgroup$ Jun 22, 2018 at 22:59
  • 2
    $\begingroup$ No, the error is not multiplied by $t^i$, first $s$ is squared, and afterwards, it's encrypted with fresh error $\endgroup$ Jul 3, 2018 at 13:18
  • $\begingroup$ Ah, it makes sense now $\endgroup$ Jul 9, 2018 at 17:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.