Modulus switching operation for CKKS scheme

[xuann6]

trafficstars

Hi there, Recently I'm reading paper of HEAAN : https://link.springer.com/chapter/10.1007/978-3-319-70694-8_15 This paper mentioned that homomorphic operations of ciphertexts at different levels has two different candidates :

1. rescaling procedure as we use in CKKS
2. modular reduction

I realize that we can use rescaling procedure to switch modulus level when evaluating 2 ciphertexts with different level, but I'm confuse by modular reduction procedure mentioned in that paper. And here's my question :

1. When using RNS representation for modular reduction, is "dropping" a number from chosen basis the only thing we need to do ?
2. If it's possible to reduce ciphertext levels without modifying plaintext message after decryption (namely the modular reduction procedure mentioned in the paper ), can we increase ciphertext levels without modifying plaintext message inversely? If it's possible, what's the actual oepration we have to do for ciphertext under RNS representation?

Thank you for reading my questions, and btw I'm not a native speaker so please forgive my bad grammar. Thanks a lot.

[Pro7ech]

Hello @xuann6,

1. Yes, if you have a ciphertext modulo Q = q0 * q1, represented as two polynomials, one modulo q0, and one modulo q1, then dropping the polynomial modulo q1 is equivalent to switching the modulus fro Q = q0 * q1 to Q' = q0.
2. Yes you can drop primes without affecting correctness as long as the norm of the message remains smaller than the ciphertext modulus, i.e. ||m(X)|| < Q.
3. Doing the inverse, that is going from Q = q0 to Q' = q0 * q1 will not decrypt to the same message, but to some new message m'(X) = m(X) + I(X) * q0 where I(X) = [[-as]_(mod q0) + as]_(mod q0*q1). This is in fact the ModUp step of the bootstrapping for the CKKS scheme, the rest of the bootstrapping circuit being the homomorphic removal of the polynomial I(X).

[xuann6]

Hi @Pro7ech,

Thanks for your reply. For the ModUp you mentioned in bootstrapping process, is that algorithm the same as key-switching procedure in the CKKS scheme under CRT representation? Since there are many similar words like ModUp or Modular Raise, I need to check I didn't misunderstand your meaning.

Thank you very much and wish you a nice day.

[Pro7ech]

Hi @xuann6,

You wouldn't want to use this one because it adds additional multiples of the original modulus, instead the one from An Improved RNS Variant of the BFV Homomorphic Encryption Scheme should be used. However, this would only be the case if your starting RNS base has more than one modulus. Usually the bootstrapping is called when there is only one modulus left in the RNS basis, so the basis extension (ModUp) becomes trivial.

[lattice0]

But there's no bootstrapping on SEAL, right? When the primes end, we have no choice but to decrypt, right?