CKKS 부트스트랩 (Bootstrapping)
암호문은 생성시 잔여 곱셈 횟수가 설정이 되어있고 이후 곱셈을 할 때마다 결과물의 잔여 곱셈 횟수(level)가 줄어드는 방식입니다. 잔여 곱셈 횟수가 0인 암호문은 더이상 곱셈을 할 수 없고 부트스트래핑 연산을 해야합니다.
일반 부트스트랩
부트스트랩 연산에는 부트스트랩 키가 필요합니다. 부트스트랩 연산에 필요한 모든 고정 회전 키로 이루어져 있어서 크기가 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
)
간이 부트스트랩 키
부트스트랩 키를 대신해 회전 키와 간이 부트스트랩 키를 사용해서도 부트스트랩을 수행할 수 있습니다. 회전 키를 사용하여 메모리 사용이 3.8GB 정도로 적지만 느립니다.
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,
)
벤치마크
다음은 부트스트랩의 성능 벤치마크입니다. 실험환경은 CPU의 경우 Intel(R) Core(TM) i7-10700K CPU @ 3.80GHz 을 사용하였고 GPU의 경우 NVIDIA GeForce RTX 5090를 사용하였습니다. 10번 측정한 값의 평균치입니다.
| 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 |
희소 부트스트랩
희소 부트스트랩은 암호문의 슬롯 갯수를 줄여서 부트스트랩 속도를 빠르게 하는 기법입니다. 간이 부트스트랩 키를 사용하거나 부트스트랩 키를 생성해서 수행할 수 있습니다.
부트스트랩 키
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
)
간이 부트스트랩 키
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,
)
벤치마크
다음은 희소 부트스트랩의 성능 벤치마크입니다. 실험환경은 CPU의 경우 Intel(R) Core(TM) i7-10700K CPU @ 3.80GHz 을 사용하였고 GPU의 경우 NVIDIA GeForce RTX 5090를 사용하였습니다. 10번 측정한 값의 평균치입니다.
| 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 |
손실 부트스트랩
손실 부트스트랩은 부트스트랩 내부 연산 순서를 변경하여서 노이즈가 증가하는 대신 빠른 속도를 얻는 기법입니다. 결과물의 소수점 유효자리가 대강 절반 정도 줄어듭니다. 일반적으로는 일반 부트스트랩의 사용이 권장됩니다만 필요한 정확도에 따라서 의미가 있을 수도 있습니다. 간이 부트스트랩 키를 사용하거나 손실 부트스트랩 키를 생성해서 수행할 수 있습니다.
손실 부트스트랩 키
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
)
간이 부트스트랩 키
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,
)
벤치마크
다음은 손실 부트스트랩의 성능 벤치마크입니다. 실험환경은 CPU의 경우 Intel(R) Core(TM) i7-10700K CPU @ 3.80GHz 을 사용하였고 GPU의 경우 NVIDIA GeForce RTX 5090를 사용하였습니다. 10번 측정한 값의 평균치입니다.
| 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 |
부호 부트스트랩
부호 부트스트랩은 손실 부트스트랩의 응용으로서 부호 메세지(-1 또는 1)를 높은 정밀도로 부트스트랩 할 수 있는 기법입니다. 부호 메세지밖에 부트스트랩 할 수 없는 대신, 결과물의 유효자리가 대강 3배 이상 늘어납니다. 부호 메세지에 대해서 효율적인 노이즈 제거가 가능하며, 이로 인해 min 과 max 같은 비교 연산을 빠르고 정밀하게 수행할 수 있게 도와줍니다. 간이 부트스트랩 키를 사용하거나 손실 부트스트랩 키를 생성해서 수행할 수 있습니다.
손실 부트스트랩 키를 이용한 부호 부트스트랩
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
)
간이 부트스트랩 키
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,
)
부호 메세지 부트스트랩 오차
다음은 일반, 손실, 부호 부트스트랩을 각각 이용하여, 부호 메세지(-1 또는 1)를 부트스트랩할 때 발생하는 평균 오차입니다. 부호 메시지에 대해서는 일반 부트스트랩과 손실 부트스트랩의 정밀도가 유사하게 측정되지만, 메시지 구간이 전체 [-1, 1]일 경우에는 일반 부트스트랩이 더 높은 정밀도를 보입니다.
| Regular Bootstrap |
Lossy Bootstrap |
Sign Bootstrap |
|
|---|---|---|---|
| Average error | 1.60562e-3 | 1.60562e-3 | 3.10572e-10 |
벤치마크
다음은 부호 부트스트랩의 성능 벤치마크입니다. 실험환경은 CPU의 경우 Intel(R) Core(TM) i7-10700K CPU @ 3.80GHz 을 사용하였고 GPU의 경우 NVIDIA GeForce RTX 5090를 사용하였습니다. 10번 측정한 값의 평균치입니다.
| 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 |