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 | 112.855 | 49.511 | 34.892 | 3.244 |
| Small | 4 | 72.206 | 30.261 | 21.456 | 2.087 |
| Small | 5 | 69.744 | 28.182 | 19.953 | 1.860 |
| Medium | 3 | 29.953 | 12.602 | 9.679 | 0.798 |
| Medium | 4 | 24.568 | 10.166 | 7.721 | 0.666 |
| Medium | 5 | 23.184 | 9.292 | 7.024 | 0.610 |
| Large | 3 | 27.919 | 11.707 | 9.410 | 0.775 |
| Large | 4 | 23.825 | 10.085 | 8.002 | 0.682 |
| Large | 5 | 21.833 | 8.843 | 6.805 | 0.605 |
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.691 | 16.939 | 11.995 | 0.958 |
| 32 | Small | 2 | 32.765 | 12.445 | 8.973 | 0.715 |
| 32 | Medium | 1 | 26.860 | 10.705 | 7.842 | 0.601 |
| 32 | Medium | 2 | 25.064 | 10.038 | 7.174 | 0.563 |
| 32 | Large | 1 | 26.677 | 10.675 | 7.947 | 0.608 |
| 1024 | Small | 2 | 71.156 | 27.944 | 19.692 | 1.621 |
| 1024 | Small | 3 | 49.461 | 18.887 | 13.523 | 1.115 |
| 1024 | Small | 4 | 45.306 | 17.388 | 12.363 | 1.030 |
| 1024 | Medium | 2 | 29.124 | 11.797 | 8.873 | 0.713 |
| 1024 | Medium | 3 | 25.419 | 10.089 | 7.478 | 0.609 |
| 1024 | Medium | 4 | 23.737 | 9.517 | 6.942 | 0.586 |
| 1024 | Large | 2 | 27.490 | 11.422 | 8.808 | 0.698 |
| 1024 | Large | 3 | 24.107 | 9.995 | 7.500 | 0.615 |
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 | 88.473 | 39.457 | 28.426 | 2.994 |
| Small | 4 | 60.810 | 25.715 | 18.462 | 1.946 |
| Small | 5 | 60.956 | 25.286 | 17.898 | 1.763 |
| Medium | 3 | 27.058 | 11.120 | 8.460 | 0.743 |
| Medium | 4 | 23.013 | 9.275 | 7.074 | 0.632 |
| Medium | 5 | 21.614 | 8.803 | 6.587 | 0.583 |
| Large | 3 | 24.660 | 10.575 | 8.288 | 0.736 |
| Large | 4 | 22.537 | 9.248 | 7.324 | 0.643 |
| Large | 5 | 20.418 | 8.476 | 6.422 | 0.586 |
Lossy bootstrapping is optimized for ciphertexts that contain only real values.
| Key Size |
Stage Count |
Runtime (s) 1 Thread |
4 Threads |
16 Threads |
GPU |
|---|---|---|---|---|---|
| Small | 3 | 81.182 | 36.468 | 26.231 | 2.816 |
| Small | 4 | 54.158 | 22.795 | 16.481 | 1.764 |
| Small | 5 | 54.706 | 22.387 | 15.977 | 1.573 |
| Medium | 3 | 19.560 | 8.181 | 6.291 | 0.546 |
| Medium | 4 | 15.120 | 6.534 | 5.056 | 0.436 |
| Medium | 5 | 15.980 | 6.428 | 4.778 | 0.419 |
| Large | 3 | 17.569 | 7.589 | 6.120 | 0.539 |
| Large | 4 | 15.494 | 6.545 | 5.313 | 0.455 |
| Large | 5 | 14.183 | 5.803 | 4.563 | 0.398 |
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 | 90.156 | 40.110 | 28.902 | 3.010 |
| Small | 4 | 62.716 | 26.354 | 18.871 | 1.954 |
| Small | 5 | 62.520 | 25.710 | 18.166 | 1.749 |
| Medium | 3 | 28.490 | 11.804 | 8.920 | 0.751 |
| Medium | 4 | 24.785 | 9.980 | 7.494 | 0.643 |
| Medium | 5 | 23.152 | 9.552 | 6.992 | 0.594 |
| Large | 3 | 26.978 | 11.193 | 8.767 | 0.746 |
| Large | 4 | 24.212 | 10.027 | 7.755 | 0.654 |
| Large | 5 | 21.975 | 9.037 | 6.800 | 0.591 |
Sign bootstrapping is optimized for ciphertexts that contain only real values.
| Key Size |
Stage Count |
Runtime (s) 1 Thread |
4 Threads |
16 Threads |
GPU |
|---|---|---|---|---|---|
| Small | 3 | 83.431 | 36.998 | 26.711 | 2.805 |
| Small | 4 | 54.858 | 23.234 | 16.717 | 1.756 |
| Small | 5 | 55.208 | 22.943 | 16.296 | 1.579 |
| Medium | 3 | 20.354 | 8.515 | 6.547 | 0.559 |
| Medium | 4 | 17.047 | 6.906 | 5.291 | 0.449 |
| Medium | 5 | 16.954 | 6.703 | 5.015 | 0.425 |
| Large | 3 | 18.636 | 7.825 | 6.389 | 0.542 |
| Large | 4 | 16.413 | 6.971 | 5.543 | 0.464 |
| Large | 5 | 15.217 | 6.160 | 4.752 | 0.408 |