ModSwitch operation in step 1 of Algorithm 2 - 2021/204

Library Questions
1

I am trying to understand Algorithm 2 in 2021/204.

I think the first ModSwitch implementation corresponds to this function call in OpenFHE. Is that correct ?

Checking FastExpandCRTBasisPlOverQ reveals that it uses Equation 5 of 2021/204 and divides the result by Q to make error caused by Q-overflow of u negligible. This is due to using qInvModpi instead of qHatModPi. Is this right ?

However, I don’t see multiplication by P. Is that because P vanishes over modulus P ?

I also needed to confirm that ScaleAndRound function implements Simple Scaling in CRT representation in 2018/117.

Thanks!

2

HI @jmall,

Instead of EvalSquare, I suggest examining the code for EvalMult (openfhe-development/bfvrns-leveledshe.cpp at v1.0.2 · openfheorg/openfhe-development · GitHub)

ModSwitch and basis extension are done using one call:

// Switch ciphertext2 from basis Q to P to PQ.
cv2[i].FastExpandCRTBasisPloverQ(basisPQ);

Multiplication by P is done at openfhe-development/dcrtpoly.cpp at v1.0.2 · openfheorg/openfhe-development · GitHub

Regarding ScaleAndRound, there are multiple versions of it (with different API), two are for HPS (with doubles; 1st is for decryption [Simple Scaling] and 2nd one is for multiplication in BFV) and one of them is for BEHZ (without doubles).

3

Thanks for your reply @ypolyakov!

I notice here that we calculate - (P * ct) mod Q. Is this inspired from remark 3.1 ?

4

Yes, it is related to modulus switching and Remark 3.1. A more general form of modulus switching is discussed in Appendix E of https://eprint.iacr.org/2021/204.pdf, which should directly answer your question.

2 Likes