Hi!
I found the current composite rescaling is implemented by iteratively dropping the last moduli until the number of dropped moduli hit the level (i.e. the composite degree), as detailed in this link:
Would there be any accuracy effects if directly dropping all required number of moduli together instead of drop them one by one? Because dropping all of them at once would be faster and also seem giving lower noise as pointed by the paper (2023/1462.pdf)
Thank you so much!
Yes, it would be more efficient to scale down by several RNS limbs at once, similar to how it is done in openfhe-development/src/pke/lib/keyswitch/keyswitch-hybrid.cpp at aa391988d354d4360f390f223a90e0d1b98839d7 · openfheorg/openfhe-development · GitHub in hybrid key switching. In terms of noise growth, there is a choice between ApproxModDown (slightly cheaper) and the exact one (like the one use in the HPS pr BEHZ BFV multiplication). With the approximate ModDown, the noise would be larger than in the case of rescaling by one limb at a time. With the exact ModDown, it should be much closer to the one-by-one approach. However, the implementation would be more involved. This is why this optimization has not been implemented yet for composite rescaling.
Correct me if I’m wrong – Thank you so much!
| Method | Speed | Noise Growth | Complexity |
|---|---|---|---|
| Current (One-by-one) | Slower | Low | Low (Existing) |
| ApproxModDown (All-at-once) | Fastest | High (Worse accuracy) | Low |
| Exact ModDown (All-at-once) | Fast | Low (Good accuracy) | High (Hard to implement) |
In terms of speed, I agree. But I want to note that the increase in computational complexity of exact ModDown vs ApproxModDown should be relatively small. The noise difference between the two can be estimated from the expression in Appendix B.2.3 of ePrint 2021/204. The expression there is given for ApproxModDown. In the case of exact ModDown, k would always be equal to 1.
i would also say that exact ModDown is only slightly more difficult to implement than ApproxModDown (more precomputed parameters might be needed).
BTW, if you are interested in implementing both ApproxModDown and exact ModDown options in OpenFHE, I would be happy to review the results and your PR so this could be added to the next release of OpenFHE.