# Homomorphic Encryption - Integer modulus in HEAAN and key sampling

I am trying to wrap my head around Homomorphic encryption, specifically the HEAAN/CKKS scheme. I am reading through the publication, but I am getting stuck on page 11, namely the KeyGen and Enc functions.

My issue in understanding comes from the generation of the public key: $$p.k.\leftarrow (b,a)$$ $$b \leftarrow-as+e(modq_L)$$ $$q_l = p^l\cdot q_0$$ where $$l$$ denotes the multiplicative level, $$0, and $$a$$ is sampled uniformly from $$R_{qL}$$. For my question's sake, lets assume that a polynomial coefficient for vector $$a$$ happens to be $$q_L-1$$. When encoding a message $$m$$, which is defined as $$v \cdot p.k. + (m + e0, e1)(mod q_L)$$

and $$e0$$/$$e1$$ being Gaussian errors, isn't it likely that there would be an overflow of the coefficients, causing inaccuracies in the decoded output? Should $$a$$ be sampled over $$q_1$$ (the integer modulus of level 1) as opposed to the maximum integer modulus $$q_L$$?

First of all, the multiplicative depth $$L$$ and thus the selection of your ciphertext modulus $$Q_L$$ is important for guaranteeing a certain number ($$L$$) of correct ciphertext multiplications before needing to bootstrap the ciphertext. After once selecting $$L$$ resp. $$Q_L$$, it is fixed for the scheme, i.e. all future operations/encryptions. Apart from that, $$L$$ is an independent parameter, which has no "impact" on the correctness of the techniques of Encoding, Encrypting, Decrypting, etc.
Now turning to what I believe is what you wanted to know: Indeed there is an overflow of $$a$$, i.e. the uniformly sampled "random component" of the ciphertext. Especially when you multiply $$a$$ with the secret key and add an error and a message $$m$$, you should not be able to retrieve $$m$$, due to the fact that they are overflowing the modulus (by far) and thus look completely random afterward (RLWE security is based on that construction). But there is a technique to protect $$m$$ from small errors: Encoding $$m$$ via a scaling factor ($$\Delta$$ in the paper) ensures that everything gets decrypted correctly.
• Yes, it's mandatory. Maybe I was a bit imprecise, but you don't have to protect $m$ from the overflow, but rather from the errors. The overflow is just part of the system. Say, you work modulo $Q$ and encode $m \in {0,...,T-1}$ with $\Delta m$, and $\Delta = Q/T$. Then you add error(s) $e$ due to computations. That means, you have a ciphertext like $(a,-a*s+\Delta m +e)$. Meanwhile, you work mod $Q$ and overflow. Commented Jun 21, 2023 at 11:46
• As you decrypt the $-a*s$ part gets removed first. Then you perform a rounded integer division by $\Delta^{-1}$ and if $round(\Delta^{-1} e) = 0$, because $e$ is small enough, you retrieve $m$ correctly. Commented Jun 21, 2023 at 11:54