장지훈, 홍석희, 서석충, 김수리, 이명훈,

Vol. 34, No. 5, pp. 841-853, 10월. 2024
10.13089/JKIISC.2024.34.5.841, Full Text:
Keywords: PQC, Finite Field Multiplication, AVX2, Karatsuba, Toom-Cook
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.

Statistics
Cite this article