1
$\begingroup$

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.

$\endgroup$

1 Answer 1

1
$\begingroup$

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.
$\endgroup$
2
  • $\begingroup$ Thanks, Mark for your answer. I didn't understand the first point of your proposed solution. Can you please elaborate a little bit more about that or provide me with some materials that can help? $\endgroup$ Commented Mar 8 at 7:39
  • 1
    $\begingroup$ 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. $\endgroup$
    – Mark Schultz-Wu
    Commented Mar 8 at 9:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.