As is well-known, the multiplicative depth and the number of non-scalar multiplications are two metrics used to evaluate the complexity of operations in HE. For example, the complexity of bootstrapping can be evaluated in this manner. BGV bootstrapping has (e-1)log p depth and (e^2)\2 sqrt(2p) multiplications (not considering optimizations).
Can we represent the complexity of scheme switching in a similar way? I know there are some papers that report the complexity of scheme switching, such as CKKS to/from TFHE and BGV to/from TFHE, but they mostly report the complexity with respect to the ciphertext modulus and ring dimension. Thanks in advance.
You can think about scheme switching as being related to bootstrapping, therefore the complexity is similar. Take a look at https://eprint.iacr.org/2022/915.pdf page 14 to see the operations required for scheme switching between various pairs of FHE schemes.
Thanks for you reply. I have read the paper you sent me, https://dl.acm.org/doi/10.1145/3560827.3563379. I understand that linear transformation, key/modulus switching are needed to switch BGV/CKKS to TFHE. And to switch back, a linear transformation is needed to perform the encoding.
(1) I notice that in this paper, they mention that an additional bootstrapping is needed after switching TFHE to BGV/CKKS. I am wondering does that mean the ciphertext after switching has a high noise level? How does switching impact the noise level?
(2) Without considering this additional bootstrapping, it seems that scheme switching does not need digit extraction, which is typically considered as the main bottleneck for bootstrapping. From this perspective, it does not seem scheme switching would have a similar complexity to bootstrapping, although they both need linear transformation, modulus switching.
I am not very familiar with scheme switching, so please correct me if I am wrong.
I know that there are mainly two papers on scheme switching, CHIMERA: Combining Ring-LWE-based Fully Homomorphic Encryption Schemes and IEEE Xplore Full-Text PDF:. But the complexity analysis is mainly about the dimension of RLWE (resp. LWE) and ciphertext modulus (table 1 in PEGASUS). There are also some paper claiming that PEGASUS mostly work on small domain intervals, e.g., [-8,8]. This is true for their current implementation. And that PEGASUS would have a Ω(R) complexity with respect to the domain size R, table3 in Efficient Homomorphic Evaluation on Large Intervals. Can I say that scheme switching has a linear complexity with respect to the input domain?
In BGV bootstrapping, the depth/computaion complexity with respect to the input domain (plaintext space) is clear. So I want to assess scheme switching in a similar way. But it remains unclear to me how scheme switching impact the noise level and computation complexity when input domain varies.
There is no universal complexity of scheme switching because it is different between pairs of schemes. The pairs of schemes requiring complexity similar to bootstrapping are TFHE to BGV/BFV/CKKS (from single value with small ciphertext modulus to packed values with large ciphertext modulus) and CKKS to/from BGV/BFV (you can check this paper for the latter). For the other options, either a multiplication by a scalar is required (BGV/BFV) or changing encoding from slots to coefficients and a key switching (from CKKS/BFV/BGV to TFHE).
While the bottleneck for BGV/BFV bootstrapping is the digit extraction and depends on the plaintext modulus, the bottleneck of CKKS bootstrapping is the encrypted approximation of the modular reduction, whose complexity depends on the secret key sparsity, on the desired output precision and the degree of the polynomial approximation, the ciphertext modulus etc. I suggest you read some papers on CKKS bootstrapping, for instance, some of these https://eprint.iacr.org/2018/153.pdf, https://eprint.iacr.org/2018/1043.pdf, https://eprint.iacr.org/2020/1203.pdf, https://eprint.iacr.org/2022/1167.pdf.
Finally, some reasons for the claims around the limitations of PEGASUS are directly related to the limitations of TFHE: a larger plaintext modulus leads to a very large ciphertext modulus, which makes operations in TFHE very slow.
This might be a bit off-topic, but as of now, is the only Scheme Switching supported by OpenFHE between CKKS and TFHE/FHEW? Is CKKS to BGV/BFV scheme switching still not implemented?
Correct. Switching CKKS to BGV/BFV requires a BGV/BFV bootstrapping as mentioned in the references above, which is currently not implemented in OpenFHE.