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) Single Thread	4 Threads	16 Threads	GPU
Small	3	106.522	43.652	31.606	5.491
Small	4	69.354	28.463	20.566	3.386
Small	5	66.456	26.981	19.198	2.924
Medium	3	30.313	12.799	9.825	0.975
Medium	4	24.776	10.228	7.848	0.813
Medium	5	22.499	9.518	7.166	0.775
Large	3	27.716	11.924	9.565	0.925
Large	4	24.111	10.184	8.144	0.822
Large	5	21.334	8.908	6.921	0.733