Modulus overflow and Chebyshev approximation

FHE Questions
1

Hello,
I am currently trying to perform a Chebyshev approximation to evaluate 1/sqrt(x). I had the same problem as in this other forum question: Weird behavior on Chebyshev - #4 by ypolyakov
While choosing a larger multiplicative depth solves the issue, I am not sure I thoroughly get the notion of modulus overflow that is mentioned. From rereading the original CKKS paper, I understand how a modulus overflow would happen and why it corrupts the ciphertext. However, I didn’t manage to properly formalize this by myself and didn’t find a direct answer in literature. Moreover, I don’t understand why this happens specifically when performing a Chebyshev approximation. Would anyone have references on this subject (modulus overflow and why it happens with Chebyshev approximation) ?

Thanks in advance for your help.

2

At a high level, the desired arithmetic in CKKS is over integers (which are scaled-up real numbers), i.e., over \mathbb{Z}. But this arithmetic is embedded in \mathbb{Z}_Q, i.e., it is bounded by ciphertext modulus Q. Whenever you perform any computations, you need to make sure none of the intermediate or final values exceed \mathbb{Z}_Q. Otherwise, you will get a modulus overflow, and the encrypted values wrap around Q.

Note that in practice Q changes (from largest at the beginning to smallest at the end - for simplicity I am referring to the leveled case), but the statement above is still valid.

3

Hello,

Thank you for your answer. The notion of modulus overflow is clearer now.

However, I still do not understand why modulus overflow happens during my Chebyshev interpolation. Indeed, to perform this operation I chose the multiplicative depth according to the table here : openfhe-development/src/pke/examples/FUNCTION_EVALUATION.md at main · openfheorg/openfhe-development · GitHub . I set my bounds to values such as [0.5; 3] (not too close to zero and over a small range) and varied the degree between 5 and 27. But I get only negative values and they are all very close together (similar to Weird behavior on Chebyshev). I solved that by increasing by one the multiplicative depth recommended in the table.

Still, many questions arise. Is there something wrong in my understanding of the table ? Why would a modulus overflow happen specifically when I perform a Chebyshev interpolation (function: 1/sqrt(x)) ? (By the way, if you have any clue about how the numbers in the table were obtained, do not hesitate to share.)

Thanks a lot for your help.

4

The numbers in the table are obtained based on the Paterson-Stockmeyer polynomial interpolation method, which is what is used in EvalChebyshevFunction.

Are the scaling factor and the first modulus chosen appropriately? Are you sure there are no zeros in your input? Please provide a minimum working example to showcase your issue. I did not see any issues when approximating 1/sqrt(x).

5

Thank your for your answer.

My input is a vector of size 16 containing values evenly distributed in the interval on which I want to approximate 1/sqrt(x). I tested my code with many different lower bounds, upper bounds and polynomial degrees. My function “GetMultDepth” in the code below takes as input the polynomial degree and outputs the corresponding multiplicative depth, according to the table given in FUNCTION_EVALUATION.md. I put two output examples below the code.

Here is a code example:

    CCParams<CryptoContextCKKSRNS> parameters;
    parameters.SetSecurityLevel(HEStd_128_classic);

#if NATIVEINT == 128 && !defined(__EMSCRIPTEN__)
    ScalingTechnique rescaleTech = FIXEDAUTO;
    usint dcrtBits = 78;
    usint firstMod = 89;
#else
    ScalingTechnique rescaleTech = FLEXIBLEAUTO;
    usint dcrtBits = 59;
    usint firstMod = 60;
#endif

    parameters.SetScalingModSize(dcrtBits);
    parameters.SetScalingTechnique(rescaleTech);
    parameters.SetFirstModSize(firstMod);

    uint32_t polyDegree = 27;

    uint32_t multDepth = GetMultDepth(polyDegree); 
    parameters.SetMultiplicativeDepth(multDepth);
    CryptoContext<DCRTPoly> cc = GenCryptoContext(parameters);
    cc->Enable(PKE);
    cc->Enable(KEYSWITCH);
    cc->Enable(LEVELEDSHE);
    cc->Enable(ADVANCEDSHE);

    auto keyPair = cc->KeyGen();
    cc->EvalMultKeyGen(keyPair.secretKey);

    double lowerBound = 0.5;
    double upperBound = 2;

    std::vector<std::complex<double>> input = {0.5, 0.59375, 0.6875, 0.78125, 0.875, 0.96875, 1.0625, 1.15625, 1.25, 1.34375, 1.4375, 1.53125, 1.625, 1.71875, 1.8125, 1.90625};

    size_t encodedLength = input.size();
    Plaintext plaintext  = cc->MakeCKKSPackedPlaintext(input);
    auto ciphertext      = cc->Encrypt(keyPair.publicKey, plaintext);

    auto result = cc->EvalChebyshevFunction([](double x) -> double { return 1/std::sqrt(x); }, ciphertext, lowerBound, upperBound, polyDegree);

    Plaintext plaintextDec;
    cc->Decrypt(keyPair.secretKey, result, &plaintextDec);
    plaintextDec->SetLength(encodedLength); 
    
    std::vector<std::complex<double>> finalResult = plaintextDec->GetCKKSPackedValue();
    std::cout << "Actual output\n\t" << finalResult << std::endl << std::endl;

Here are two output examples.
Firstly on the interval [1,2] with polynomial degree 13 and multiplicative depth 5:

[ (-3,0) (-3.02987,0) (-3.05718,0) (-3.08236,0) (-3.10558,0) (-3.12712,0) (-3.14721,0) (-3.16595,0) (-3.18354,0) (-3.19999,0) (-3.21555,0) (-3.23021,0) (-3.24407,0) (-3.25721,0) (-3.26972,0) (-3.28159,0) ]

Secondly on the interval [0.7, 2] with polynomial degree 27 and multiplicative depth 6:

[ (3.32128,0) (4.30869,0) (7.45238,0) (6.84932,0) (5.26606,0) (4.5096,0) (6.86303,0) (3.74379,0) (5.10435,0) (6.02175,0) (5.73903,0) (5.68307,0) (6.63103,0) (4.47987,0) (7.11322,0) (8.08926,0) ]

Thanks a lot for your help.

6

Two things. First, CKKS is an approximate scheme, so you cannot represent an exact number. Even encoding and encryption introduce a small error. Therefore, you want to select your interval for approximation more conservatively to ensure no overflow. For example, your lower bound is 0.5, which is exactly your lowest input. Pick something like 0.45 instead for the lower bound.

Second, the reason you get incorrect decryption results is that you do not leave sufficient bits for decryption. When the decryption happens on the last level, like in your case, the maximum magnitude of the messages for which you have guaranteed decryption correctness is firstModSize - scalingModSize bits. In your case, that is 1 bit. That’s why you see correctness when you increase the multiplicative depth: by doing so, you add another level and increase the maximum magnitude of the messages that can be decrypted correctly.

You should choose the scaling mod size based on the desired precision (larger precision larger scaling factor) but also based on your expected magnitude of the output messages (larger magnitude, smaller scaling factor or an extra level). For your example 55 bits instead of 59 seems to work well.

7

Thank you for this detailed answer. I managed to solve my issue based on your explanation.