For QBFVInit: Delta0 = QBFVInit / PInput = about 48 bits
For Q and Bigq: Delta1 = 48 - (80 - 71) = 39 bits
Since the reduction from Q (71 bits) to Bigq (47 bits) is done via modular reduction rather than a formal modulus switching, the ciphertext is then digit-decomposed into 8-bit digits (because Bigq / Delta1 is about 8 bits). The EvalFBT procedure is applied to perform the computation modulo PDigit. After this step, the resulting ciphertext ctxtAfterFBT (which encodes m mod PDigit) is converted back from modulus Bigq (47 bits) to Q (71 bits) in order to perform the subtraction.
My concern is about this conversion step: during the transition from Bigq (47 bits) back to Q (71 bits), it seems that a scaling operation is applied in the form
ctxtAfterFBT = ctxtAfterFBT * (Q / Bigq).
Would this multiplication significantly increase the noise in ctxtAfterFBT (by roughly 24 bits)? I understand that this noise will be reduced modulo PDigit (8 bits) after the subtraction, but it still appears to grow quickly.
Would it help to control this noise if we keep the modulus of ctxtAfterFBT larger than Q (for example, by keeping one additional level) and then perform a modulus switching?
If my understanding above is incorrect, please do not hesitate to point it out!
Your understanding seems to be correct, but I do not see any issue with modulus switching from Q' to Q (here, I am using the notation of the paper and OpenFHE). Before the modulus switching from Q' to Q, the encrypted message in ctxtAfterFBT looks like \frac{Q'}{p} m + e \bmod Q'. After the modulus switching, it becomes \frac{Q}{p} m + \frac{Q}{Q'} e + e_{ms} \bmod Q, where e_{ms} is the modulus switching noise. Since \frac{Q}{Q'} e \gg e_{ms}, the relative error is roughly the same as before modulus switching, i.e., the modulus switching has a negligible effect on the noise.
If our goal were to increase the gap between \frac{Q'}{p} m and e (before modulus switching) and keep this gap when going to Q, we would first need to use an Hermite interpolation (either a higher-order trigonometric Hermite interpolation as part of FBT or a polynomial Hermite interpolation afterwards) or, alternatively, CKKS bootstrapping from ePrint 2024/109 to reduce the noise (in this case an extra limb would be useful). In other words, the problem is not in the modulus switching but in the signal-to-noise ratio before this, which can, in its turn, be reduced via bootstrapping/Hermite interpolation techniques. Note that the gap could also be trivially increased by increasing Q' from a 47-bit number to a 59-bit one (but this may require a larger N) - I assumed above that we want to keep Q' the same.
Hi Yuriy, thank you very much for your reply! I now realize that this essentially concerns the signal-to-noise ratio.
I also understand that the FBT follows the PBS structure of TFHE/FHEW, where BFV ciphertext corresponds to TRLWE ciphertext in TFHE and CKKS ciphertext corresponds to TLWE ciphertext in TFHE (correct me if I misunderstand). That said, I still have a question: why is RLWE (BFV) selected as the relay for FBT?
From what I have observed, even in serial FBT or in FBT combined with levelled operations, the actual FBT operations and levelled multiplications seem to be performed directly on CKKS ciphertexts, whereas RLWE (BFV) mainly appears to function in modulus switching. Could you share some insights into the rationale behind this design?