자료 구조

동형암호 연산에 사용되는 다양한 자료구조를 설명합니다.

엔진 (Engine)

모든 작업의 근간이 되는 자료 구조입니다. 다른 모든 자료 구조들을 생성하고 그 자료 구조들을 활용한 연산을 담당합니다. 파일로 저장하는 경우에도 엔진을 통합니다.

비밀 키 (Secret Key)

복호화에 필요합니다. 다른 모든 키들을 생성할 때에도 필요합니다.

공개 키 (Public Key)

암호화에 필요합니다. 비밀 키를 기반으로 생성합니다. 다자간 연산의 경우 생성 방법이 복잡합니다. 자세한 것은 다자간 연산 문서를 참고해주세요.

암호문 (Ciphertext)

복소수 혹은 실수 배열을 암호화한 암호문입니다. 공개 키를 기반으로 생성합니다. 덧셈, 곱셈 회전 등 많은 동형암호 연산에 사용할 수 있습니다.

암호문은 생성시 잔여 곱셈 횟수가 설정이 되어있고 이후 곱셈을 할 때마다 결과물의 잔여 곱셈 횟수(level)가 줄어드는 방식입니다. 잔여 곱셈 횟수가 0인 암호문은 더이상 곱셈을 할 수 없고 부트스트래핑 연산을 해야합니다. 자세한 것은 부트스트랩 문서를 참고해주세요.

암호문을 생성하면 이차원 다항식으로 구성되어있습니다. 보통 동형암호에서 이차원 다항식을 (b, a)로 표현합니다.

두 암호문이 곱해지면 삼차원 다항식이 됩니다. 이러면 추가적인 연산이 어렵기 때문에 다시 2차원 다항식으로 변경해줘야 합니다. 이 과정을 재선형화라고 부릅니다.

평문 (Plaintext)

복소수 혹은 실수 배열을 인코딩한 평문입니다. 생성에 키를 필요로 하지 않습니다. 암호문과의 연산에 사용할 수 있습니다. 평문을 사용해서 암호화된 데이터와 암호화되지 않은 데이터간의 덧셈과 곱셈 같은 동형암호 연산이 가능합니다.

평문을 생성하면 일차원 다항식으로 구성되어있습니다.

재선형화 키 (Relinearization Key)

암호문을 생성하면 이차원 다항식으로 구성되어있습니다. 두 암호문이 곱해지면 삼차원 다항식이 됩니다. 이러면 추가적인 연산이 어렵기 때문에 다시 2차원 다항식으로 변경해줘야 합니다. 이 과정을 재선형화라고 부르고 재선형화 키는 이 때 사용됩니다. 비밀 키를 기반으로 생성합니다.

켤레화 키 (Conjugation Key)

암호문의 허수부의 부호를 바꾸는 켤레화에 필요합니다. 비밀 키를 기반으로 생성합니다.

고정 회전 키 (Fixed Rotation Key)

암호문을 회전시키는 회전 연산에 필요합니다. 지정된 델타값 만큼 오른쪽으로 회전하는 것만 가능합니다. 비밀 키를 기반으로 생성합니다.

회전 키 (Rotation Key)

암호문을 회전시키는 회전 연산에 필요합니다. 비밀 키를 기반으로 생성합니다.

내부적으로 고정 회전 키들의 기저로 이루어져있어 모든 델타값의 회전이 가능합니다. 내부 고정 회전 키들은 각각 2의 n승의 델타값을 가집니다.

암호문을 3칸 회전하고 싶은 경우에는 세가지 옵션이 있습니다.

델타값 1의 고정 회전 키로 3번 회전
델타값 3의 고정 회전 키로 1번 회전
회전 키로 회전

회전 키를 사용하는 경우, 내부적으로 델타값 1의 고정 회전 키로 회전 한 다음 델타값 2의 고정 회전 키로 회전합니다. 이렇기 때문에 수행시간은 옵션 1이 대략 옵션 2의 세배, 옵션 3가 대략 옵션 2의 두배 정도 소요됩니다. 필요한 델타값이 몹시 한정된 경우가 아니라면 회전 키를 통한 회전을 권장합니다.

부트스트랩 키 (Bootstrap Key)

암호문의 곱셈 횟수를 복구시키는 부트스트랩 연산에 필요합니다. 비밀 키를 기반으로 생성합니다.

내부적으로 부트스트랩 연산에 필요한 모든 고정 회전 키로 이루어져 있어서 크기가 14GB 정도입니다. 메모리 사용량이 많습니다.

메모리가 한정적이라 부트스트랩 키를 사용할 수 없는 경우를 위해서 더 작은 형태의 간이 부트스트랩 키가 존재합니다. 부트스트랩 키는 부트스트랩 연산에 필요한 모든 델타값에 해당하는 고정 회전 키를 가지고 있기 때문에 부트스트랩 연산을 빠르게 처리할 수 있습니다.

대신 간이 부트스트랩 키와 회전 키를 사용하면 메모리가 부족한 상황에서도 부트스트랩 연산이 가능합니다. 간이 부트스트랩 키와 회전 키를 사용하는 경우 6GB 정도의 메모리가 필요합니다. 메모리가 충분하다면 부트스트랩 키를 활용하는 것을 권장합니다.

간이 부트스트랩 키 (Small Bootstrap Key)

암호문의 곱셈 횟수를 복구시키는 부트스트랩 연산에 필요합니다. 비밀 키를 기반으로 생성합니다.

공개 키 A (Public Key A)

다자간 연산의 일종의 공통 공개 키라고 볼 수 있습니다. 개별 공개 키 B를 생성할 때 필요합니다. 모든 개별 공개 키 B를 생성한 후, 공개 키 A와 모든 개별 공개 키 B를 이용해서 최종 공용 공개 키를 생성합니다.

보통 동형암호에서 이차원 다항식을 (b, a)로 표현하는데, 이차원 다항식인 최종 공용 공개 키의 a 부분에 해당하기에 공개 키 A라고 부릅니다. 최종 공개 키와의 혼선을 막기 위해서 이름을 분리하였습니다.

공개 키 B (Public Key B)

다자간 연산의 개별 공개 키입니다. 공용 공개 키들을 생성할 때 필요합니다. 개별 비밀 키와 공통 공개 키 A를 기반으로 생성합니다.

보통 동형암호에서 이차원 다항식을 (b, a)로 표현하는데, 이차원 다항식인 최종 공용 공개 키의 b 부분이 개별 공개 키 B의 합이기 때문에 공개 키 B라고 부릅니다.