CKKS Bootstrapping

When a ciphertext is created, it has a fixed multiplication count called a level. When two ciphertexts are multiplied, the resulting ciphertext will have the level reduced by one compared to the input ciphertexts. A ciphertext with level 0 can no longer be multiplied. It is possible to reset this level to a higher value by the bootstrapping operation. Bootstrapping requires an engine created with Engine(bootstrap=True), and restores a ciphertext to have 17 multiplicative levels.

Usage

The bootstrapping operation requires the bootstrap key. The bootstrap key incorporates every single fixed roll key that is needed by the bootstrap operation. Because of this, the bootstrap key is quite large (about 14.2GB, see Sizes).

from desilofhe import Engine

engine = Engine(bootstrap=True)
secret_key = engine.create_secret_key()
public_key = engine.create_public_key(secret_key)
relinearization_key = engine.create_relinearization_key(secret_key)
conjugation_key = engine.create_conjugation_key(secret_key)
bootstrap_key = engine.create_bootstrap_key(secret_key)

message = [-1, 0, 1]
ciphertext = engine.encrypt(message, public_key, level=0)
bootstrapped = engine.bootstrap(
    ciphertext, relinearization_key, conjugation_key, bootstrap_key
)

Two real-valued ciphertexts can be bootstrapped at once with merge_bootstrap, which takes the same keys as bootstrap.

Small Bootstrap Key

Alternatively, the bootstrapping operation can be performed using the roll key and the small bootstrap key instead of the bootstrap key. This approach reduces memory usage to around 3.8GB but makes the operation slower.

from desilofhe import Engine

engine = Engine(bootstrap=True)
secret_key = engine.create_secret_key()
public_key = engine.create_public_key(secret_key)
relinearization_key = engine.create_relinearization_key(secret_key)
conjugation_key = engine.create_conjugation_key(secret_key)
roll_key = engine.create_roll_key(secret_key)
small_bootstrap_key = engine.create_small_bootstrap_key(secret_key)

message = [-1, 0, 1]
ciphertext = engine.encrypt(message, public_key, level=0)
bootstrapped = engine.bootstrap(
    ciphertext,
    relinearization_key,
    conjugation_key,
    roll_key,
    small_bootstrap_key,
)

Benchmark

Here are the benchmarks of the bootstrapping operation. The experiments were performed on an Intel(R) Core(TM) i7-10700K CPU @ 3.80GHz for the CPU measurements and an NVIDIA GeForce RTX 5090 for the GPU measurements. These values are the averages of 10 runs. The small key size uses the small bootstrap key and the roll key, and the medium key size uses the bootstrap key.

Key Size	Runtime (s) 1 Thread	8 Threads	GPU
Small	115.305	33.027	1.182
Medium	33.896	10.148	0.116

Precision of Bootstrapping

The following represents the precision of the bootstrapping operation. It is the mean error of bootstrapping, measured over messages uniformly distributed in the interval [-1, 1]. The error is measured against the decrypted input ciphertext, so the encryption error is not included.

	Mean error	Precision
Bootstrap	7.73844e-07	20.3 bits

The errors were measured with the following code.

Bootstrap

import numpy as np
from desilofhe import Engine

engine = Engine(bootstrap=True)

secret_key = engine.create_secret_key()
relinearization_key = engine.create_relinearization_key(secret_key)
conjugation_key = engine.create_conjugation_key(secret_key)
bootstrap_key = engine.create_bootstrap_key(secret_key)

message = np.linspace(-1, 1, engine.slot_count)

ciphertext = engine.encrypt(message, secret_key)
bootstrapped = engine.bootstrap(
    ciphertext, relinearization_key, conjugation_key, bootstrap_key
)

encrypted_decrypted = engine.decrypt(ciphertext, secret_key)
bootstrapped_decrypted = engine.decrypt(bootstrapped, secret_key)

mean_error = np.mean(np.abs(bootstrapped_decrypted - encrypted_decrypted))
print(f"Bootstrap Mean Error: {mean_error}")
print(f"Bootstrap Precision: {-np.log2(mean_error)} bits")