AVX2 환경에서 HQC의 GF(2)[x] 곱셈 최적화 (Optimized Implementation of GF(2)[x] Multiplication for HQC on AVX2)

서지정보

· 발행기관 : 한국정보보호학회
· 수록지 정보 : 정보보호학회논문지 / 34권 / 5호 / 841 ~ 853페이지
· 저자명 : 장지훈, 이명훈, 김수리, 서석충, 홍석희

초록

본 논문에서는 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%의 성능 향상을 보인다.

영어초록

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.

참고자료

· 없음