Hello everyone, as far as I know, the CKKS bootstrapping in the literature diverges around 2021 between two methods:
Bossuat et al. implements bootstrapping with depth-optimal Chebyshev interpolant evaluation via BSGS and double-hoisted rotations in linear transforms. The finalized bootstrapping algorithm is a mix of this paper and Han & Ki.
Lee et al. implements bootstrapping by obtaining the optimal minimax approximate polynomial of the modular reduction function based on multi-interval Remez algorithm.
In OpenFHE, I only see the former method implemented and was wondering the reason for the preference (or if I’m missing the second implementation in the documentation).
Thank you so much!
Actually, there are many more methods to compute the homomorphic modular reduction. This slide is one year old, so its slightly outdated, but it gives a good overview of what methods are used for papers related to the CKKS bootstrapping:
I’ve reproduced many of them and had the opportunity to discuss with the authors of some of these papers (an others not listed/published) while doing so, and we ended up with the same conclusion: despite all the effort and recent works, HK19 remains the best for overall performance and is really difficult to beat.
The reason is that it turns out that although in theory some of these approaches should perform better, in practice it is not the case because the polynomial representation of the modular function is not HE friendly (compact and with coefficients with small variance). This is really important to minimize the noise added by the homomorphic polynomial evaluation.
Is there any chance that the slide you shared is from an open source discussion / seminar?