NTRU Hardware Accelerator Based on Fast Convolution Methods for Post-Quantum Cryptography

Abstract

본 논문에서는 차세대 암호 시스템인 양자 내성 암호 (PQC) NTRU의 하드웨어 가속기를 구현하였다. 양자 컴퓨터가 개발되면 기존 암호 시스템이 위협될 것으로 예측되며, 이에 대응하여 미국 NIST에서는 차세대 암호 시스템으로써 양자 내성 암호 표준 공모를 진행하고 있다. NTRU는 lattice 기반 난제에 근간을 두는 유망한 PQC 후보 알고리즘이다. 현재 PQC NTRU는 소프트웨어 코드로만 공개되어 있으나, 많은 연산량을 요구하는 Convolution을 수행하는 데에 비효율적이다. 본 논문에서는 크기가 큰 polynomial 곱셈을 가속화하기 위해 Fast Convolution 구조를 고안하였다.

본 논문의 의의는 다음과 같다. 첫째, 소프트웨어 코드 대비 시간 복잡도를 줄이고 하드웨어 선행 연구 대비 가속화 Convolution을 수행하는 구조를 고안하였다. 둘째, PQC 요구 사항에 적합한 NTRU parameter set을 사용하여 하드웨어로 구현하였다. 고안된 Convolution 구조는 곱셈기를 사용하지 않고, ternary polynomial의 특성을 이용하여 덧셈기로만 연산을 진행한다. 또한, rotation을 적용하여 truncated polynomial ring 내에서 연산이 이루어지도록 하였다. Fast Convolution의 경우, 가속화 모듈을 추가하여 동시에 처리되는 항의 개수를 증가하여 연산에 필요한 clock cycle을 감소시켰다. 본 연구에서는 기본 모듈(NTRU x1)과 2배속 모듈(NTRU x2), 4배속 모듈(NTRU x4)을 제시하였다. 해당 NTRU는 모두 PQC parameter set을 적용하여 구현되었다.

효율적인 Convolution 연산 구조를 적용한 설계는 하드웨어 기술 언어인 Verilog를 사용하여 구현되었으며, Design Compiler를 통해 합성 또한 진행하였다. 성능 개선에 따른 면적을 실험한 결과, 속도가 4배 가속될 때 면적이 2배만 증가하는 설계 결과를 보였다. 4배속 모듈의 경우 ⌈N/4⌉번의 clock cycle만이 필요하기 때문에, Convolution이 두 번 진행되는 복호화 과정에서 특히 효과적인 연산 수행이 가능하다. 한편, PQC NTRU 연산을 위한 하위 모듈에서 면적 최적화 또한 진행하였다.

고안된 Fast Convolution 구조는 PQC 후보군 중 NTRU 외 다른 lattice 기반 암호 시스템 연산에도 활용될 수 있다. 또한, 면적의 여유가 있을 경우 Fast Convolution 구조를 확장하여 추가 가속 모듈을 적용할 수 있다. 즉, 본 논문은 효율적인 하드웨어 설계를 위해 Convolution 연산량을 줄이면서 양자 내성 암호 기준에 맞는 고성능 설계 방법을 제시한다.| In this paper, a hardware accelerator for NTRU of post-quantum cryptography (PQC), a next-generation cryptosystem, is implemented. It is predicted that the emergence of quantum computers will threaten the existing cryptographic system. In response, the National Institute of Standards and Technology (NIST) has conducted the standardization of PQC since 2016. Among the candidates, NTRU is a promising algorithm based on the mathematical hardness of lattice. Currently, PQC NTRU is only released as a software code; however, it is inefficient to perform Convolution which requires a considerable amount of operations. The proposed Fast Convolution architecture accelerates the multiplication of large polynomials.

The contributions of this work are as follows. First of all, the devised method reduces the time complexity compared to software NTRU and performs faster Convolution, unlike previous studies. Second, the implemented hardware accelerator used parameter sets that are suitable for PQC requirements. The proposed Convolution method does not require multipliers; however, by using the characteristics of ternary polynomial, it can be operated only with adders and multiplexers.

In addition, calculations are performed by rotation to operate over truncated polynomial rings. For Fast Convolution, the number of terms processed simultaneously is increased by adding acceleration modules. Therefore, the clock cycles required for the operations are reduced up to four times. In this paper, a basic module (NTRU x1), a module with double-speed (NTRU x2), and quadruple-speed (NTRU x4) are presented. All the NTRU versions are implemented with PQC parameter sets.

For the experimental results, the proposed architecture was implemented in Verilog, a hardware description language, and synthesized with Design Compiler. As a result, it shows that the area only increased by two times when the speed was accelerated about four times. Indeed, Fast Convolution with quadruple-speed only requires ⌈𝑁/4⌉ clock cycles to operate Convolution. This performance contributes to the efficiency of decryption where Convolution is operated twice in contrast to encryption. Area optimization for the submodules of NTRU operations was also performed.

This proposed architecture with high performance can be utilized for other lattice-based cryptography of NIST PQC candidates. This implementation also shows high scalability for additional acceleration methods. In summary, this paper presents a hardware accelerator for NTRU of post-quantum cryptography that shows high performance and quantum resistance while reducing the amount of computation with Fast Convolution methods.