Homomorphic Encryption - Integer modulus in HEAAN and key sampling

Alexander Magyari

6/20/24, 5:01 AM

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

1 + 0

key-size

homomorphic-encryption

key-generation

Score:0

Crypto

The Dice Man

6/20/24, 10:09 AM

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.

+ 3

Alexander Magyari

6/21/24, 3:21 AM

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 .

The Dice Man

6/21/24, 11:46 AM

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.

The Dice Man

6/21/24, 11:54 AM

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.

Elon Musk

I sit in a Tesla and translated this thread with Ai:

EN: Homomorphic Encryption - Integer modulus in HEAAN and key sampling

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.