Hi guys,
I’m wondering if the key-switching Keys in OpenFHE are reusable, that is the ciphertext in different levels (BGV and CKKS) can use the same KeySwitch Key.
That feature is viable in SEAL, as far as I know, cause they use “one special prime policy”, that is the special case of dnum = l for the hybrid key-switch. So, when applying key-switching on level-i ciphertext, they just delete part of the key-switch keys (according to the modulus deleted during Modulus Switching).
But for hybrid key-switching, is this technique still applicable? Or we just have to store a key-switch key for multiplication in every level? Is there any reading material for discussion on doing key-switching in different multiplication levels?
In all OpenFHE examples based on hybrid key switching (default for CKKS and BGV), only one switching key (e.g., for multiplication or a specific rotation) is used for all levels; typically it corresponds to level 0. For a level-i ciphertext, the other RNS limbs (for levels < i) in the evaluation key are ignored during key switching. This is done automatically by OpenFHE.
Thank you so much for replying! Actually, what I really want to know is the mathematics behind Hybrid-Key-switching, and I’ve just found the answer in “Better Bootstrapping for Approximate Homomorphic Encryption”. It seems OpenFHE goes totally with the Key-Switch operation described in that paper, with little modification in the step “2-1. Zero-padding and Split”.
But one thing that still confuses me is the difference between SEAL and OpenFHE. Because we can treat Ke-Switching in SEAL as a special case of Hybrid Key-Switching in OpenFHE with dnum = L.
Key-Switching in SEAL is basically
Sum{DigitDecompose(c2), KeySwitchKey[(Q_hat)(Q_hat_inverse)Ps2]}
While Key-Switching in OpenFHE goes like
Sum{(Q_hat_inverse)DigitDecompose(c2), KeySwitchKey[(Q_hat)Ps2]}
That would introduce a multiplication of (Q_hat_inverse) on c2 every time a KeySwitch is executed. I wonder if it is possible for OpenFHE to move that (Q_hat_inverse) into Key-Switch Keys to save some computation? Or that sort of technique is simply impossible (not right)?
Thanks @Sijia Good catch! It looks we missed this optimization in hybrid key switching (back when we implemented it in PALISADE). The BV key switching does include the optimization (I just looked at the code).
I looked deeper into this issue and decided to write it down in more detail. In the case of hybrid key switching, our Q_i is decomposed into multiple digits \tilde{Q_j}, where j = 0 \dots d_{num}-1. Each of this digits may have multiple machine-word RNS moduli q_k, where k = 0 \dots i (a subset of this for each digit).
If \tilde{Q_j} has only one machine-word modulus, then we can apply the HPS optimization directly. We can move \left[ \left( \frac{Q_i}{\tilde{Q_j}} \right)^{-1} \right]_{\tilde{Q_j}} \frac{Q_i}{\tilde{Q_j}} to s from the ciphertext digits, i.e., do this product as part of key generation (saving scalar multiplications). Moreover, as we need s_{q_k}, this scalar factor for a given q_k becomes congruent to 1 \bmod q_k. So we do not even need to do the scalar multiplication as part of key generation.
When \tilde{Q_j} contains multiple machine-word RNS moduli, which is what desired in practice (the SEAL mode requires larger keys for larger i, starting with i = 4 or so, and, hence, is rarely used in practice), we can still move the product \left[ \left(\frac{Q_i}{\tilde{Q_j}}\right) ^{-1} \right]_{\tilde{Q_j}} \frac{Q_i}{\tilde{Q_j}} to s, i.e., do it as part of key generation. This scalar product is still congruent to 1 \bmod q_k as the RNS decomposition of 1 \bmod \tilde{Q_j} implies congruency to 1 for all q_k within the digit \tilde{Q_j}.
Just wanted to write it down to simplify the implementation of the optimization in OpenFHE.
