CKKS Bootstrapping

When a ciphertext is created, it has a fixed multiplication count called a level. When two cipehrtexts 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.

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 12.3GB).

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
)

Small Bootstrap Key

Alternatively, the bootstrapping operation can be performed using the roll key and the small bootstrap key instead of the bootstrapping 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,
)

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.

Key Size	Runtime (s) 1 Thread	8 Threads	GPU
Small	113.277	33.300	1.170
Medium	33.816	10.113	0.116

Precision of Bootstrapping

The following represents the precision of the bootstrapping operation. It is the average of the bootstrapping error measured over messages uniformly distributed in the interval [-1, 1]. When evaluating the precision of the sign bootstrapping, we use only the sign values (i.e., -1 and 1).

	Average error	Precision	Compact Average error	Compact Precision
Bootstrap	1.08748e-06	19.8 bits	7.02514e-07	20.4 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
)
decrypted = engine.decrypt(bootstrapped, secret_key)

average_noise = np.mean(abs(message - decrypted))
print(f"Bootstrap Average Noise :{average_noise}")
print(f"Bootstrap Average Noise (Bits) :{np.log2(average_noise)}")