본 논문에서는 CKKS-기반 완전동형암호를 위한 가변적인 구조의 키 교환 아키텍처를 제안하고 FPGA를 이용해 하드웨어로 구현한다. 키 교환 알고리즘은 완전동형암호 시스템에서 특정 연산 이후에 암호문이 원래의 키로 복호화될 수 없는 문제를 해결하기 위한 하위 알고리즘이다. 키 교환 알고리즘은 NTT(Number Theoretic Transform) 연산과 기저 변환(Base Conversion) 연산을 반복하는 복잡하고 실행시간이 긴 연산이다. NTT와 Base Conversion은 그 자체로도 이미 복잡한 연산인데, 이를 반복하는 Key-Switching 자체도 특정 연산 이후마다 매번 반복되어야 한다. 따라서 키 교환 아키텍처는 차세대 암호인 완전동형암호에서 가장 신중하게 설계되어야 할 핵심 모듈이다.
최신 완전동형암호 체계(Shceme)들은 RNS(Residue Number System)를 도입하여 큰 정수(Big Integer)에 대한 직접적인 연산을 여러 Residue에 대한 연산들로 대체한다. 이는 동형암호 시스템이 연산 가능한 Modulus의 범위를 확장했지만, 키 교환과 같은 특정 연산의 복잡도는 더욱 증가시켰다. 그러므로 하드웨어 설계자는 RNS를 지원하는 완전동형암호 시스템을 설계할 때 연산의 반복성과 연산에 필요한 파라미터의 크기를 충분히 고려하여 설계하여야 한다.
최신 동형암호 체계들은 Ring-LWE(Learning With Error)를 기반으로 암호화와 키 생성 시 잡음(Noise)을 추가하여 보안성을 강화한다. 따라서 CKKS-기반 완전동형암호는 암호문의 특정 연산마다 잡음이 증가하며, 그 횟수가 곱셈 레벨(Multiplicative Level, L)로 제한되어 있다. 이러한 곱셈 레벨 L은 시스템의 성능을 결정하면서 동시에 분해 숫자(dnum, Decomposition Number), 다항식 길이(Polynomial Length, N), Modulus의 비트 길이(Modulus Bit-Width, logQ), 보안 단계(Security Level, λ)와 같은 중요한 시스템 변수들과 긴밀하게 연관되어 있어 응용될 분야에 따라 유연하게 선택될 필요가 있다. 그러나 대부분의 키 교환 아키텍처 연구는 특정 응용에 최적화된 곱셈 레벨로 시스템을 한정하여 유연성을 포기한다. 본 논문에서는 여러 곱셈 레벨을 지원하는 가변적인 구조의 키 교환 아키텍처를 제안한다.
키 교환 아키텍처에서 가장 중요한 연산인 NTT는 다항식 곱셈의 시간복잡도를 O(N²)에서 O(NlogN)으로 낮추어 완전동형암호 시스템에서 빈번히 일어나는 긴 길이의 다항식 곱셈을 가속화한다. 216의 긴 길이의 다항식 곱셈을 수행하는 완전동형암호 시스템에서 NTT 아키텍처는 하드웨어 크기와 성능을 결정하는 핵심 모듈이다. 추가로, RNS를 지원하는 키 교환 알고리즘에서 서로 다른 Modulus에 대하여 여러 번 반복되는 만큼 NTT의 설계는 여러 Modulus를 효율적으로 지원하여야 한다. 따라서 본 논문에서는 NTT와 INTT, 기저 변환, 키 곱셈을 하나의 모듈로 수행 가능한 가변 연산 코어(Configurable Arithmetic Core)를 제안한다. 또한, 서로 다른 Modulus에 대하여 NTT의 회전 인자(Twiddle Factor)를 변환 중에 생성하는 회전인자 생성기(Twiddle Factor Generator) 모듈을 추가하여 메모리 자원을 줄이고 회전 인자를 위한 Off-Chip Memory Access를 줄이는 방법을 제안한다.
본 논문에서는 키 교환 알고리즘에 사용되는 연산들을 동시에 지원하는 가변 연산 코어(Configurable Arithmetic Core)를 활용하여 여러 곱셈 레벨을 지원하는 가변적인 구조의 키 교환 아키텍처를 제안한다. 그리고 해당 아키텍처를 Xilinx사의 ALVEO FPGA에 구현하여 최신 완전동형암호 라이브러리인 OpenFHE와 비교한다.