Weird behavior on Chebyshev

Library Questions
1

Hello, I am using chebyshev approximation to evaluate exp(x). The problem is that, even though values are in the interval, results are messy.

I am using 2^16 ring with security 128 bits, this is the key part of the code:

vector<double> v = {-5, -4, -3, -2, -1, 0, 0.1, 0.2, 0.3, 1, 2, 3, 4, 5, 6, 7, 8};
Plaintext p = cryptoContext->MakeCKKSPackedPlaintext(v, 1, 0, nullptr, numSlots);
Ciphertext<DCRTPoly> c = crypto_context->Encrypt(key_pair.publicKey, p);
c = crypto_context->EvalChebyshevFunction([](double x) -> double { return exp(x); }, c, -10, 10, 27);

When i print the decrypted results, i get something like this:

(-2.88821e+07, -2.86466e+07, -2.81768e+07, -2.72802e+07, -2.57516e+07, -2.33729e+07, -2.30795e+07, -2.2775e+07, -2.24593e+07, ...

Am I doing something wrong?

2

For the given range of values (-10,10) using only 27 degrees is insufficient. Try bumping it up by a lot and gradually reduce the degree to trade off between the accuracy and multiplication depth you want.

openfhe-development/src/pke/examples/FUNCTION_EVALUATION.md at main · openfheorg/openfhe-development · GitHub might be useful for you to determine the depth to set your program to

I’m marking this as closed, but feel free to open it up again if your problem isn’t solved.

3

Same happens with degree 200 and 288.

Output with 288:

(-2783.7, -2783.69, -2783.66, -2783.58, -2783.34, -2782.71, -2782.61, -2782.49, -2782.36, -2780.99, -2776.32, -2763.63, -2729.11, -2635.3, -2380.28, -1687.08, 197.247, -2782.71, -2782.71, -2782.71, -2782.71, ...

I don’t think is related to the degree, the function is pretty easy to approximate (with gsl_chebyshev a degree=27 returns an average error of 10^-6)

4

@marc-alonso Could you post your complete example here, including the cryptocontext parameters? exp grows fast with an argument (i.e., exponentially). It is important to know what multiplicative depth you are using. You may need room (extra levels) not to cause an overflow over your ciphertext/plaintext modulus when computing e^{10}, which is about 22,000.

Overall, it is not the best scenario for Chebyshev interpolation as you have both very small and very large values in this range, i.e., you would probably need a relatively large CKKS scaling factor for this case to achieve desired precision. Depending on your application, I would probably consider working in the logarithmic scale, i.e., switching the problem from exponential to linear.

5

This is most likely a plaintext overflow. The CKKS plaintext isn’t an element of the ciphertext ring \mathbb{Z}[X]_{Q_{\ell}}/(X^{N}+1) (Q_{\ell} = \prod_{i=0}^{\ell} q_{i}), it is an element of \mathbb{R}[X]/(X^{N}+1), so to remain well define its infinity norm must remain small than Q_{\ell}/2 during all steps of the computation.

Check that the ratio between the remaining modulus Q_{\ell} after the evaluation and the plaintext scaling factor is greater than ~2\exp(x). If not, then you’ll have a modular reduction by Q_{\ell} on the plaintext during the evaluation and this will corrupt the plaintext.

Getting a resulting plaintext with large values that all look aline such as

(-2783.7, -2783.69, -2783.66, -2783.58, -2783.34, -2782.71, -2782.61, -2782.49, -2782.36, -2780.99, -2776.32, -2763.63, -2729.11, -2635.3, -2380.28, -1687.08, 197.247, -2782.71, -2782.71, -2782.71, -2782.71, ...

is typical of a plaintext overflow.

1 Like
6

I suggest you to take advantage of the fact that e^x = (e^{x/10})^{10} and approximate e^{x/10} in [-1, 1] (it might take more levels but it is more stable for sure).

2 Likes
7

@marc-alonso

Has the issue been resolved?

8

Yes, I used this approach:

Thank you