Hello! I am trying to evaluate the square root of two using CKKS.
I wrote a function to calculate Taylor’s coefficients, and then I evaluate the polynomial using EvalPoly. The program work when I use degree = 8, but when I try degree = 16, the output is totally incorrect.
@narger I highly suspect this is a plaintext overlfow issue. This means that at some point during computation the norm of at least one of the plaintext coefficients (not slots) became larger than half the current modulus, corrupting the plaintext. Using the standard power basis is not numerically stable with the CKKS scheme. If you keep increasing the degree of the polynomial, a value greater than 1 will eventually blow up, and inversely, a value smaller than 1 will eventually vanish. This is what happened to this work BLEACH: Cleaning Errors in Discrete Computations over CKKS, which didn’t use the Chebyshev basis (see Appendix A).
Using the Chebyshev basis solves this numerical instability issue because it has a natural change of basis x’ = (2x-a-b)/(b-a) for a given interval [a, b], which ensures that -1<=x’<=1, but also that with higher power the value doesn’t vanish. This not only avoids plaintext overflow issues, but it also drastically reduces the variances of the power basis, which reduces the added error (CKKS works a little bit like floating point numbers, it has a fixed precision, and a small value added to a large value gets flooded by noise).
For example, if you take TableA1 of the work I referenced and compute the standard deviation of the coefficients, you get 59718 = 2^{15.86} which means that they will lose, just because of the distribution of the coefficients of the polynomial, close to 16 bits of precision. On top of this, you can add the numerical instability of computing x^{i} for large i.
If instead you use the Chebyshev basis for the same polynomial, you get a standard deviation of about 0.25.
