# Questions on CKKS bootstrapping with some computations after bootstrapping

Do you have sample code with a large multiplication depth combined with ckk_bootstrapping? In the examples I’ve seen, only MakeCKKSPackedPlaintext+EvalBootstrap functions are used. When I tried to use 12 layers of multiplication depth with EvalBootstrap, I got significant errors. When using boostrapping, how should I set the “level” parameter in MakeCKKSPackedPlaintext? For example, if the total depth is 28 and “levelsUsedBeforeBootstrap” is set to 8, and MakeCKKSPackedPlaintext starts from level 0, when should I perform EvalBootstrap? Will EvalBootstrap directly jump to layer 21?

For example, how to use CKK bootstrapping to implement a function and ensure accurate results?

large multiplication depth combined with ckk_bootstrapping

I suppose it depends on how you define “large”. We have a logistic regression repo: GitHub - openfheorg/openfhe-logreg-training-examples: OpenFHE-Based Examples of Logistic Regression Training using Nesterov Accelerated Gradient Descent where we start with a ~relatively~ high mult depth. In that example, we got up to a depth of 29:

• levelsBeforeBootstrap = 14
• approxBootstrapDepth = 8
• levelBudget = {1, 1}

You would/should perform bootstrap before the budget exceeds the threshold. TL;DR you want to keep the bound as tight as possible: declare a depth such that you minimize the number of bootstraps while keeping the depth low. For example, don’t declare a depth of 500 “just to be sure” and to avoid any bootstraps. I’m not well versed in this area and can’t give you a formula other than telling you that you probably need to trace the number of ops.

In the logistic regression example, we structured it such that at the end of every iteration we run a bootstrap and we then determined the appropriate depth for that.

For example, how to use CKK bootstrapping to implement a function and ensure accurate results?

This is only tangentially related, and sorry if you already know this, but are you familiar with the idea of grouping together multiplications? The goal is to reduce the number of homomorphic multiplications required. Quickly skimming the image, it seems like your highest power term is x^{11}, so if we wanted to multiply this, instead of doing the direct multiplication 11 times, you might expand the equation and store intermediate values:

1. x
2. x^2 (one multiplications of x)
3. x^4 (one multiplications of x^2)
4. x^8 (one multiplications of x^4)

and thus you can achieve x^{11} by doing (x^8 \cdot x^2 \cdot x), which only requires 6 multiplications (3 + 1 + 2).

We use this function specifically to rigorously measure the case of a multiplication depth of 11 layers, and to test the impact of bootstrapping combined with multiplication on the results.

# openfhe-development/src/pke/examples/advanced-ckks-bootstrapping.cpp

When I adjust the data size to between 1000-2000 and only perform EvalBootstrap, the result is completely incorrect.

  // Step 4: Encoding and encryption of inputs
// Generate random input
std::vector<double> x;
std::random_device rd;
std::mt19937 gen(rd());
std::uniform_real_distribution<> dis(100.0, 500.0);
// Encoding as plaintexts
// We specify the number of slots as numSlots to achieve a performance
// improvement. We use the other default values of depth 1, levels 0, and no
// params. Alternatively, you can also set batch size as a parameter in the
// CryptoContext as follows: parameters.SetBatchSize(numSlots); Here, we
// assume all ciphertexts in the cryptoContext will have numSlots slots. We
// start with a depleted ciphertext that has used up all of its levels.
uint32_t start_level = depth - 1;
std::cout << "start_level" << start_level << std::endl;
Plaintext ptxt = cryptoContext->MakeCKKSPackedPlaintext(x, 1, start_level,
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;

// Step 5: Perform the bootstrapping operation. The goal is to increase the
// number of levels remaining for HE computation.
//ciph = cryptoContext->EvalMult(ciph, ciph);
auto ciphertextAfter = cryptoContext->EvalBootstrap(ciph);

std::cout << "Number of levels remaining after bootstrapping: "
<< depth - ciphertextAfter->GetLevel() << std::endl
<< std::endl;
Plaintext result;
cryptoContext->Decrypt(keyPair.secretKey, ciphertextAfter, &result);


Several questions/clarifications.

• What parameters are you using for bootstrapping?
• Check the scaling factor and first modulus size. Are they set the same way as in the bootstrapping examples?
• Are you running it for NATIVE_SIZE=128 or 64? NATIVE_SIZE=128 has a higher precision after bootstrapping.
• Are you using single- or double-precision CKKS bootstrapping (double-precision is useful for NATIVE_SIZE=64 and achieves higher precision)
• See the iterative bootstrapping example for double-precision bootstrapping
• An example with a large depth after bootstrapping is the logistic regression training example @iquah mentioned. It does a computation with 14 levels (one iteration of logreg) between bootstrapping calls.
• The level parameter for MakeCKKSPackedPlaintext’ sets the level of the ciphertext after encryption. For example, level 0 means fresh encryption [using the full multiplicative depth = bootstrapping depth + leveled computation after bootstrapping (before next bootstrapping)].
• If you use level 0 (full multiplicative depth is available), then OpenFHE will not need to call bootstrapping as the remaining number of levels is already enough. Hence, a leveled computation will be used. Eventually, a bootstrapping will be called (when the leveled budget is saturated).
• Large magnitude is a bad configuration for CKKS bootstrapping (which seems to be the problem in your most recent example). You always want to scale down the message to 1 (or less than 1). CKKS bootstrapping under the hood uses a sine wave to approximate modular reduction, which means the scaled message should be in an interval where the sine wave is well-approximated by a linear function.

If you want me to look at why your example does not produce correct results, please post the full example, including all parameters for the CryptoContext.

1 Like

The task is to modify the code sample to adjust the size of the random input between 100.0 and 500.0

//==================================================================================
// BSD 2-Clause License
//
// Copyright (c) 2014-2022, NJIT, Duality Technologies Inc. and other contributors
//
// All rights reserved.
//
// Author TPOC: contact@openfhe.org
//
// Redistribution and use in source and binary forms, with or without
// modification, are permitted provided that the following conditions are met:
//
// 1. Redistributions of source code must retain the above copyright notice, this
//    list of conditions and the following disclaimer.
//
// 2. Redistributions in binary form must reproduce the above copyright notice,
//    this list of conditions and the following disclaimer in the documentation
//    and/or other materials provided with the distribution.
//
// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
// AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
// IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
// DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
// FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
// DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
// SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
// CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
// OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
//==================================================================================

/*
Example for CKKS bootstrapping with sparse packing
*/

#define PROFILE

#include "openfhe.h"

using namespace lbcrypto;

void BootstrapExample(uint32_t numSlots);

int main(int argc, char* argv[]) {
// We run the example with 8 slots and ring dimension 4096 to illustrate how to run bootstrapping with a sparse plaintext.
// Using a sparse plaintext and specifying the smaller number of slots gives a performance improvement (typically up to 3x).
BootstrapExample(8);
}

void BootstrapExample(uint32_t numSlots) {
// Step 1: Set CryptoContext
CCParams<CryptoContextCKKSRNS> parameters;

// A. Specify main parameters
/*  A1) Secret key distribution
* The secret key distribution for CKKS should either be SPARSE_TERNARY or UNIFORM_TERNARY.
* The SPARSE_TERNARY distribution was used in the original CKKS paper,
* but in this example, we use UNIFORM_TERNARY because this is included in the homomorphic
* encryption standard.
*/
SecretKeyDist secretKeyDist = UNIFORM_TERNARY;
parameters.SetSecretKeyDist(secretKeyDist);

/*  A2) Desired security level based on FHE standards.
* In this example, we use the "NotSet" option, so the example can run more quickly with
* a smaller ring dimension. Note that this should be used only in
* non-production environments, or by experts who understand the security
* implications of their choices. In production-like environments, we recommend using
* HEStd_128_classic, HEStd_192_classic, or HEStd_256_classic for 128-bit, 192-bit,
* or 256-bit security, respectively. If you choose one of these as your security level,
* you do not need to set the ring dimension.
*/
parameters.SetSecurityLevel(HEStd_NotSet);
parameters.SetRingDim(1 << 12);

/*  A3) Key switching parameters.
* By default, we use HYBRID key switching with a digit size of 3.
* Choosing a larger digit size can reduce complexity, but the size of keys will increase.
* Note that you can leave these lines of code out completely, since these are the default values.
*/
parameters.SetNumLargeDigits(3);
parameters.SetKeySwitchTechnique(HYBRID);

/*  A4) Scaling parameters.
* By default, we set the modulus sizes and rescaling technique to the following values
* to obtain a good precision and performance tradeoff. We recommend keeping the parameters
* below unless you are an FHE expert.
*/
#if NATIVEINT == 128 && !defined(__EMSCRIPTEN__)
// Currently, only FIXEDMANUAL and FIXEDAUTO modes are supported for 128-bit CKKS bootstrapping.
ScalingTechnique rescaleTech = FIXEDAUTO;
usint dcrtBits               = 78;
usint firstMod               = 89;
#else
// All modes are supported for 64-bit CKKS bootstrapping.
ScalingTechnique rescaleTech = FLEXIBLEAUTO;
usint dcrtBits               = 59;
usint firstMod               = 60;
#endif

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

/*  A4) 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 = {3, 3};

// We approximate the number of levels bootstrapping will consume to help set our initial multiplicative depth.
uint32_t approxBootstrapDepth = 8;

/* We give the user the option of configuring values for an optimization algorithm in bootstrapping.
* Here, we specify the giant step for the baby-step-giant-step algorithm in linear transforms
* for encoding and decoding, respectively. Either choose this to be a power of 2
* or an exact divisor of the number of slots. Setting it to have the default value of {0, 0} allows OpenFHE to choose
* the values automatically.
*/
std::vector<uint32_t> bsgsDim = {0, 0};

/*  A5) Multiplicative depth.
* The goal of bootstrapping is to increase the number of available levels we have, or in other words,
* to dynamically increase the multiplicative depth. However, the bootstrapping procedure itself
* needs to consume a few levels to run. We compute the number of bootstrapping levels required
* using GetBootstrapDepth, and add it to levelsUsedBeforeBootstrap to set our initial multiplicative
* depth.
*/
uint32_t levelsUsedBeforeBootstrap = 10;
usint depth =
levelsUsedBeforeBootstrap + FHECKKSRNS::GetBootstrapDepth(approxBootstrapDepth, levelBudget, secretKeyDist);
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);
cryptoContext->Enable(FHE);

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

// Step 2: Precomputations for bootstrapping
cryptoContext->EvalBootstrapSetup(levelBudget, bsgsDim, numSlots);

// Step 3: Key Generation
auto keyPair = cryptoContext->KeyGen();
cryptoContext->EvalMultKeyGen(keyPair.secretKey);
// Generate bootstrapping keys.
cryptoContext->EvalBootstrapKeyGen(keyPair.secretKey, numSlots);

// Step 4: Encoding and encryption of inputs
// Generate random input
std::vector<double> x;
std::random_device rd;
std::mt19937 gen(rd());
std::uniform_real_distribution<> dis(100.0, 500.0);
for (size_t i = 0; i < numSlots; i++) {
x.push_back(dis(gen));
}

// Encoding as plaintexts
// We specify the number of slots as numSlots to achieve a performance improvement.
// We use the other default values of depth 1, levels 0, and no params.
// Alternatively, you can also set batch size as a parameter in the CryptoContext as follows:
// parameters.SetBatchSize(numSlots);
// Here, we assume all ciphertexts in the cryptoContext will have numSlots slots.
// We start with a depleted ciphertext that has used up all of its levels.
Plaintext ptxt = cryptoContext->MakeCKKSPackedPlaintext(x, 1, depth - 1, 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;

// Step 5: Perform the bootstrapping operation. The goal is to increase the number of levels remaining
// for HE computation.
auto ciphertextAfter = cryptoContext->EvalBootstrap(ciph);

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

// Step 7: Decryption and output
Plaintext result;
cryptoContext->Decrypt(keyPair.secretKey, ciphertextAfter, &result);
result->SetLength(numSlots);
std::cout << "Output after bootstrapping \n\t" << result << std::endl;
}
`

out put:

CKKS scheme is using ring dimension 4096

Input: (424.691, 267.531, 237.782, 129.829, 111.516, 305.156, 168.588, 294.903, … ); Estimated precision: 59 bits

Initial number of levels remaining: 1
Number of levels remaining after bootstrapping: 10

Output after bootstrapping
(419.045, 261.984, 232.179, 124.373, 106.045, 299.576, 163.091, 289.27, … ); Estimated precision: 26 bits

Not in front of a computer. But the first thing I can see: the input messages are too large (see the bullet point in my previous nessage). You should scale down the input vector by 500 to get better accuracy.

After you scale down, you can further increase the precision by using iterative (double-precision) bootstrapping ( I assume you compiled with NATIVE_SIZE =64, i.e., the default setting).

1 Like

Hello, sorry for the intrusion
Just wanted to ask, is it a good practice to scale down the ciphertext magnitude before executing a bootstrap, so that all the values are in [0, 1]? Having larger values affects the precision?
Thank you!

Yes, the values should be scaled down to [-1,1]. Otherwise, the accuracy of CKKS bootstrapping will degrade.

2 Likes

Why limit the values to the range of -1 to 1? What are the theoretical reasons behind it? Is it possible to expand this limitation?

Under the hood, modular reduction is approximated using a sine wave. The sine wave approximates well the modular reduction (linear function) only at relatively small values of the argument (|m|/q << 1, where |m| is the CKKS-scaled magnitude of the message and q is the ciphertext/plaintext modulus). If the values are scaled down to -1 to 1, then OpenFHE under the hood makes sure |m|/q << 1. If you increase the values, the approximation error will increase (you will get to the region where the sine wave is no longer close to a linear function).