순환과 회전
DESILO FHE 라이브러리에서는 순환은 roll, 회전은 rotate을 의미합니다.
벡터 (CKKS)
CKKS 암호문은 벡터이기 때문에 임의의 값만큼씩 이동하는 것이 가능합니다. 이 때 왼쪽 혹은 오른쪽으로 이동하는 것을 선택할 수 있습니다.
많은 FHE 라이브러리들이 암호문을 왼쪽으로 이동시키는 것을 택했습니다. 마이크로소프트 SEAL이나 OpenFHE가 이런 방식을 채택하고 있습니다.
하지만 FHE가 점점 더 복잡한 연산에 적용되면서 행렬 연산에 대한 수요가 늘어가고 있고,
행렬 연산에 있어서는 기존의 파이썬 라이브러리들이 대부분 오른쪽으로 이동하는 것을 택하고 있습니다.
NumPy, PyTorch, TensorFlow 등이 대표적입니다.
어느 방향으로 회전하는 것이 정해진 것이 없는 상황에서 특정 방향 이동이 익숙한 집단에게는 나머지 한 방향이 헷갈릴 수 있습니다. 따라서 DESILO FHE 라이브러리는 양쪽 방향의 이동을 전부 지원합니다.
roll함수는NumPy처럼 오른쪽으로 이동을 시킵니다. 한글로는 순환이라고 표현합니다.rotate함수는SEAL처럼 왼쪽으로 이동을 시킵니다. 한글로는 회전이라고 표현합니다.
Matrix (GL)
GL 암호문은 3차원이고 모든 축에 대한 순환을 지원합니다.
다차원 배열에서는 rotate 보다는 roll이 훨씬 자연스럽기에 GL은 roll 함수만을 지원합니다.
예시
array([[[ 0, 1, 2, 3],
[ 4, 5, 6, 7],
[ 8, 9, 10, 11],
[12, 13, 14, 15]],
[[16, 17, 18, 19],
[20, 21, 22, 23],
[24, 25, 26, 27],
[28, 29, 30, 31]],
[[32, 33, 34, 35],
[36, 37, 38, 39],
[40, 41, 42, 43],
[44, 45, 46, 47]],
[[48, 49, 50, 51],
[52, 53, 54, 55],
[56, 57, 58, 59],
[60, 61, 62, 63]]])
배치 축 순환
array([[[48, 49, 50, 51],
[52, 53, 54, 55],
[56, 57, 58, 59],
[60, 61, 62, 63]],
[[ 0, 1, 2, 3],
[ 4, 5, 6, 7],
[ 8, 9, 10, 11],
[12, 13, 14, 15]],
[[16, 17, 18, 19],
[20, 21, 22, 23],
[24, 25, 26, 27],
[28, 29, 30, 31]],
[[32, 33, 34, 35],
[36, 37, 38, 39],
[40, 41, 42, 43],
[44, 45, 46, 47]]])
세로 축 순환
array([[[12, 13, 14, 15],
[ 0, 1, 2, 3],
[ 4, 5, 6, 7],
[ 8, 9, 10, 11]],
[[28, 29, 30, 31],
[16, 17, 18, 19],
[20, 21, 22, 23],
[24, 25, 26, 27]],
[[44, 45, 46, 47],
[32, 33, 34, 35],
[36, 37, 38, 39],
[40, 41, 42, 43]],
[[60, 61, 62, 63],
[48, 49, 50, 51],
[52, 53, 54, 55],
[56, 57, 58, 59]]])
가로 축 순환
array([[[ 3, 0, 1, 2],
[ 7, 4, 5, 6],
[11, 8, 9, 10],
[15, 12, 13, 14]],
[[19, 16, 17, 18],
[23, 20, 21, 22],
[27, 24, 25, 26],
[31, 28, 29, 30]],
[[35, 32, 33, 34],
[39, 36, 37, 38],
[43, 40, 41, 42],
[47, 44, 45, 46]],
[[51, 48, 49, 50],
[55, 52, 53, 54],
[59, 56, 57, 58],
[63, 60, 61, 62]]])
최적화 기법
키 선택
암호문을 3칸 순환하고 싶은 경우에는 세가지 옵션이 있습니다.
- 이동량 1의 고정 순환 키로 3번 순환
- 이동량 3의 고정 순환 키로 1번 순환
- 순환 키로 순환
순환 키를 사용하는 경우, 내부적으로 이동량 1의 고정 순환 키로 순환 한 다음 이동량 2의 고정 순환 키로 순환합니다. 이렇기 때문에 수행시간은 옵션 1이 대략 옵션 2의 세배, 옵션 3가 대략 옵션 2의 두배 정도 소요됩니다.
필요한 이동량을 정확하게 알고 있는 경우가 아니라면 순환 키를 통한 순환을 권장합니다.
순환 키에 있어서 최악의 이동량은 -1입니다.
내부적으로 12~15회의 순환 연산을 수행해야합니다.
이런 경우에는 이동량 -1의 고정 순환 키가 훨씬 효율적입니다.
다양한 이동량에 대한 처리
GL의 도래 이전에는 CKKS를 활용한 행렬 연산이 많았습니다. 벡터를 순환시키고 곱한 후 결과값을 다시 순환시켜서 행렬 곱셈을 모사하였습니다. 이러한 경우에 특정 암호문을 다양한 이동량으로 순환하는 일이 잦았습니다.
다행히 동형 순환 및 회전에서는 이동량과 상관없이 필요한 전처리 단계가 존재합니다.
이 특성을 활용하면 특정 암호문을 다양한 이동량으로 순환할 때 더 효율적으로 처리할 수 있습니다.
DESILO FHE 라이브러리는 roll_many와 rotate_many 함수를 제공합니다.
고정 순환 키의 배열 혹은 순환 키를 통해서 사용할 수 있습니다.
많은 경우, 다수의 고정 순환 키를 사용하는 방식이 메모리를 더 사용하지만 더 빠르기 때문에 권장되는 사용방식입니다.
예시
from desilofhe import Engine
engine = Engine()
secret_key = engine.create_secret_key()
fixed_roll_key_shift_1 = engine.create_fixed_roll_key(secret_key, shift=1)
fixed_roll_key_shift_2 = engine.create_fixed_roll_key(secret_key, shift=2)
fixed_roll_key_shift_3 = engine.create_fixed_roll_key(secret_key, shift=3)
fixed_roll_key_shift_4 = engine.create_fixed_roll_key(secret_key, shift=4)
roll_key = engine.create_roll_key(secret_key)
message = [1, 2, 3, 4]
ciphertext = engine.encrypt(message, secret_key)
rolled_ciphertexts_1 = engine.roll_many(
ciphertext,
[
fixed_roll_key_shift_1,
fixed_roll_key_shift_2,
fixed_roll_key_shift_3,
fixed_roll_key_shift_4,
],
)
rolled_ciphertexts_2 = engine.roll_many(
ciphertext, roll_key, shifts=[1, 2, 3, 4]
)