FLEXIBLEAUTO ScalingTechnique, GetNoiseScaleDeg and decryption in CKKS

Library Questions
1

I’m trying to understand the rescaling in CKKS. I am working under the assumption that OpenFHE’s implementation of CKKS is based on the paper [KPP21], that is, when we set the scaling technique as FLEXIBLEAUTO, OpenFHE uses a different scaling factors \Delta_{i} for each for each level i, as described in the table in page 17 of [KPP21]. Thus, my first question is if this assumption is correct.

Then, still following [KPP21], I would expect the ciphertexts to be rescaled before each multiplication. However, it seems that before the first multiplication, ciphertexts are not rescaled. Could one explain why?

Third: If we rescale before multiplying, then, after we multiply, the scaling factor is \Delta_i^2 instead of \Delta_i, right? So, does GetNoiseScaleDeg() return this exponent (either 1 or 2)?

And fourth and final question, if we can indeed have scaling factor \Delta_i^2, then, when we reach the last level, we have \Delta_0^2. But the ciphertext is defined modulo q_0 only (i.e., all the other primes were dropped). How would it possible if \Delta_0^2 > q_0? Can we even decrypt then?

(Sorry for so many questions in one single question, but they all seem related. Please, if you can just answer some of them, that is fine, go ahead!)

1 Like
2

Thus, my first question is if this assumption is correct.

Yes

Then, still following [KPP21], I would expect the ciphertexts to be rescaled before each multiplication. However, it seems that before the first multiplication, ciphertexts are not rescaled. Could one explain why?

Please read “Our work” section (pages 2 and 3). We explain there why we suggest doing the rescaling right before the next multiplication.

So, does GetNoiseScaleDeg() return this exponent (either 1 or 2)?

Yes, it becomes 2.

Can we even decrypt then?

\Delta_0^2 means the final rescaling has not been done yet (2 RNS limbs are left rather than 1). This is equivalent to regular CKKS when rescaling is done to \Delta (which consumes 1 RNS limb/level and, hence, there is only 1 RNS limb left).

3

Hello! Thanks for the answer!

I had actually read that Section already (and even the more technical one in the body of the paper). I understand the motivation of rescaling before multiplying. But I am wondering what it means for the first multiplication. If we multiply two fresh ciphertexts, both with scaling factor \Delta_L = q_L, we don’t rescale them before multiplying? Otherwise, we would obtain ciphertexts with scaling factor \Delta_L / q_L = 1, then multiply them, which seems weird. Btw, this observation is consistent with my experiments with OpenFHE (i.e., when I print the number of primes before and after the first multiplication, they are the same, indicating that no rescale was performed).

And about the decryption, does this mean that a user of OpenFHE has to be aware of this and stop multiplying when there are two primes left? Indeed, I coded a simple example where I run many multiplications and try to decrypt. When there are two primes left, the decryption works fine. But then, I multiply again, and the decryption fails.

4

Just for the record, this is the program that tries to decrypt with two and with one prime left.

#include "openfhe.h"

using namespace lbcrypto;

int get_number_primes(const Ciphertext<DCRTPoly>& ctxt1){
    const DCRTPoly& poly = ctxt1->GetElements()[0];
    return poly.GetNumOfElements();
}

int main(int argc, char* argv[]) {
    int numSlots = 8;
    // Step 1: Set CryptoContext
    CCParams<CryptoContextCKKSRNS> parameters;

    SecretKeyDist secretKeyDist = UNIFORM_TERNARY;
    parameters.SetSecretKeyDist(secretKeyDist);

    parameters.SetSecurityLevel(HEStd_NotSet);
    parameters.SetRingDim(1 << 12);

    parameters.SetNumLargeDigits(3);
    parameters.SetKeySwitchTechnique(HYBRID);

    ScalingTechnique rescaleTech = FLEXIBLEAUTO;
    usint dcrtBits               = 59;
    usint firstMod               = 60;

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

	parameters.SetBatchSize(numSlots); // fix the number of slots for all plaintexts
	std::cout << "Parameters " << parameters << std::endl << std::endl;

    int depth = 5;
    parameters.SetMultiplicativeDepth(depth);

    // Generate crypto context.
    CryptoContext<DCRTPoly> cryptoContext = GenCryptoContext(parameters);

    // Enable features that you wish to use. Note, we must enable FHE to use bootstrapping.
    cryptoContext->Enable(PKE); 
    cryptoContext->Enable(KEYSWITCH);
    cryptoContext->Enable(LEVELEDSHE);
    cryptoContext->Enable(ADVANCEDSHE);

    usint ringDim = cryptoContext->GetRingDimension();
    std::cout << "CKKS scheme is using ring dimension " << ringDim << std::endl << std::endl;

    auto keyPair = cryptoContext->KeyGen();
    cryptoContext->EvalMultKeyGen(keyPair.secretKey);
   
    // Step 4: Encoding and encryption of inputs
    // Generate random input
    std::vector<double> x1;
    std::random_device rd;
    std::mt19937 gen(rd());
    std::uniform_real_distribution<> dis(0.0, 1.0);
    for (size_t i = 0; i < numSlots; i++)
        x1.push_back(dis(gen));
    
    Plaintext ptxt1 = cryptoContext->MakeCKKSPackedPlaintext(x1);
    ptxt1->SetLength(numSlots);
    std::cout << "Input 1: " << ptxt1 << std::endl;

    // Encrypt the encoded vector
    Ciphertext<DCRTPoly> ctxt1 = cryptoContext->Encrypt(keyPair.publicKey, ptxt1);

    std::cout << "Initial level ctxt1: " << ctxt1->GetLevel() << std::endl;
    std::cout << "depth: " << depth << std::endl;

    std::cout << "Number of primes in the moduli chain of ctxt1: " << get_number_primes(ctxt1) << std::endl;

	Ciphertext<DCRTPoly> cMul = cryptoContext->EvalMult(ctxt1, ctxt1);
    std::cout << "Number of primes in the moduli chain of cMul: " << get_number_primes(ctxt1) << std::endl << std::endl;
	
    while (get_number_primes(cMul) > 2)
        cMul = cryptoContext->EvalMult(cMul, ctxt1);
    
    std::cout << "Decrypting cMul while it has " << get_number_primes(cMul) << " primes in the moduli chain" << std::endl;
    Plaintext result;
    cryptoContext->Decrypt(keyPair.secretKey, cMul, &result);
    result->SetLength(numSlots);
    std::cout << "Decrypted result: " << result << std::endl << std::endl;

    cMul = cryptoContext->EvalMult(cMul, ctxt1); // this should drop one of the two remaining primes
    if (1 == get_number_primes(cMul)){
        std::cout << "Decrypting cMul while it has only 1 prime in the moduli chain" << std::endl;
        cryptoContext->Decrypt(keyPair.secretKey, cMul, &result);
        result->SetLength(numSlots);
        std::cout << "Decrypted result: " << result << std::endl;
    }
    return 0;
}

And this the ouput I get

Parameters scheme: CKKSRNS; ptModulus: 0; digitSize: 0; standardDeviation: 3.19; secretKeyDist: UNIFORM_TERNARY; maxRelinSkDeg: 2; ksTech: HYBRID; scalTech: FLEXIBLEAUTO; batchSize: 8; firstModSize: 60; numLargeDigits: 3; multiplicativeDepth:1; scalingModSize: 59; securityLevel: HEStd_NotSet; ringDim: 4096; evalAddCount: 0; keySwitchCount: 0; encryptionTechnique: STANDARD; multiplicationTechnique: HPS; PRENumHops: 0; PREMode: INDCPA; multipartyMode: FIXED_NOISE_MULTIPARTY; executionMode: EXEC_EVALUATION; decryptionNoiseMode: FIXED_NOISE_DECRYPT; noiseEstimate: 0; desiredPrecision: 25; statisticalSecurity: 30; numAdversarialQueries: 1; thresholdNumOfParties: 1; interactiveBootCompressionLevel: SLACK

CKKS scheme is using ring dimension 4096

Input 1: (0.937898, 0.798491, 0.889802, 0.0889563, 0.0410105, 0.435597, 0.0616124, 0.207677, … ); Estimated precision: 59 bits

Initial level ctxt1: 0
depth: 5
Number of primes in the moduli chain of ctxt1: 6
Number of primes in the moduli chain of cMul: 6

Decrypting cMul while it has 2 primes in the moduli chain
Decrypted result: (0.680667, 0.259191, 0.496319, 4.95521e-07, 4.75742e-09, 0.0068314, 5.47028e-08, 8.02298e-05, … ); Estimated precision: 49 bits

Decrypting cMul while it has only 1 prime in the moduli chain
terminate called after throwing an instance of ‘lbcrypto::OpenFHEException’
what(): /home/hilder/Documents/gitRepos/openfhe-src/src/pke/lib/encoding/ckkspackedencoding.cpp:l.537:Decode(): The decryption failed because the approximation error is too high. Check the parameters.
Aborted (core dumped)

5

In FLEXIBLEAUTOEXT, an auxiliary modulus (20-bit or so) is added when generating fresh ciphertexts. The high-level idea it reduce the fresh encryption noise to modulus switching/rescaling noise. Rescaling happens before first multiplication in this case. This is explained in the paper. The mode is referred to as RE-CKKS-DE.

In FLEXIBLEAUTO, no rescaling is done before first multiplication. This mode is referred to as CKKS-DE.

For both of these modes, rescaling is done before the following multiplications.

As far as decryption is concerned, the user specifies the multiplicative depth at crypto context generation. If the user exceeds this multiplicative depth when performing multiplications, then the decryption will not succeed (by design). For example, your code sets the multiplicative depth to 5 but tries to evaluate a circuit with 6 multiplicative levels; hence, the decryption will fail (by design), regardless which scaling mode for CKKS is used.