CKKS 부트스트랩 (Bootstrapping)

암호문은 생성시 잔여 곱셈 횟수가 설정이 되어 있고 이후 곱셈을 할 때마다 결과물의 잔여 곱셈 횟수(level)가 줄어드는 방식입니다. 잔여 곱셈 횟수가 0인 암호문은 더이상 곱셈을 할 수 없고 부트스트랩 연산을 해야 합니다. 부트스트랩은 Engine(bootstrap=True)로 생성한 엔진에서만 사용할 수 있으며, 암호문의 곱셈 레벨을 17로 복원합니다.

사용 방법

부트스트랩 연산에는 부트스트랩 키가 필요합니다. 부트스트랩 연산에 필요한 모든 고정 순환 키로 이루어져 있어서 크기가 14.2GB 정도입니다(크기 참고).

from desilofhe import Engine

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

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

실수 암호문 두 개는 merge_bootstrap으로 한 번에 부트스트랩할 수 있으며, bootstrap과 같은 키를 사용합니다.

간이 부트스트랩 키

부트스트랩 키를 대신해 순환 키와 간이 부트스트랩 키를 사용해서도 부트스트랩을 수행할 수 있습니다. 순환 키를 사용하여 메모리 사용이 3.8GB 정도로 적지만 느립니다.

from desilofhe import Engine

engine = Engine(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)
roll_key = engine.create_roll_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,
    roll_key,
    small_bootstrap_key,
)

벤치마크

다음은 부트스트랩의 성능 벤치마크입니다. 실험환경은 CPU의 경우 Intel(R) Core(TM) i7-10700K CPU @ 3.80GHz 을 사용하였고 GPU의 경우 NVIDIA GeForce RTX 5090를 사용하였습니다. 10번 측정한 값의 평균치입니다. Small은 간이 부트스트랩 키와 순환 키를, Medium은 부트스트랩 키를 사용한 결과입니다.

Key Size	Runtime (s) 1 Thread	8 Threads	GPU
Small	115.305	33.027	1.182
Medium	33.896	10.148	0.116

부트스트랩 정밀도

다음은 부트스트랩의 정밀도입니다. [-1, 1] 사이에 고루 분포한 메시지를 기준으로 부트스트랩 오차의 평균을 측정한 값입니다. 오차는 부트스트랩 전 암호문을 복호화한 값과 비교하여 측정하므로 암호화 오차는 포함되지 않습니다.

	Mean error	Precision
Bootstrap	7.73844e-07	20.3 bits

다음 코드로 측정하였습니다.

부트스트랩

import numpy as np
from desilofhe import Engine

engine = Engine(bootstrap=True)

secret_key = engine.create_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 = np.linspace(-1, 1, engine.slot_count)

ciphertext = engine.encrypt(message, secret_key)
bootstrapped = engine.bootstrap(
    ciphertext, relinearization_key, conjugation_key, bootstrap_key
)

encrypted_decrypted = engine.decrypt(ciphertext, secret_key)
bootstrapped_decrypted = engine.decrypt(bootstrapped, secret_key)

mean_error = np.mean(np.abs(bootstrapped_decrypted - encrypted_decrypted))
print(f"Bootstrap Mean Error: {mean_error}")
print(f"Bootstrap Precision: {-np.log2(mean_error)} bits")