CKKS levels needed for bootstrap

Library Questions
1

In the examples provided on github, in the comments, it’s said that levels needed for bootstrap is 1, but after testing it, seems like it requires 2 levels.

int main() {
  // Setup CryptoContext
  SecretKeyDist secretKeyDist = UNIFORM_TERNARY;  // SPARSE_TERNARY or UNIFORM_TERNARY {-1, 0, +1}
  SecurityLevel securityLevel = HEStd_NotSet;     // If different from HEStd_NotSet, do not to set ring dimension
  uint32_t ringDimension = 1 << 12;               // Number of coefficients in the ring, minimum batchSize*2
 
  CCParams<CryptoContextCKKSRNS> parameters;
  parameters.SetSecretKeyDist(secretKeyDist);
  parameters.SetSecurityLevel(securityLevel);
  parameters.SetRingDim(ringDimension);
 
  // Don't change, only expert users should modify
#if NATIVEINT == 128
  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);
 
  /* Bootstrapping parameters.
   * We set a budget for the number of levels we can consume in bootstrapping for encoding and decoding, respectively.
   * Using larger numbers of levels reduces the complexity and number of rotation keys,
   * but increases the depth required for bootstrapping.
   * We must choose values smaller than ceil(log2(slots)). A level budget of {4, 4} is good for higher ring
   * dimensions (65536 and higher).
   */
  std::vector<uint32_t> levelBudget = {4, 4};
 
  // Note that the actual number of levels avalailable after bootstrapping before next bootstrapping
  // will be levelsAvailableAfterBootstrap - 1 because an additional level
  // is used for scaling the ciphertext before next bootstrapping (in 64-bit CKKS bootstrapping)
  uint32_t levelsAvailableAfterBootstrap = 10;
  usint depth = levelsAvailableAfterBootstrap + FHECKKSRNS::GetBootstrapDepth(levelBudget, secretKeyDist);
  parameters.SetMultiplicativeDepth(depth);
 
  CryptoContext<DCRTPoly> cryptoContext = GenCryptoContext(parameters);
 
  // Enable features
  cryptoContext->Enable(PKE);          // Enable public key encryption functionality
  cryptoContext->Enable(KEYSWITCH);    // Enable key switching (required for changing ciphertext keys or performing rotations)
  cryptoContext->Enable(LEVELEDSHE);   // Enable leveled SHE (Somewhat Homomorphic Encryption) operations
  cryptoContext->Enable(ADVANCEDSHE);  // Enable advanced SHE features like multiplication, rotations, and rescaling
  cryptoContext->Enable(FHE);          // Enable full FHE (bootstrapping) capabilities
 
  uint32_t ringDim = cryptoContext->GetRingDimension();
  // This is the maximum number of slots that can be used for full packing.
  uint32_t numSlots = ringDim / 2;
  std::cout << "CKKS scheme is using ring dimension " << ringDim << std::endl;
  std::cout << "Number of slots: " << numSlots << std::endl;
  std::cout << "CKKS scheme initialized with Bootstrapping support." << std::endl;
 
  // Measure Key Generation Time
  auto start = std::chrono::high_resolution_clock::now();
 
  KeyPair<DCRTPoly> keyPair = cryptoContext->KeyGen();
 
  auto end = std::chrono::high_resolution_clock::now();
  std::chrono::duration<double, std::milli> durationKeyGen = end - start;
  std::cout << "Key Generartion (Public/Private) took: " << durationKeyGen.count() << " ms" << std::endl;
 
  // Measure EvalMult Key Generation Time
  start = std::chrono::high_resolution_clock::now();
 
  cryptoContext->EvalMultKeyGen(keyPair.secretKey);
 
  end = std::chrono::high_resolution_clock::now();
  std::chrono::duration<double, std::milli> durationMultKeyGen = end - start;
  std::cout << "EvalMult Key Generation took: " << durationMultKeyGen.count() << " ms" << std::endl;
 
  // Measure EvalBootstrap Key Generation Time
  start = std::chrono::high_resolution_clock::now();
 
  cryptoContext->EvalBootstrapSetup(levelBudget);
  cryptoContext->EvalBootstrapKeyGen(keyPair.secretKey, numSlots);
 
  end = std::chrono::high_resolution_clock::now();
  std::chrono::duration<double, std::milli> durationBootstrapKeyGen = end - start;
  std::cout << "EvalBootstrap Key Generation took: " << durationBootstrapKeyGen.count() << " ms" << std::endl;
 
  std::vector<double> x;
  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++) {
    x.push_back(dis(gen));
  }
 
  Plaintext ptxt = cryptoContext->MakeCKKSPackedPlaintext(x, 1, 0, nullptr, numSlots);
  ptxt->SetLength(numSlots);
  std::cout << "Input: " << ptxt << std::endl;
 
  // Encrypt the encoded vectors
  Ciphertext<DCRTPoly> ciph = cryptoContext->Encrypt(keyPair.publicKey, ptxt);
 
  std::cout << "Initial number of levels remaining: " << depth - ciph->GetLevel() << std::endl;
 
  double scalar = 3.5;  // example scalar
 
  // Create a vector filled with the scalar
  std::vector<double> scalarVec(numSlots, scalar);
 
  Plaintext scalarPtxt = cryptoContext->MakeCKKSPackedPlaintext(scalarVec);
 
  Ciphertext<DCRTPoly> ciphScaled = cryptoContext->EvalMult(ciph, scalarPtxt);
 
  Ciphertext<DCRTPoly> ciphScaled2 = cryptoContext->EvalMult(ciphScaled, 3.5);
  cryptoContext->EvalMultInPlace(ciphScaled2, 3.5);
  cryptoContext->EvalMultInPlace(ciphScaled2, 3.5);
  cryptoContext->EvalMultInPlace(ciphScaled2, 3.5);
  for (size_t i = 0; i < 26; ++i) {
    cryptoContext->EvalMultInPlace(ciphScaled2, 3.5);
  }
 
  // Rescale explicitly
  // cryptoContext->EvalRescaleInPlace(ciphScaled2);
 
  std::cout << "Initial number of levels remaining after mult: " << depth - ciphScaled2->GetLevel() << std::endl;
 
  // Step 5: Perform the bootstrapping operation. The goal is to increase the number of levels remaining
  // for HE computation.
  auto ciphertextAfter = cryptoContext->EvalBootstrap(ciphScaled2);
 
  std::cout << "Number of levels remaining after bootstrapping: " << depth - ciphertextAfter->GetLevel() << std::endl
            << std::endl;
 
  for (size_t i = 0; i < 10; ++i) {
    cryptoContext->EvalMultInPlace(ciphertextAfter, 3.5);
  }
 
  std::cout << "Initial number of levels remaining after mult2: " << depth - ciphertextAfter->GetLevel() << std::endl;
 
  auto ciphertextAfter2 = cryptoContext->EvalBootstrap(ciphertextAfter);
 
  std::cout << "Number of levels remaining after bootstrapping2: " << depth - ciphertextAfter2->GetLevel() << std::endl
            << std::endl;
 
  return 0;
}

Initial number of levels remaining: 32
Initial number of levels remaining after mult: 2
Number of levels remaining after bootstrapping: 11

Initial number of levels remaining after mult2: 1
terminate called after throwing an instance of 'lbcrypto::OpenFHEException'
  what():  basic/openfhe-development/src/core/include/lattice/hal/default/dcrtpoly-impl.h:l.695:DropLastElement(): DropLastElement: Removing last element of DCRTPoly renders it invalid.
Aborted
make: *** [Makefile:73: fhe] Error 134

Seems like the EvalBootstrap can only be done with at least 2 levels. Can someone explain the conflicting docs?

2

If your question is about FLEXIBLEAUTO*, there after a multiplication we have a noise degree of 2 (the message is encoded as \Delta^2) because in FLEXIBLEAUTO*, the rescaling is done right before the next multiplication. This means that if you are currently at \Delta^2, two extra RNS limbs are needed (instead of 1).

This is already accounted for in examples like openfhe-development/src/pke/examples/simple-ckks-bootstrapping.cpp at v1.4.2 · openfheorg/openfhe-development · GitHub (note the ciphertextAfter->GetNoiseScaleDeg() here).

3

That’s an interesting topic, is there a docs about the FLEXIBLEAUTO?

By the way, I was referring to openfhe-development/src/pke/examples/simple-ckks-bootstrapping.cpp at v1.4.2 · openfheorg/openfhe-development · GitHub

It states that 1 level is needed for bootstrap but in my example it actually needs 2

4

FLEXIBLEAUTO is described in ePrint 2020/1118. There it is referred to as CKKS-DE.

In the example you cited, the number of levels is printed out correctly (note the use of GetNoiseScaleDeg()):

    std::cout << "Number of levels remaining after bootstrapping: "
              << depth - ciphertextAfter->GetLevel() - (ciphertextAfter->GetNoiseScaleDeg() - 1) << std::endl
              << std::endl;

In your code, you are not considering the noise degree:

  std::cout << "Initial number of levels remaining after mult: " << depth - ciphScaled2->GetLevel() << std::endl;

You need to compute the number of levels the same way as in the example, i.e., you need to include (ciphScaled2->GetNoiseScaleDeg() - 1). If the noise degree is 1, this has no effect. However, if the noise degree is 2 (which is the default behavior for FLEXIBLEAUTO), you will see the number of levels remaining as 0 (not 1).

As I had already pointed out, when you have a ciphertext with a noise degree of 2, i.e., scaled as \Delta^2, and you have two RNS limbs, no more mutliplicative levels are left. One multiplicative level is needed for the CKKS bootstrapping to go through in the scenario you are working with.

5

Thanks for the reply.

Two last questions that came through my mind.

  std::vector<uint32_t> levelBudget = {4, 4};
 
  uint32_t levelsAvailableAfterBootstrap = 10;
  usint depth = levelsAvailableAfterBootstrap + FHECKKSRNS::GetBootstrapDepth(levelBudget, secretKeyDist);
  parameters.SetMultiplicativeDepth(depth);

From my understanding levelBugdet is divided into encoding and decoding of the bootstrap?
If i check the depth available after the bootstrap it shows 10, shouldn’t it show levelsAvailableAfterBootstrap + levelBudget[0] + levelBudget[1] so 18 as it need 8 levels for the bootstrap encoding and decoding operations?

And in FHECKKSRNS::GetBootstrapDepth(levelBudget, secretKeyDist); why do we need secretKeyDist?

6

We typically start new topics for new questions. I will briefly answer the questions here:

CKKS bootstrapping includes four steps (the order may be different): ModRaise, Encode (CoeffsToSlots), Approx Mod, and Decode (SlotsToCoeffs). In other words, encoding and decoding are part of CKKS bootstrapping. GetBootstrapDepth computes the number of levels needed for the full CKKS bootstrapping.

The Approx Mod function (main bottleneck) depends on the secret key distribution. The number of levels for sparse ternary secrets is smaller than for uniform ternary secrets. This is why sparse secrets are often prefered in research papers, although uniform secrets are often recommended for more production-oriented settings.

I suggest reading Security Guidelines for Implementing Homomorphic Encryption for more details on CKKS bootstrapping and secret distributions.