Modulus reduction with base conversion (RNS domain)

FHE Questions
1

Hi, I’m trying to implement approximate modulus switching algorithms in the following RNS CKKS (p.8-9) ( A Full RNS Variant of Approximate Homomorphic Encryption)

There’s no problem with the modulus raising(modup) implementation (Alg.1), but I can’t understand what is going on in the modulus reduction(moddown) algorithm.

For example, When I put [18 28 73](mod 131 137 173) rns vector and modup with (mod 57 73 113 233), the output was [50 5 105 169 18 28 73](mod 57 73 113 233 131 137 173) which was correct.
However, when I moddown the previous modup vector back again, the output was [129 135 171](mod 131 137 173) which was -2 values of the original moduli; with other parameters, there are similar unacceptable outputs. (I expected [18 28 73], the rear values of the modup vector)

Is it just because of an error term that occurs in approximate computing?
or should there be some RNS multiplication between modulus raising and modulus reduction?

Sorry for the poor explanation of my lack of understanding :sob:

2

@ghcrpt

The approximate modular reduction is implemented in OpenFHE as ApproxModDown (see openfhe-development/dcrtpoly.cpp at v0.9.3 · openfheorg/openfhe-development · GitHub). The algorithmic description for the BGV case is provided on page 33 of Revisiting Homomorphic Encryption Schemes for Finite Fields. Note that BGV has two extra steps: multiplying by t and t^{-1}; CKKS and BFV do not have it. You can see this from the implementation in OpenFHE where the same key switching implementation is used for all three schemes.

Note also also that the fast basis extension (called ApproxSwitchCRTBasis in OpenFHE) has to be applied to the coefficient representation of the polynomials (as can be seen from the code).

For a more general formulation of modulus switching, you can review the derivations in Appendix E of Revisiting Homomorphic Encryption Schemes for Finite Fields

Please let me know if you have any further questions on modulus switching after looking at these references.

2 Likes