I 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?
We followed the DM blueprint. In this case, LWE → RLWE (an additive homomorphic scheme) and RGSW->CKKS (for bootstrapping and multiplications, i.e., for nonlinear operations). So it is a logical vectorized extension of FHEW/TFHE.
RLWE is exact and the message is encoded in a BFV-like manner. In other words, this hybrid cryptosystem does not have the inherent IND-CPA^D issue of approximate CKKS and is not subject to key recovery attacks as long as the decrypted result is correct with negligible probability of failure. Hence, this cryptosystem is as exact as BGV, BFV, FHEW, or TFHE, although approximate CKKS is used internally for the bootstrapping operation.
There is an alternative (pure CKKS) instantiation of FBT, which is also discussed in the main paper. Note that this pure CKKS flavor does not enjoy the benefit of being an exact FHE scheme (in its typical configuration). We are planning to add the pure CKKS flavor in v1.5.
I still have a small question regarding the conversion. You mentioned that the hybrid cryptosystem can be as exact as BGV, BFV, FHEW, or TFHE, whereas the FBT result in CKKS remains approximate (even though Hermite interpolation helps reduce the error). May I ask at which stage this conversion from approximate to exact actually takes place? Is it during SchemeletRLWEMP::convert, perhaps through a technique like Homomorphic Rounding, or does it instead occur at the decryption stage?
The conversion in this case is very lightweight, and does not require any key material (not even key switching). It comes down to modulus switching and scaling to make sure we go from power-of-two parameters to NTT-friendly ones (to use Double-CRT in CKKS bootstrapping), and adjust the scaling factor so that CKKS could be used. A different way to interpret this is that we use CKKS everywhere except for encryption and decryption, where we use classical RLWE (BFV) procedures that make sure the noise is separate from the message during encryption and the noise is removed during decryption. These two steps are what makes this cryptosystem exact.
In CKKS bootstrapping, our goal is to make sure the noise never gets too close to the message (so it would not lead to incorrect rounding during decryption). Our main tool to control the noise is (trigonometric) Hermite interpolation - we have to apply it to make sure the messages stays separable from noise.
In classical CKKS, the message and noise are mixed during encryption, and there is no rounding step during decryption. This is why the classical CKKS scheme is approximate.