divide_and_round_q_last_inplace math

[lattice0]

I've been reading the pubkey encryption, which does modulus witching, which it claims it's done in divide_and_round_q_last_inplace. I couldn't find the math about this. Initially I though it was base conversion, because you're just switching form base Q to base Q', which has one less element. However, the BEHZ paper "Implementation and Performance Evaluation of
RNS Variants of the BFV Homomorphic Encryption
Scheme" (https://eprint.iacr.org/2018/589.pdf) does not seem to have the math implemented in this function.

Could you point me to the exact math on this?

[fionser]

1. From math, the modulus switching scale the ct from a larger modulus (say Q) to a smaller modulus Q' (Q' < Q).
2. To do so, we simply compute round(ct*Q'/Q).
3. Since we are talking about RNS variant, the inverse Q/Q' is just the last small prime in the prime chain (say q)
   Thus what divide_and_round_q_last_inplace do is round(ct/q)

[lattice0]

@fionser do you mean that in order to convert from basis (a1,a2,a3) we can multiply the RNS number, coefficient-wise, by a1a2/(a1a2*a3) = 1/a3? How can this convert the basis?

[lattice0]

@fionser The representation of 4 in (3,5,7) is (1,4,4). When we divide and round: (1/7, 4/7, 4/7) we get (0,1,1) which is not 4 in basis (3,5)

[WeiDaiWD]

It's suppose to give you round(4 / 7) = 1. The algorithm is described in the comments of divide_and_round_q_last_inplace. It is way more complicated than what you have described -- (1/7, 4/7 , 4/7).

[lattice0]

@WeiDaiWD oh right forgot and divide the left-side 4, I'm doing round(4/7) = (round(1/7),round(4/7), round(4/7)) but then I get 1 = (0,1,1). If I discard the latest element I get (0,1) which is not the representation of 1 in (3,5). I seem the algorithm and understood some of the stuff but it looks a little bit different from the one mentioned here. For instance, inverse of M/mi

[WeiDaiWD]

round(4/7) = (round(1/7),round(4/7), round(4/7))

This is different from the code or what fionser described.

[fionser]

• Indeed the fast basis convert algorithm computes floor(4/7)
  we use the relationship round(4/7) = floor((4 + floor(7/2)) / 7)
• 4 in basis (3, 5, 7) is （1，4, 4)
  • floor(7/2) mod 3 = 0; floor(7/2) mod 5 = 3; floor(7/2) mod 7 = 3
  • Then 4 + floor(7/2) in basis is (1, 2, 0)
• the divide_and_round_q_last computes
  ( 1 - 0 )*7^{-1} mod 3 = 1
(2 - 0)* 7^{-1} mod 5 = 1
  That is in (1, 1) in the basis (3, 5) is 1 , i.e., round(4/7)

[lattice0]

Got it @fionser. Now we have the 3rd basis element of all coefficients 0, so in essence we have the representation of floor(ct/q) in basis of size one less than before. But what guarantees that floor(ct/q) still decrypts to the same plaintext? Am I missing something more? What about repeated iterations of the same stuff until we reach a smaller basis?

Why aren't you using the BeHZ base conversion formula?

Thank you!

[fionser]

• The fast basis convert (easy to understand and explain) might introduce some rounding errors which is fine for CKKS and (in the key switching steps)
  For the BFV scheme, we need exact result, which we need more complicated BEHZ algorithm.
• Basically floor(ct/q) will not decrypts to the "same" plaintext m.
  Whenever we use this divde-then-round function, m should be some multiple of q (or close to q, or
  m = 0). The divde-then-round function will gives you a ct that decrypts to round(m/q).

[lattice0]

@fionser now I get it. I saw it being used in

SEAL/native/src/seal/encryptor.cpp

Line 138 in 88bbc51

SEAL_ITERATE(iter(temp, destination), temp.size(), [&](auto I) {

but I forgot it was on the encryption of 0, not m. So yes, it still decrypt to 0. But why not just encrypt directly with a subset of the basis, instead of doing this modulus switching? By the way, is this the BeHZ algorithm?

I'm asking because I'm doing internal stuff on SEAL, so I did encrypt ct with a subset of size 2 from a basis of size 3, instead of doing modulus switching, then operated with conventional ciphertexts encrypted with the modulus switching technique and it worked.

[WeiDaiWD]

If you encrypt 0 with two primes q0 and q1 and an freshly sampled error e, now the noise size is ||e|| after decryption.

If you encrypt 0 with three primes q0, q1, and q2 and an freshly sampled error e, now the noise is also ||e|| after decryption.
Then, if you perform divide (with flooring or rounding) the ciphertext by q2, you end up with an encryption of 0 with two primes q0 and q1. The new ciphertext has noise size close to (or actually a bit larger than) ||e||/q2 after decryption.

We inserted this extra scaling of fresh encryption of zero to reduce the noise in a freshly encrypted ciphertext. This matters a lot to CKKS.

[WeiDaiWD]

This is not one of the algorithms in BEHZ. The BEHZ paper mainly deal with conversions between disjoint basis. In the case of divide_and_round_q_last_inplace, we are converting to a sub basis while inserting a division/rounding operation.