Bootstrapping, Part 1

Table of Contents:

Week 6 at SuperSecure

Code

Explanation

What really sets the FHE scheme apart from earlier pre-FHE approaches is its ability to support computations with unbounded circuit depth — a game-changer for practical encrypted computing. The reason circuit depth is usually bounded in traditional homomorphic encryption schemes is because they use a concept called levels. Each multiplication consumes one level, and once the ciphertext reaches level 0, no further multiplications can be performed.

Our CKKS scheme supports bootstrapping — a technique that brings a ciphertext’s level back up to its original state, effectively extending the circuit’s lifespan. However, bootstrapping only works if the scheme is configured with parameters that explicitly support it.

Bootstrapping might sound complex, but in this chapter, we’ll show you how the Bootstrapper class makes it surprisingly easy to use.

Week 6 at SuperSecure, Inc.

After successfully deploying a linear model, we’re now aiming to build more complex models. However, as we increase the depth of the model or try to approximate activation functions using polynomials, we frequently run into level exhaustion issues.

Since decrypting and re-encrypting is out of the question, we’ve decided to integrate bootstrapping technique into our pipeline.

As a first step, you’ve been tasked with writing a bootstrap-enabled prototype that runs without separating the key manager system — just for internal testing purposes.

Task : Begin by setting up the FHE parameters and initializing the evaluation modules required for homomorphic operations.

Next, use the key generator to produce the necessary keys. Note that for this scenario, full power-of-two rotation keys are not required — generate only the specific rotation keys needed for the bootstrapping process.

Once the setup is complete, run a simple computation that consumes a few levels, and then apply the bootstrapping operation.

Finally, verify and print how the ciphertext level is restored after bootstrapping, comparing it to the level before and after the operation.

Code

open code

#include "HEaaN/HEaaN.hpp"

#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <iomanip>
#include <iostream>
#include <numeric>

int main() {
    const auto preset{HEaaN::ParameterPreset::FGb};
    const auto context = makeContext(preset);
    const auto log_slots = HEaaN::getLogFullSlots(context);

    const auto sk = HEaaN::SecretKey(context);
    const auto pack = HEaaN::KeyPack(context);
    const auto keygen = HEaaN::KeyGenerator(context, sk, pack);

    const bool min_key = false;

    std::cout << "Generate enc / conj / mult keys ... \n";
    keygen.genEncKey();
    keygen.genConjKey();
    keygen.genMultKey();
    std::cout << "Generate rotation keys used in the bootstrap process ...\n";
    keygen.genRotKeysForBootstrap(log_slots, min_key);

    const auto eval = HEaaN::HomEvaluator(context, pack);

    std::cout << "Generate Bootstrapper ...\n";
    const auto btp = HEaaN::Bootstrapper(eval, log_slots, min_key);

    HEaaN::Message message(HEaaN::getLogFullSlots(context));
    const auto message_size = message.getSize();

    for (int i = 0; i < message_size; ++i) {
        message[i].real(std::rand() / static_cast<HEaaN::Real>(RAND_MAX));
        message[i].imag(std::rand() / static_cast<HEaaN::Real>(RAND_MAX));
    }

    HEaaN::Ciphertext ctxt(context), ctxt_res(context), ctxt_boot(context);
    const auto enc = HEaaN::Encryptor(context);
    enc.encrypt(message, sk, ctxt, 4);
    std::cout << "Input Ciphertext - level : " << ctxt.getLevel()
              << "\n";

    eval.mult(ctxt, ctxt, ctxt_res);

    std::cout << "Result Ciphertext - level : " << ctxt_res.getLevel() << "\n";

    std::cout << "Bootstrap ... \n";
    if (ctxt_res.getLevel() < btp.getMinLevelForBootstrap())
        throw HEaaN::RuntimeException(
            "The input Ciphertext is smaller than the minimum level for bootstrap");
    btp.bootstrap(ctxt_res, ctxt_boot, true);

    std::cout << "Bootstrapped Ciphertext - level : "
                << ctxt_boot.getLevel() << "\n";

    const auto dec = HEaaN::Decryptor(context);
    HEaaN::Message dmsg_res, dmsg_boot;
    dec.decrypt(ctxt_res, sk, dmsg_res);
    dec.decrypt(ctxt_boot, sk, dmsg_boot);

    std::cout << "\nPlaintext Message : \n";
    std::cout << std::left << std::setw(24) << "Computed" << "Bootstrap \n";
    std::cout << std::fixed << std::setprecision(4);
    for (HEaaN::u64 i = message_size - 10; i < message_size; i++) {
        std::cout << std::left << std::setw(24)
                  << dmsg_res[i] << dmsg_boot[i] << "\n";
    }

    HEaaN::Real max_error = std::transform_reduce(
        dmsg_res.begin(), dmsg_res.end(), dmsg_boot.begin(),
        0.0, [](auto x, auto y) { return std::max(x, y); },
        [](auto x, auto y) { return std::abs(x - y);});
    std::cout << "Log max error: " << std::log2(max_error) << "\n";
}

Explanation

Let's explore the code line by line.

In this post, we’ll walk through an example code for performing bootstrapping. The entire process is divided into three parts, and each step can be handled with a simple API call.

Generate keys for bootstrapping
Construct the bootstrapper
Run bootstrapping after a single multiplication

Let’s dive into each step. We’ll start by introducing a new parameter, $FGb$.

    const auto preset{HEaaN::ParameterPreset::FGb};

We introduce a new parameter, $FGb$, which enables bootstrapping. The first letter "F" stands for Fully Homomorphic Encryption (FHE)—a scheme that supports unlimited multiplication through bootstrapping. This is in contrast to the previous parameter, $SD3$, which represents a somewhat homomorphic encryption scheme and supports only a limited number of multiplications without bootstrapping.

The second letter "G"¹ indicates a log-degree of 16, referring to the degree of the polynomial used in the underlying algebraic structure. For now, it’s enough to know that this allows for a maximum message size of 32,768 slots, which is half the polynomial degree.

We’ll explore the parameter details more thoroughly in the upcoming Parameter section.

    const bool min_key = false;

This variable determines whether key size optimization will be applied. It’s a boolean flag that can be passed to both the key generation function and the constructor of the bootstrapper. However, providing it explicitly is optional, as both functions default to min_key = false.

When set to true, the key size is significantly reduced—with minimal performance trade-offs. For example, in the $FGb$ parameter setting, the number of rotation keys drops from 38 to just 8, while bootstrapping time increases by only about 10–20%.

Whether to enable this option depends on your specific use case. If minimizing key size is a priority and slight performance degradation is acceptable, enabling it can be a worthwhile optimization.

    std::cout << "Generate enc / conj / mult keys ... \n";
    keygen.genEncKey();
    keygen.genConjKey();
    keygen.genMultKey();
    std::cout << "Generate rotation keys used in the bootstrap process ...\n";
    keygen.genRotKeysForBootstrap(log_slots, min_key);

Bootstrapping requires conjugation keys, multiplication keys, and rotation keys. Among these, rotation keys can be generated using the genRotKeysForBootstrap() function. Unlike the general genRotKeyBundle() method, this approach does not require generating rotation keys for all power-of-two indices.

Let’s take a closer look at the arguments of the key generation function. The log_slots argument specifies the base-2 logarithm of the number of slots in the input ciphertext. Note that the number of slots in the ciphertext refers to the number of message slots encrypted within that ciphertext.

If you enable the min key optimization, it’s sufficient to generate only the minimal set of rotation keys by setting min_key = true as the second argument.

    std::cout << "Generate Bootstrapper ...\n";
    const auto btp = HEaaN::Bootstrapper(eval, log_slots, min_key);

Note that the HomEvaluator is passed to the bootstrapper so that it can access the evaluation key managed by the evaluator.

If you're bootstrapping a ciphertext that uses the full number of slots, you don't need to explicitly specify the log_slots argument. However, if the ciphertext uses fewer slots, you must provide the same log_slots value used during key generation to ensure consistency.

The min_key option in the bootstrapper’s constructor is set to false by default. If you generated only the minimal set of rotation keys, make sure to set min_key = true in the constructor as well.

When the bootstrapper is constructed, it internally generates the constants required for bootstrapping, assuming full-slot ciphertexts by default. If the log_slots argument is explicitly provided, the bootstrapper creates the corresponding bootstrapping constants for that slot size instead. Regardless of this, bootstrapping for single-slot ciphertexts is always supported.

    std::cout << "Input Ciphertext - level : " << ctxt.getLevel()
              << "\n";

    eval.mult(ctxt, ctxt, ctxt_res);

    std::cout << "Result Ciphertext - level : " << ctxt_res.getLevel() << "\n";

You can verify that a multiplication operation reduces the ciphertext's level by one. The only way to restore the level while preserving the encrypted message with negligible error is to perform bootstrapping.

You can confirm this by running the bootstrap and printing the ciphertext’s level as shown below:

    std::cout << "Bootstrap ... \n";
    if (ctxt_res.getLevel() < btp.getMinLevelForBootstrap())
        throw HEaaN::RuntimeException(
            "The input Ciphertext is smaller than the minimum level for bootstrap");
    btp.bootstrap(ctxt_res, ctxt_boot, true);

    std::cout << "Bootstrapped Ciphertext - level : "
                << ctxt_boot.getLevel() << "\n";

Before bootstrapping, make sure that the input ciphertext has a level greater than or equal to the minimum level required for bootstrapping. In most cases—including when using the $FGb$ parameter—the minimum level is 3, which is consumed during the SlotToCoeff step. (See Remark for more details.)

Additionally, the third argument in the bootstrap function should be set to true if the encrypted message contains complex numbers. If the message consists of real numbers only, you can omit this argument—doing so results in a bootstrapping process that is approximately 30% faster.

Remark – How Does Bootstrapping Work?

You don’t need a deep mathematical understanding of bootstrapping to use it effectively. However, having a high-level overview of how it works can provide valuable intuition. For example, it may help you understand why various evaluation keys are required and how they're used, why bootstrapping is more computationally intensive than other homomorphic operations, and why there are range limitations on input messages, among other things.

Bootstrapping generally consists of four main steps: $$ \text{SlotToCoeff} \to \text{LevelRecover} \to \text{CoeffToSlot} \to \text{EvalMod} $$

The $\text{SlotToCoeff}$ and $\text{CoeffToSlot}$ steps perform homomorphic evaluations of the DFT and inverse DFT (iDFT) matrices, respectively. $\text{EvalMod}$ evaluates a polynomial which approximates the function that computes modulo $1$ within a given range.

These steps rely on different evaluation keys:

Rotation keys are required for matrix evaluations (i.e., $\text{SlotToCoeff}$ and $\text{CoeffToSlot}$)
Multiplication key is needed for polynomial evaluations in $\text{EvalMod}$
Conjugation key comes into play after $\text{CoeffToSlot}$, since its result may contain complex values. Before evaluating the polynomial in $\text{EvalMod}$, the ciphertext must be separated into real and imaginary parts, which requires the conjugation key.

But what exactly is the $\text{LevelRecover}$ step? LevelRecover is, in fact, an essential part of bootstrapping. While a detailed explanation is out of scope for now, the basic idea is this: It lifts a message at a lower level (e.g., x mod q) to a higher level representation (e.g., x + qI mod Q). At this point, although the level is restored, the message now contains unwanted integer noise terms (qI). If the message x is known to lie within the range (−1,1), applying a mod 1 function can recover the correct x mod Q.

However, we cannot directly evaluate the mod 1 function right after $\text{LevelRecover}$, because that step exists only in the coefficient-encoded domain. Therefore, it must be wrapped between $\text{SlotToCoeff}$ and $\text{CoeffToSlot}$ to convert the message to and from the coefficient space appropriately.

Now that we've explored how bootstrapping restores the ciphertext level, you should have a general idea of the overall process. While we didn’t go into the full details of matrix and polynomial evaluations—both of which are computationally expensive operations—they play a major role in bootstrapping. Fortunately, HEaaN includes many optimizations that make these heavy computations practically applicable.

Starting from the next chapter, we’ll move beyond basic API usage and dive into more advanced topics that will help you apply HEaaN in more flexible and powerful ways. We hope this helps you get even more comfortable with HEaaN!

No portion of this book may be reproduced in any form without written permission from CryptoLab, Inc.

acronym for Grande ↩

Keyboard shortcuts

The HEaaN Book

Bootstrapping, Part 1

Week 6 at SuperSecure, Inc.

Code

Explanation

Remark – How Does Bootstrapping Work?