본 논문에서는 가변적인 구조의 NTT 아키텍처를 제안하고 FPGA를 이용해 하드웨어로 구현한다. NTT 아키텍처는 차세대 암호인 양자내성암호, 동형암호의 핵심 모듈이다. NTT는 Ring-LWE의 다항식 곱셈의 복잡도를 O(N²)에서 O(NlogN)으로 낮추어주는 역할을 하여 암호 알고리즘을 가속 시킨다. FPGA 기반 NTT 아키텍처는 여기에 더해 하드웨어적으로 구성된 병렬적 구조로 성능을 최대화하는데 유리하다. 그러나 하드웨어 기반의 아키텍처는 병렬화를 통해 빠른 성능을 구현하는 것은 유리하지만 다양한 길이, 다양한 모듈러스를 지원하는 등의 유연성이 낮다.
동형암호는 다른 Ring-LWE 암호와 다르게 복수의 표준을 지원한다. 동형암호표준화기구(Homomorphic Encryption Standardization)에서 지정한 동형암호의 표준은 기구에서 지정한 수학적 정의를 만족하는 어떠한 수도 사용할 수 있고, 이는 동형암호 사용자가 정밀도, 연산횟수 등 사용자의 용도에 맞게 선택한다. 동형암호 아키텍처는 사용자가 선택하는 다양한 길이와 모듈러스를 지원하는 하드웨어를 제공해야 한다. 따라서 동형암호 아키텍처는 다른 Ring-LWE 암호에서 목표로 하는 병렬화를 통한 빠른 성능 구현과 더불어 복수의 표준에 만족하는 다양한 길이, 다양한 모듈러스를 지원해야한다.
제안하는 NTT 아키텍처는 다양한 길이와 다양한 모듈러스를 지원하는 가변적인 구조로 설계되었으며, 가변적인 구조를 지원하기 위하여 모듈러 덧셈기, 모듈러 뺄셈기, 모듈러 곱셈기 등 모듈러 연산기의 최적화된 구조와 Cooley-Tukey 알고리즘, Gentleman-Sande 알고리즘의 원리를 이용하여 다양한 길이를 지원할 수 있는 하드웨어 구조를 제안하고 구현한다. 모듈러 연산기는 DSP-기반의 모듈로 높은 효율성을 보여주며, 다양한 모듈러스에 대하여 동작이 가능하다. 또한 MUX, DEMUX를 이용한 구조를 통해 다양한 길이의 다항식의 NTT 변환이 가능하다.
본 논문에서는 동형암호표준화기구에서 제시한 표준을 준수하는 NTT 아키텍처를 제안하고 구현한다. 제안하는 구조는 SDF(Single-path Delay Feedback) 구조와 MDF(Multi-path Delay Feedback) 구조의 가변적인 NTT와 DSP의 효율을 고려한 51비트, CPU와 호환성을 고려한 64비트 등 4가지의 가변적인 NTT 아키텍처 구조를 제안하고 구현하였다. 제안한 4가지 구조의 FPGA에서 LUT, FF, DSP, BRAM의 하드웨어 자원 사용량과 데이터 처리량을 통해 성능을 분석한다.