AVX2 환경에서 HQC의 GF(2)[x] 곱셈 최적화
Optimized Implementation of GF(2)[x] Multiplication for HQC on AVX2
0
조회
0
다운로드
0
인용
0
참고문헌
키워드
초록
본 논문에서는 AVX2 환경에서 HQC 내 곱셈 연산의 최적화 방안을 제안한다. HQC는 NIST PQC 공모전 round 4의 후보 알고리즘 중 하나로, 이진 코드 기반의 키 교환 알고리즘이다. 곱셈 연산은 HQC의 내부 연산 중 시간복잡도가 높은 연산 중 하나로, AVX2 환경에서 전체 클럭 사이클의 약 30%를 차지한다. 곱셈의 최적화를 위해 카라추바, 툼-쿡 알고리즘을 사용하였다. 두 알고리즘 모두 분할 정복 방식으로, 그 내부에서 더 작은 차수의 곱셈 연산이 필요하다. 본 논문에서는 가장 효율적인 카라추바, 툼-쿡 알고리즘의 조합을 찾아 HQC 다항식 곱셈을 최적화하는 방법을 제안하고, 기존 구현물과의 성능을 비교한다. 비교 결과 hqc-128, -192, -256의 곱셈에서 기존 대비 4.5%, 2.5%, 30.3%의 성능 향상을 보인다. 이를 키 생성, 캡슐화, 디캡슐화에 적용하였을 때, 기존 대비 hqc-128에서 각각 2.2%, 2.4%, 2.3%, hqc-192에서 각각 1.6%, 4.2%, 2.6%, hqc-256에서 각각 13.3%, 14.7%, 13.3%의 성능 향상을 보인다.
Abstract
This paper proposes an optimization method for the multiplication operation in HQC on AVX2. HQC is a candidate in NIST PQC standardization round 4 and is a binary code-based key exchange algorithm. The multiplication operation is one of the most time-complex operations in HQC, accounting for about 30% of the total clock cycles in the AVX2 environment. For the optimization, we used Karatsuba and Toom-Cook algorithms. Both algorithms are based on divide-and-conquer methods, which require multiplications of smaller order within them. We propose a method to optimize polynomial multiplication in HQC by finding the most efficient combination of Karatsuba and Toom-Cook algorithms, and compare the performance of the proposed method based on the implementation submitted to the PQC standardization. The results of the comparison demonstrate a performance improvement of 4.5%, 2.5%, and 30.3% over the multiplications of original hqc-128, -192, and -256. When applied to key generation, encapsulation, and decapsulation, the performance improvement over the original HQC is 2.2%, 2.4%, and 2.3% for hqc-128, 1.6%, 4.2%, and 2.6% for hqc-192, and 13.3%, 14.7%, and 13.3% for hqc-256, respectively.
참고문헌 (9)
- Melchor, Carlos Aguilar, "Hamming quasi-cyclic (HQC)", NIST PQC submissions, Round 4, ~ (2024)
- A. Karatsuba, "Multiplication of multidigit numbers on automata", Soviet physics doklady, 7, pp.595~596 (1963)
- A. L. Toom, "The complexity of a scheme of functional elements realizing the multiplication of integers", Soviet Mathematics Doklady, 4(3), pp.714~716 (1963)
- S. A. Cook, "On the minimum computation time of functions", Transactions of the American Mathematical Society, 142, pp.291~314 (1969)
- Gao, Shuhong, "Additive fast Fourier transforms over finite fields", IEEE Transactions on Information Theory, 56(12), pp.6265~6272 (2010)
- R. Avanzi, "Crystals-kyber algorithm specifications and supporting documentation", NIST PQC submissions, Round 3, ~ (2021)
- L. Ducas, "Crystals-Dilithium algorithm specifications and supporting documentation", NIST PQC submissions, Round 3, ~ (2020)
- using avx512instruction set and vpclmulqdq instruction, "Journal of Cryptographic Engineering", 2023, 37~55
- "Proceedings of the ANTS-VIII 2008", 2008, 153~166