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.
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 | 108.075 | 44.001 | 32.100 | 3.130 |
| Small | 4 | 70.137 | 28.427 | 20.841 | 2.020 |
| Small | 5 | 66.095 | 26.853 | 19.449 | 1.842 |
| Medium | 3 | 30.512 | 12.734 | 9.924 | 0.823 |
| Medium | 4 | 24.765 | 10.231 | 7.923 | 0.673 |
| Medium | 5 | 23.176 | 9.517 | 7.202 | 0.627 |
| Large | 3 | 28.122 | 11.860 | 9.626 | 0.793 |
| Large | 4 | 23.889 | 10.150 | 8.202 | 0.695 |
| Large | 5 | 20.840 | 8.815 | 6.943 | 0.600 |
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.207 | 16.995 | 12.354 | 0.976 |
| 32 | Small | 2 | 32.293 | 12.706 | 9.275 | 0.729 |
| 32 | Medium | 1 | 26.593 | 10.781 | 8.058 | 0.625 |
| 32 | Medium | 2 | 25.485 | 10.108 | 7.387 | 0.582 |
| 32 | Large | 1 | 26.619 | 10.819 | 8.171 | 0.627 |
| 1024 | Small | 2 | 70.202 | 28.229 | 20.147 | 1.606 |
| 1024 | Small | 3 | 48.467 | 19.313 | 13.929 | 1.129 |
| 1024 | Small | 4 | 45.378 | 17.606 | 12.716 | 1.058 |
| 1024 | Medium | 2 | 29.102 | 11.945 | 9.077 | 0.721 |
| 1024 | Medium | 3 | 25.554 | 10.296 | 7.699 | 0.626 |
| 1024 | Medium | 4 | 23.830 | 9.540 | 7.168 | 0.603 |
| 1024 | Large | 2 | 27.669 | 11.450 | 9.020 | 0.716 |
| 1024 | Large | 3 | 24.548 | 10.021 | 7.713 | 0.626 |
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=0)
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 = engine.encrypt(message, public_key, level=0)
bootstrapped = engine.lossy_bootstrap(
ciphertext,
relinearization_key,
conjugation_key,
rotation_key,
small_bootstrap_key,
)
bootstrapped_stage_count_5 = engine.lossy_bootstrap(
ciphertext,
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 | 84.058 | 34.761 | 26.129 | 3.017 |
| Small | 4 | 59.371 | 24.093 | 17.840 | 1.955 |
| Small | 5 | 59.641 | 23.720 | 17.447 | 1.779 |
| Medium | 3 | 27.120 | 11.205 | 8.637 | 0.761 |
| Medium | 4 | 23.035 | 9.387 | 7.270 | 0.643 |
| Medium | 5 | 21.642 | 8.918 | 6.769 | 0.604 |
| Large | 3 | 25.321 | 10.529 | 8.464 | 0.745 |
| Large | 4 | 22.407 | 9.362 | 7.495 | 0.658 |
| Large | 5 | 19.441 | 8.513 | 6.613 | 0.596 |