What is the purpose of decomposing ciphertext into digits during relinearization in Brakerski Vaikuntanathan homomorphic encryption?

Question

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?

Answer 1

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$.