Skip to content

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.

Regular Bootstrap

The 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
)

Small 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 10 runs.

Key
Size		 Stage
Count		 Runtime (s)
1 Thread
4 Threads
16 Threads
GPU
Small 3 107.814 44.385 31.861 3.139
Small 4 69.498 28.640 20.738 2.030
Small 5 66.958 27.193 19.377 1.829
Medium 3 30.005 12.747 9.883 0.823
Medium 4 25.182 10.244 7.899 0.676
Medium 5 22.652 9.563 7.171 0.626
Large 3 27.821 11.878 9.617 0.794
Large 4 24.267 10.237 8.195 0.689
Large 5 21.881 8.969 6.945 0.620

Sparse Bootstrap

The bootstrapping operation is faster with a reduced slot_count. The sparse bootstrapping operation can be done with either a bootstrap key or a small bootstrap key.

Bootstrap Key

from desilofhe import Engine

engine = Engine(slot_count=1024, 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, 0] * 256
ciphertext = engine.encrypt(message, public_key, level=0)
bootstrapped = engine.bootstrap(
    ciphertext, relinearization_key, conjugation_key, bootstrap_key
)

Small Bootstrap Key

from desilofhe import Engine

engine = Engine(slot_count=1024, 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, 0] * 256
ciphertext = engine.encrypt(message, public_key, level=0)
bootstrapped = engine.bootstrap(
    ciphertext,
    relinearization_key,
    conjugation_key,
    rotation_key,
    small_bootstrap_key,
    stage_count=1,
)

Benchmark

Here are the benchmarks of the sparse 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.

Slot
Count		 Key
Size		 Stage
Count		 Runtime (s)
1 Thread
4 Threads
16 Threads
GPU
32 Small 1 43.159 17.042 12.191 0.987
32 Small 2 32.921 12.814 9.178 0.737
32 Medium 1 26.965 10.919 8.040 0.623
32 Medium 2 25.492 10.125 7.358 0.587
32 Large 1 26.889 10.821 8.144 0.627
1024 Small 2 71.585 28.191 19.855 1.631
1024 Small 3 48.352 19.431 13.814 1.140
1024 Small 4 45.258 17.673 12.701 1.052
1024 Medium 2 28.620 11.957 9.091 0.724
1024 Medium 3 25.158 10.315 7.700 0.628
1024 Medium 4 24.217 9.691 7.149 0.606
1024 Large 2 27.668 11.456 9.027 0.724
1024 Large 3 24.776 10.019 7.710 0.634

Lossy Bootstap

The lossy bootstrap operation is faster while sacrificing some precision. The resulting significant figures below the decimal is about halved. In general, the regular bootstrapping is the recommended method, but depending on the precision requirements this method could also be useful. The lossy bootstrapping operation can be done with either a lossy bootstrap key or a small bootstrap key.

Lossy Bootstrap Key

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)
lossy_bootstrap_key = engine.create_lossy_bootstrap_key(
    secret_key, stage_count=3
)

message = [-1, 0, 1]
ciphertext = engine.encrypt(message, public_key, level=3)
bootstrapped = engine.lossy_bootstrap(
    ciphertext, relinearization_key, conjugation_key, lossy_bootstrap_key
)

Small Bootstrap Key

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_level_3 = engine.encrypt(message, public_key, level=3)
bootstrapped = engine.lossy_bootstrap(
    ciphertext_level_3,
    relinearization_key,
    conjugation_key,
    rotation_key,
    small_bootstrap_key,
)

ciphertext_level_5 = engine.encrypt(message, public_key, level=5)
bootstrapped_stage_count_5 = engine.lossy_bootstrap(
    ciphertext_level_5,
    relinearization_key,
    conjugation_key,
    rotation_key,
    small_bootstrap_key,
    stage_count=5,
)

Benchmark

Here are the benchmarks of the lossy 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		 Stage
Count		 Runtime (s)
1 Thread
4 Threads
16 Threads
GPU
Small 3 85.590 35.247 26.051 3.015
Small 4 59.425 24.323 17.881 1.969
Small 5 59.594 24.087 17.437 1.776
Medium 3 27.263 11.310 8.626 0.758
Medium 4 22.697 9.497 7.252 0.641
Medium 5 22.049 9.148 6.798 0.614
Large 3 25.060 10.640 8.459 0.747
Large 4 22.396 9.444 7.504 0.664
Large 5 20.696 8.535 6.597 0.602

Sign Bootstrap

The sign bootstrapping operation is a variant of the lossy bootstrap that enables bootstrapping of sign values, i.e., -1 and 1, with higher precision. Although this is applicable only to sign values, the resulting ciphertext achieves roughly three times more significant digits. By efficiently reducing the noise of sign values, this operation facilitates fast and high-precision comparison functions such as min and max. The sign bootstrapping can be performed with either a small bootstrap key or a lossy bootstrap key.

Sign Bootstrap with Lossy Bootstrap Key

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)
lossy_bootstrap_key = engine.create_lossy_bootstrap_key(
    secret_key, stage_count=3
)

message = [-1, 1]
ciphertext = engine.encrypt(message, public_key, level=3)
bootstrapped = engine.sign_bootstrap(
    ciphertext, relinearization_key, conjugation_key, lossy_bootstrap_key
)

Small Bootstrap Key

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, 1]
ciphertext_level_3 = engine.encrypt(message, public_key, level=3)
bootstrapped = engine.sign_bootstrap(
    ciphertext_level_3,
    relinearization_key,
    conjugation_key,
    rotation_key,
    small_bootstrap_key,
)

ciphertext_level_5 = engine.encrypt(message, public_key, level=5)
bootstrapped_stage_count_5 = engine.sign_bootstrap(
    ciphertext_level_5,
    relinearization_key,
    conjugation_key,
    rotation_key,
    small_bootstrap_key,
    stage_count=5,
)

Sign Message Bootstrapping Error

The following shows the average error observed when bootstrapping sign messages (i.e., -1 and 1) using the regular, lossy, and sign bootstrapping methods, respectively. Note that for sign messages, the precision of the regular and lossy bootstrapping is measured to be similar; however, when the message range covers the entire interval [-1, 1], the regular bootstrapping exhibits higher precision.

Regular
Bootstrap		 Lossy
Bootstrap		 Sign
Bootstrap
Average error 1.60562e-3 1.60562e-3 3.10572e-10

Benchmark

Here are the benchmarks of the sign 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		 Stage
Count		 Runtime (s)
1 Thread
4 Threads
16 Threads
GPU
Small 3 87.888 36.027 26.648 2.871
Small 4 59.671 25.027 18.402 1.928
Small 5 59.889 24.756 17.929 1.750
Medium 3 29.019 11.921 9.148 0.783
Medium 4 24.934 10.170 7.696 0.666
Medium 5 23.868 9.814 7.272 0.641
Large 3 27.302 11.373 9.007 0.781
Large 4 24.503 10.145 7.966 0.683
Large 5 22.487 9.211 7.025 0.626