# Chebyshev vs Optimal Minimax Polynomial Approximation

**URL:** <https://openfhe.discourse.group/t/chebyshev-vs-optimal-minimax-polynomial-approximation/1578>\
**Category:** FHE Questions\
**Created:** [September 16, 2024, 7:36pm UTC](https://openfhe.discourse.group/t/chebyshev-vs-optimal-minimax-polynomial-approximation/1578 "2024-09-16T19:36:41Z")\
**Posts on this page:** 3\
**Page:** 1

<div class="post-metadata">

**Author:** ![seyda](https://yyz1.discourse-cdn.com/flex031/user_avatar/openfhe.discourse.group/seyda/32/397_2.png) [@seyda](https://openfhe.discourse.group/u/seyda)\
**Post date:** [September 16, 2024, 7:36pm UTC](https://openfhe.discourse.group/t/chebyshev-vs-optimal-minimax-polynomial-approximation/1578/1 "2024-09-16T19:36:41Z")

</div>

Hello everyone, as far as I know, the CKKS bootstrapping in the literature diverges around 2021 between two methods:

- [Bossuat et al.](https://eprint.iacr.org/2022/024) 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](https://eprint.iacr.org/2019/688.pdf).
- [Lee et al.](https://link.springer.com/chapter/10.1007/978-3-030-77870-5_22) 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!

---

<div class="post-metadata">

**Author:** ![Pro7ech](https://yyz1.discourse-cdn.com/flex031/user_avatar/openfhe.discourse.group/pro7ech/32/301_2.png) [@Pro7ech](https://openfhe.discourse.group/u/Pro7ech)\
**Post date:** [September 17, 2024, 2:31pm UTC](https://openfhe.discourse.group/t/chebyshev-vs-optimal-minimax-polynomial-approximation/1578/2 "2024-09-17T14:31:35Z")

</div>

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:

 ![{E9194227-B40C-473A-8F84-2E355B597416}](https://canada1.discourse-cdn.com/flex031/uploads/openfhe/original/1X/14b55d7cf629e4d7cd0415ddc74600add4368a21.png)

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.

---

<div class="post-metadata">

**Author:** ![seyda](https://yyz1.discourse-cdn.com/flex031/user_avatar/openfhe.discourse.group/seyda/32/397_2.png) [@seyda](https://openfhe.discourse.group/u/seyda)\
**Post date:** [September 17, 2024, 3:04pm UTC](https://openfhe.discourse.group/t/chebyshev-vs-optimal-minimax-polynomial-approximation/1578/3 "2024-09-17T15:04:49Z")

</div>

Thank you so much 😇 Is there any chance that the slide you shared is from an open source discussion / seminar?