콘텐츠로 이동

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 111.153 50.250 34.906 3.080
Small 4 71.865 30.536 21.556 2.007
Small 5 69.345 28.541 19.907 1.820
Medium 3 30.719 12.560 9.732 0.776
Medium 4 24.994 10.196 7.745 0.635
Medium 5 23.611 9.623 7.118 0.600
Large 3 27.399 11.850 9.468 0.747
Large 4 24.226 10.026 8.049 0.648
Large 5 21.586 8.928 6.846 0.582

14 레벨 부트스트랩

기존의 파라미터로는 부트트스랩 후 레벨이 최대 10이 남습니다. stage_count를 3으로 주었을 때 그렇고, stage_count를 키우면 속도가 더 빠르지만 남는 레벨은 더 줄어듭니다. 이를 극복하기 위해서 부트스트랩 후 레벨이 14가 되는 새로운 파라미터를 추가하였습니다. 파라미터의 제약상 stage_count는 3만 지원됩니다.

from desilofhe import Engine

engine = Engine(use_bootstrap_to_14_levels=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)

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

간이 부트스트랩 키

간이 부트스트랩 키도 사용 가능합니다.

from desilofhe import Engine

engine = Engine(use_bootstrap_to_14_levels=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,
)

벤치마크

다음은 부트스트랩의 성능 벤치마크입니다. 실험환경은 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 139.025 60.864 42.782 3.283
Medium 3 37.549 15.535 12.095 0.849
Large 3 33.582 14.619 11.689 0.815

희소 부트스트랩

희소 부트스트랩은 암호문의 슬롯 갯수를 줄여서 부트스트랩 속도를 빠르게 하는 기법입니다. 간이 부트스트랩 키를 사용하거나 부트스트랩 키를 생성해서 수행할 수 있습니다.

부트스트랩 키

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.630 16.745 12.004 0.927
32 Small 2 32.727 12.591 9.002 0.687
32 Medium 1 26.502 10.728 7.889 0.577
32 Medium 2 25.079 10.070 7.202 0.538
32 Large 1 26.197 10.795 7.981 0.580
1024 Small 2 69.975 28.240 19.700 1.582
1024 Small 3 49.533 19.160 13.577 1.080
1024 Small 4 44.567 17.565 12.414 1.010
1024 Medium 2 29.201 11.850 8.916 0.678
1024 Medium 3 25.569 10.188 7.504 0.588
1024 Medium 4 24.274 9.515 6.989 0.562
1024 Large 2 27.581 11.478 8.836 0.670
1024 Large 3 24.617 9.906 7.548 0.589

손실 부트스트랩

손실 부트스트랩은 부트스트랩 내부 연산 순서를 변경하여서 노이즈가 증가하는 대신 빠른 속도를 얻는 기법입니다. 결과물의 소수점 유효자리가 대강 절반 정도 줄어듭니다. 일반적으로는 일반 부트스트랩의 사용이 권장됩니다만 필요한 정확도에 따라서 의미가 있을 수도 있습니다. 간이 부트스트랩 키를 사용하거나 손실 부트스트랩 키를 생성해서 수행할 수 있습니다. 14 레벨 부트스트랩 파라미터에서는 지원하지 않습니다.

손실 부트스트랩 키

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 87.112 38.158 27.515 2.746
Small 4 58.221 24.471 17.754 1.795
Small 5 57.687 24.314 17.201 1.619
Medium 3 24.039 10.046 7.641 0.640
Medium 4 20.360 8.322 6.328 0.534
Medium 5 20.255 8.019 5.979 0.505
Large 3 22.067 9.445 7.483 0.630
Large 4 20.132 8.296 6.590 0.551
Large 5 18.552 7.408 5.743 0.493

손실 부트스트랩의 경우 실수값만 있는 암호문에 대해서 좀 더 빨리 수행됩니다.

Key
Size		 Stage
Count		 Runtime (s)
1 Thread
4 Threads
16 Threads
GPU
Small 3 81.395 35.765 25.752 2.611
Small 4 52.606 22.552 16.032 1.663
Small 5 53.114 22.092 15.689 1.490
Medium 3 18.253 7.532 5.893 0.498
Medium 4 14.835 6.076 4.699 0.395
Medium 5 14.887 5.960 4.436 0.371
Large 3 16.046 7.006 5.731 0.488
Large 4 14.215 6.089 4.952 0.406
Large 5 13.090 5.343 4.214 0.351

부호 부트스트랩

부호 부트스트랩은 손실 부트스트랩의 응용으로서 부호 메세지(-1 또는 1)를 높은 정밀도로 부트스트랩 할 수 있는 기법입니다. 부호 메세지밖에 부트스트랩 할 수 없는 대신, 결과물의 유효자리가 대강 3배 이상 늘어납니다. 부호 메세지에 대해서 효율적인 노이즈 제거가 가능하며, 이로 인해 min 과 max 같은 비교 연산을 빠르고 정밀하게 수행할 수 있게 도와줍니다. 간이 부트스트랩 키를 사용하거나 손실 부트스트랩 키를 생성해서 수행할 수 있습니다. 14 레벨 부트스트랩 파라미터에서는 지원하지 않습니다.

손실 부트스트랩 키를 이용한 부호 부트스트랩

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.257 38.385 27.588 2.744
Small 4 58.256 24.834 17.732 1.808
Small 5 58.498 24.236 17.178 1.625
Medium 3 24.391 10.039 7.656 0.641
Medium 4 20.577 8.415 6.340 0.529
Medium 5 19.968 8.104 5.987 0.509
Large 3 22.408 9.405 7.485 0.628
Large 4 19.977 8.376 6.585 0.543
Large 5 18.151 7.484 5.771 0.491

부호 부트스트랩의 경우 실수값만 있는 암호문에 대해서 좀 더 빨리 수행됩니다.

Key
Size		 Stage
Count		 Runtime (s)
1 Thread
4 Threads
16 Threads
GPU
Small 3 80.993 35.728 25.818 2.611
Small 4 52.593 22.451 16.105 1.662
Small 5 52.560 22.111 15.644 1.488
Medium 3 18.242 7.665 5.890 0.503
Medium 4 14.918 6.026 4.687 0.396
Medium 5 14.895 5.954 4.450 0.375
Large 3 16.271 7.006 5.723 0.489
Large 4 14.378 6.080 4.934 0.404
Large 5 12.840 5.392 4.206 0.351