CKKS Bootstrappping

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.

Bootstrapping operation requires the bootstrap key. The bootstrap key incorporates every single fixed rotation 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(use_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, stage_count=3)

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

Alternatively, the bootstrapping operation can be performed using the rotation 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(use_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)
rotation_key = engine.create_rotation_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,
    rotation_key,
    small_bootstrap_key,
)

bootstrapped_stage_count_5 = engine.bootstrap(
    ciphertext,
    relinearization_key,
    conjugation_key,
    rotation_key,
    small_bootstrap_key,
    stage_count=5,
)

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 100 runs.

Key Size	Stage Count	Runtime (s) Single Thread	4 Threads	16 Threads	GPU
Small	3	107.951	44.272	32.225	3.820
Small	4	69.508	28.681	20.864	2.532
Small	5	67.132	27.136	19.533	2.328
Medium	3	30.741	12.807	9.895	0.984
Medium	4	25.106	10.297	7.898	0.815
Medium	5	22.728	9.593	7.223	0.768
Large	3	27.456	11.956	9.618	0.928
Large	4	23.878	10.202	8.206	0.816
Large	5	20.769	8.777	6.904	0.725