# Implement reciprocal of a floating point number using Chebyshev approximation in CKKS

I am trying to obtain the reciprocal of a floating point value $$x$$ using the Chebyshev approximation, where $$x$$ is mostly in the order of $$10^3$$ to $$10^5$$. Subsequently, I am trying to implement that algorithm using CKKS for secure computation. My initial attempt with Taylor's series didn't help me that much due to accuracy issues; hence I am looking for alternate solutions. I am trying to obtain an algorithm based on Chebyshev approximation to achieve the same.

I found a plaintext implementation in this link: https://github.com/usnistgov/ChebTools. However, as per the unit testing, the reciprocal test case fails. Simunatnesouly, some computations are not possible to implement using CKKS. I also found an openFHE library here: https://github.com/openfheorg/openfhe-development/tree/main. I believe this library contains an implementation of division using Chebyshev interpolation. However, I could not find the algorithm from this library. It will be really helpful if a division algorithm using Chebyshev approximation can be found. Your help in this regard is very much appreciated.

Chebyshev approximation was initially used to homomorphically compute $$x\mapsto \sin(x)$$ (which itself was a stand-in for $$x\mapsto \lfloor x\rfloor$$), see for example this. In general division for CKKS is quite hard. I have seen people suggest that the most reasonable things to do are to use division algorithms for it. For example, this paper uses Goldschmidt's division algorithm to compute $$f(x) = 1/x$$.
That being said, further work dropped Goldschmidt's algorithm, and instead used techniques that appear to avoid computing $$x\mapsto 1/x$$. You can argue these further techniques do actually still compute this function (using Goldschmidt's algorithm), but this is something I haven't written up/published, so is perhaps difficult to communicate in a crypto.stackexchange answer box. The short answer is that (part of) the above work can be seen as
1. taking a Pade approximant to $$f(x) = \mathsf{sign}(x)$$, meaning an approximation of this function by a quotient of two polynomials $$\frac{p(x)}{q(x)}$$, and then
2. approximating $$q(x)\mapsto 1/q(x)$$ using Goldschmidt.
• Maybe this is more useful --- here (say line 161) is an example of how to evaluate $\sqrt{x}$ in OpenFHE using Chebyshev approximation. The adaptation to $x\mapsto 1/x$ should be immediate. Commented Mar 8 at 9:17