I’m trying to understand the rescaling in CKKS. I am working under the assumption that OpenFHE’s implementation of CKKS is based on the paper [KPP21], that is, when we set the scaling technique as FLEXIBLEAUTO, OpenFHE uses a different scaling factors \Delta_{i} for each for each level i, as described in the table in page 17 of [KPP21]. Thus, my first question is if this assumption is correct.

Then, still following [KPP21], I would expect the ciphertexts to be rescaled before each multiplication. However, it seems that before the first multiplication, ciphertexts are not rescaled. Could one explain why?

Third: If we rescale before multiplying, then, after we multiply, the scaling factor is \Delta_i^2 instead of \Delta_i, right? So, does GetNoiseScaleDeg() return this exponent (either 1 or 2)?

And fourth and final question, if we can indeed have scaling factor \Delta_i^2, then, when we reach the last level, we have \Delta_0^2. But the ciphertext is defined modulo q_0 only (i.e., all the other primes were dropped). How would it possible if \Delta_0^2 > q_0? Can we even decrypt then?

(Sorry for so many questions in one single question, but they all seem related. Please, if you can just answer some of them, that is fine, go ahead!)

Thus, my first question is if this assumption is correct.

Yes

Then, still following [KPP21], I would expect the ciphertexts to be rescaled before each multiplication. However, it seems that before the first multiplication, ciphertexts are not rescaled. Could one explain why?

Please read “Our work” section (pages 2 and 3). We explain there why we suggest doing the rescaling right before the next multiplication.

So, does GetNoiseScaleDeg() return this exponent (either 1 or 2)?

Yes, it becomes 2.

Can we even decrypt then?

\Delta_0^2 means the final rescaling has not been done yet (2 RNS limbs are left rather than 1). This is equivalent to regular CKKS when rescaling is done to \Delta (which consumes 1 RNS limb/level and, hence, there is only 1 RNS limb left).

I had actually read that Section already (and even the more technical one in the body of the paper). I understand the motivation of rescaling before multiplying. But I am wondering what it means for the first multiplication. If we multiply two fresh ciphertexts, both with scaling factor \Delta_L = q_L, we don’t rescale them before multiplying? Otherwise, we would obtain ciphertexts with scaling factor \Delta_L / q_L = 1, then multiply them, which seems weird. Btw, this observation is consistent with my experiments with OpenFHE (i.e., when I print the number of primes before and after the first multiplication, they are the same, indicating that no rescale was performed).

And about the decryption, does this mean that a user of OpenFHE has to be aware of this and stop multiplying when there are two primes left? Indeed, I coded a simple example where I run many multiplications and try to decrypt. When there are two primes left, the decryption works fine. But then, I multiply again, and the decryption fails.

Initial level ctxt1: 0
depth: 5
Number of primes in the moduli chain of ctxt1: 6
Number of primes in the moduli chain of cMul: 6

Decrypting cMul while it has 2 primes in the moduli chain
Decrypted result: (0.680667, 0.259191, 0.496319, 4.95521e-07, 4.75742e-09, 0.0068314, 5.47028e-08, 8.02298e-05, … ); Estimated precision: 49 bits

Decrypting cMul while it has only 1 prime in the moduli chain
terminate called after throwing an instance of ‘lbcrypto::OpenFHEException’
what(): /home/hilder/Documents/gitRepos/openfhe-src/src/pke/lib/encoding/ckkspackedencoding.cpp:l.537:Decode(): The decryption failed because the approximation error is too high. Check the parameters.
Aborted (core dumped)

In FLEXIBLEAUTOEXT, an auxiliary modulus (20-bit or so) is added when generating fresh ciphertexts. The high-level idea it reduce the fresh encryption noise to modulus switching/rescaling noise. Rescaling happens before first multiplication in this case. This is explained in the paper. The mode is referred to as RE-CKKS-DE.

In FLEXIBLEAUTO, no rescaling is done before first multiplication. This mode is referred to as CKKS-DE.

For both of these modes, rescaling is done before the following multiplications.

As far as decryption is concerned, the user specifies the multiplicative depth at crypto context generation. If the user exceeds this multiplicative depth when performing multiplications, then the decryption will not succeed (by design). For example, your code sets the multiplicative depth to 5 but tries to evaluate a circuit with 6 multiplicative levels; hence, the decryption will fail (by design), regardless which scaling mode for CKKS is used.