SIMD 명령어 집합을 이용한 KpqC 양자내성암호 고속화 연구 = Accelerating KpqC Post-Quantum Cryptography Using SIMD Instruction Sets

국문 초록 (Abstract)

본 연구는 KpqC 알고리즘 중 NTT-unfriendly 링을 사용하는 두 격자기반암호 알고리즘, SMAUG-T와 NCC-Sign Non-Cyclotomic을 대상으로 SIMD 명령어 집합을 지원하는 AVX2에서 NTT 기반 다항식 곱셈을 이용한 최적화를 제안한다. 격자기반암호 알고리즘의 핵심 연산인 다항식 곱셈을 수행하는 데 있어 NTT가 가장 효과적으로 알려져 있는 만큼, CRYSTALS-Kyber, CRYSTALS-Dilithium뿐만 아니라 국내 KpqC 격자기반암호 알고리즘 중 HAETAE, NTRU+ 또한 NTT 기반 다항식 곱셈을 채택하고 있다. 반면 Non-Cyclotomic 다항식 링을 사용하는 NCC-Sign Non-Cyclotomic과 Cyclotomic 다항식 링을 사용하나, NTT/iNTT 변환에 필요한 에서 primitive -th root of unity가 존재하지 않는 SMAUG-T 두 알고리즘 모두 NTT 기반 다항식 곱셈을 수행할 수 없다. 기존 연구에서는 NTT-unfriendly 링을 사용하는 Saber에서 NTT-friendly 링 동형 사상을 통해 NTT 기반 다항식 곱셈을 수행하였으며, NTT 기반 다항식 곱셈이 기존의 Toom-Cook 기반 다항식 곱셈보다 우수한 성능을 보임을 확인하였다. SMAUG-T의 경우 기존 연구에서도 AVX2에서 Saber의 NTT-friendly 링 동형 사상을 적용한 NTT 기반 다항식 곱셈을 수행하였다. 그러나 해당 동형 사상은 SMAUG-T에 대하여 최적은 아니다. 본 연구에서는 Saber에서의 NTT-friendly 링 동형 사상을 정의하는 접근 방식을 바탕으로, AVX2에서 NCC-Sign Non-Cyclotomic과 SMAUG-T를 위한 최적의 NTT-friendly 링 동형 사상을 설계하고, 이를 통해 NTT 기반 다항식 곱셈을 수행하였다. 결과적으로 AVX2에서 기존 SMAUG-T의 NTT 기반 다항식 곱셈 대비 최대 14.2%의 성능 향상을 달성하였으며, NCC-Sign Non-Cyclotomic에서의 NTT 기반 다항식 곱셈은 기존 Reference C(x86/64) 대비 4381.1% 성능 향상을 달성하였다. 이와 더불어 우리가 아는 한, NCC-Sign Non-Cyclotomic에 대한 AVX2 최초 구현을 제시한다.

다국어 초록 (Multilingual Abstract)

This work proposes an optimization based on NTT-based polynomial multiplication on AVX2, which supports SIMD instruction sets, targeting two lattice-based cryptographic algorithms in KpqC that use NTT-unfriendly rings, namely SMAUG-T and NCC-Sign Non-Cyclotomic. Since NTT is widely known to be the most effective method for performing polynomial multiplication, which is the core operation of lattice-based cryptographic algorithms, not only CRYSTALS-Kyber and CRYSTALS-Dilithium but also domestic KpqC lattice-based cryptographic algorithms such as HAETAE and NTRU+ adopt NTT-based polynomial multiplication. In contrast, both NCC-Sign Non-Cyclotomic, which uses a Non-Cyclotomic polynomial ring, and SMAUG-T, which uses a cyclotomic polynomial ring but does not admit the existence of a primitive k-th root of unity required for NTT/iNTT, cannot perform NTT-based polynomial multiplication. In prior work, NTT-based polynomial multiplication was performed for Saber, which uses an NTT-unfriendly ring, through an NTT-friendly ring isomorphism, and it was shown that NTT-based polynomial multiplication achieves better performance than conventional Toom-Cook-based polynomial multiplication. For SMAUG-T, previous work also applied the NTT-friendly ring isomorphism used in Saber to perform NTT-based polynomial multiplication on AVX2. However, this isomorphism is not optimal for SMAUG-T. In this work, based on the approach used to define the NTT-friendly ring isomorphism for Saber, we design optimal NTT-friendly ring isomorphisms for NCC-Sign Non-Cyclotomic and SMAUG-T on AVX2, and perform NTT-based polynomial multiplication accordingly.
As a result, we achieve up to 14.2% performance improvement over the existing NTT-based polynomial multiplication for SMAUG-T on AVX2, and the NTT-based polynomial multiplication for NCC-Sign Non-Cyclotomic achieves a 4381.1% performance improvement compared to the reference C (x86/64) implementation. In addition, to the best of our knowledge, we present the first AVX2 implementation of NCC-Sign Non-Cyclotomic.

목차 (Table of Contents)

• 제 1 장 Introduction 1
• 제 2 장 Preliminaries 3
• 제 1 절 SMAUG-T 3
• 제 2 절 NCC-Sign Non-Cyclotomic 5
• 제 3 절 Polynomial Multiplication Algorithms 7
• 2.3.1. School-Book 7
• 2.3.2. Toom-Cook 7
• 2.3.3. Number Theoretic Transform 9
• 제 4 절 Complete and Incomplete NTT 14
• 제 5 절 NTT-unfriendly Ring 15
• 2.5.1. Non-Cyclotomic Polynomial Modulus 15
• 2.5.2. Absence of Required Primitive Roots of Unity 16
• 제 6 절 Advanced Vector Extensions 2 (AVX2) 17
• 제 3 장 NTT Optimization Techniques on AVX2 18
• 제 1 절 Montgomery Arithmetic 18
• 3.1.1. Unsigned Montgomery reduction 18
• 3.1.2. Signed Montgomery multiplication 20
• 제 2 절 Lazy Reduction 24
• 제 3 절 Layer Merging 25
• 제 4 절 Shuffle 26
• 제 4 장 NTT-Based Polynomial Multiplication for SMAUG-T on AVX2 28
• 제 1 절 Large-Prime vs Multi-Moduli 28
• 제 2 절 Selection of Optimal Primes in Multi-Moduli 29
• 제 3 절 NTT Optimization Strategy for SMAUG-T 31
• 4.3.1. MT-Shuffle and Signed Montgomery multiplication 31
• 4.3.2. Layer Merging 31
• 4.3.3. Layer-Specific Simplification of CT butterfly 31
• 제 5 장 NTT-Based Polynomial Multiplication for NCC-Sign Non-Cyclotomic on AVX2 32
• 제 1 절 Multi-Moduli 32
• 5.1.1. Cyclotomic Ring Extension for Enabling the NTT 32
• 5.1.2. Selection of NTT-friendly Primes for Multi-Moduli 32
• 제 2 절 NTT Optimization Strategy for NCC-Sign Non-Cyclotomic 34
• 5.2.1. MT-Shuffle and Signed Montgomery multiplication 34
• 5.2.2. Layer-specific Simplification of CT butterfly 34
• 5.2.3. Layer Merging 34
• 제 6 장 Performance Analysis on AVX2 35
• 제 1 절 Performance of SMAUG-T 35
• 제 2 절 Performance of NCC-Sign Non-Cyclotomic 36
• 참조 논문 38
• Abstract (English) 41