0
$\begingroup$

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<l\leq L$, 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$?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
0
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Is it the right interpretation that not only can the public key overflow a+m, but that it is expected? Could you please elaborate on how delta affects protecting the message from overflow? I understand how it can be used to maintain precision, but I still don't see the how the plaintext message could be preserved after the encryption process, given that the addition of a results in a modular overflow . $\endgroup$
    – Alexander Magyari
    Commented Jun 21, 2023 at 3:21
  • $\begingroup$ 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. $\endgroup$
    – The Dice Man
    Commented Jun 21, 2023 at 11:46
  • $\begingroup$ 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. $\endgroup$
    – The Dice Man
    Commented Jun 21, 2023 at 11:54

Your Answer

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

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