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를 사용하였습니다. 100번 측정한 값의 평균치입니다.

Key Size	Stage Count	Runtime (s) Single Thread	4 Threads	16 Threads	GPU
Small	3	107.951	44.272	32.225	3.820
Small	4	69.508	28.681	20.864	2.532
Small	5	67.132	27.136	19.533	2.328
Medium	3	30.741	12.807	9.895	0.984
Medium	4	25.106	10.297	7.898	0.815
Medium	5	22.728	9.593	7.223	0.768
Large	3	27.456	11.956	9.618	0.928
Large	4	23.878	10.202	8.206	0.816
Large	5	20.769	8.777	6.904	0.725