When to perform CKKS bootstrapping

Library Questions
1

Hello everyone,

I’m currently developing an application that involves performing many multiplications, with bootstrapping steps in between. Ideally, I’d like to continue multiplying as long as ciphertext->GetLevel() < max_mult_depth without triggering bootstrapping. However, I keep encountering the following error:

/home/kholod/openfhe-development/src/core/include/lattice/hal/default/dcrtpoly-impl.h:l.695:DropLastElement(): DropLastElement: Removing last element of DCRTPoly renders it invalid.

After experimenting with the conditions for performing an additional multiplication, I found that one more multiplication is possible if ciphertext->GetLevel() < max_mult_depth - 2.

I’m curious why it’s necessary to leave 2 levels available for bootstrapping. I reviewed the original CKKS bootstrapping paper, particularly the following section:

image
image989×659 116 KB

Am I correct in understanding that the ciphertext needs 2 available levels to ensure the modulus q remains sufficiently large, thereby keeping the error small? Or is there another reason why 2 multiplicative levels must be reserved for bootstrapping?

Additionally, I’m unsure how to interpret these 2 levels in the context of bootstrapping. While bootstrapping requires ~20 levels to complete, I thought this impacted the number of levels available after bootstrapping, rather than the levels that must be preserved beforehand. Is it accurate to say that bootstrapping itself requires these 2 levels for its computations and is able to refresh ciphertext only for max_mult_depth - ~20 levels available?

I find this a bit confusing because, in my case, if GetLevel() is still below the maximum multiplicative depth, I expect that further multiplications should be possible without bootstrapping. However, this doesn’t seem to be the case. I would greatly appreciate it if someone could clarify why these 2 levels are needed.

Lastly, as a suggestion, would it be helpful to introduce a function like LevelAvailBeforeBootstrapping? This might prevent the unexpected errors that arise when assuming there are still sufficient levels for multiplication based solely on max_mult_depth - ciphertext->GetLevel().

Thank you very much for your time and assistance!

Arseniy

cc @sloede

OpenFHE 1.2.1
MWE:

#define _USE_MATH_DEFINES
#include <vector>
#include <cassert>
#include <iostream>
#include <cmath>
#include <fstream>
#include <tuple>
#include <string>
#include "openfhe.h"

void test_bootstrapping(){
    size_t levelsAvailableAfterBootstrap = 15;
    size_t data_length = 1<<5;
    // openfhe setup from https://github.com/openfheorg/openfhe-development/blob/main/src/pke/examples/advanced-ckks-bootstrapping.cpp
    lbcrypto::CCParams<lbcrypto::CryptoContextCKKSRNS> parameters;
    lbcrypto::SecretKeyDist secretKeyDist = lbcrypto::SPARSE_TERNARY;
    parameters.SetSecretKeyDist(secretKeyDist);
    // parameters.SetSecurityLevel(lbcrypto::HEStd_128_classic);
    parameters.SetSecurityLevel(lbcrypto::HEStd_NotSet);
    parameters.SetRingDim(1<<10);
    parameters.SetBatchSize(data_length);
#if NATIVEINT == 128 && !defined(__EMSCRIPTEN__)
    // Currently, only FIXEDMANUAL and FIXEDAUTO modes are supported for 128-bit CKKS bootstrapping.
    lbcrypto::ScalingTechnique rescaleTech = lbcrypto::FIXEDAUTO;
    usint dcrtBits               = 78;
    usint firstMod               = 89;
#else
    // All modes are supported for 64-bit CKKS bootstrapping.
    lbcrypto::ScalingTechnique rescaleTech = lbcrypto::FLEXIBLEAUTO;
    usint dcrtBits               = 59;
    usint firstMod               = 60;
#endif
    parameters.SetScalingModSize(dcrtBits);
    parameters.SetScalingTechnique(rescaleTech);
    parameters.SetFirstModSize(firstMod);
    std::vector<uint32_t> levelBudget = {4, 4};
    std::vector<uint32_t> bsgsDim = {0, 0};
    size_t depth = levelsAvailableAfterBootstrap+lbcrypto::FHECKKSRNS::GetBootstrapDepth(levelBudget, secretKeyDist);
    parameters.SetMultiplicativeDepth(depth);
    lbcrypto::CryptoContext<lbcrypto::DCRTPoly> cryptoContext = GenCryptoContext(parameters);
    cryptoContext->Enable(lbcrypto::PKE);
    cryptoContext->Enable(lbcrypto::KEYSWITCH);
    cryptoContext->Enable(lbcrypto::LEVELEDSHE);
    cryptoContext->Enable(lbcrypto::ADVANCEDSHE);
    cryptoContext->Enable(lbcrypto::FHE);
    cryptoContext->EvalBootstrapSetup(levelBudget, bsgsDim, data_length);
    lbcrypto::KeyPair<lbcrypto::DCRTPoly> keyPair = cryptoContext->KeyGen();

    cryptoContext->EvalMultKeyGen(keyPair.secretKey);
    cryptoContext->EvalBootstrapKeyGen(keyPair.secretKey, data_length);

    std::vector<double> data_vec(data_length, 0.42);
    auto ptxt = cryptoContext->MakeCKKSPackedPlaintext(data_vec);
    auto ciph = cryptoContext->Encrypt(keyPair.publicKey, ptxt);

    //while(ciph->GetLevel()<depth-0) //error
    //while(ciph->GetLevel()<depth-1) //error
    while(ciph->GetLevel()<depth-2) //ok
        ciph = cryptoContext->EvalMult(ciph, 1.0);

    ciph = cryptoContext->EvalBootstrap(ciph);

    cryptoContext->Decrypt(keyPair.secretKey, ciph, &ptxt);
}

int main(){
    test_bootstrapping();
    return 0;
}
2

Please ask one question at a time and be concise in asking your questions. It is hard to read the full article/essay. I will answer the first question.

One level is needed for 64-bit NATIVEINT (default) to do an extra scalar multiplication before bootstrapping.

Another “level” may be needed because you are using the FLEXIBALEAUTO(EXT) mode which does not do immediate rescaling; it rescales right before next multiplication (see Approximate Homomorphic Encryption with Reduced Approximation Error for the reasoning). In reality, the multiplication already took place but the size of the modulus was not reduced via rescaling (hence the ciphertext level has not been updated). In other words, the multiplicative level has already been used but the ciphertext was not simply rescaled.

3

Thank you very much for your patience in answering our many questions, we really appreciate it! These explanations are, again, extremely helpful to better understand the behavior of the CKKS scheme and its OpenFHE implementation.