Earticle

초록

한국어

양자 컴퓨팅 발전에 따른 Shor 알고리즘 및 Grover 알고리즘의 등장으로 인해 기존 공개키암호 알고리즘이 위협받 고 있다. 이에 따라 미국 국립표준기술연구소에서는 양자내성암호 표준화 공모전을 통하여, 양자 컴퓨팅 발전으로 인한 보안 위협에 대비하고 있다. 표준화 공모전을 통해 선정된 4종의 표준화 대상 양자내성암호들은 보안성 및 민 첩성 측면에서 각기 다양한 방식으로 연구되고 있으며, 이 중 격자 기반의 전자서명 알고리즘인 CRYSTALSDilithium은 다항식 곱셈을 위하여 NTT 연산을 이용하고 있으나, 최근 희소 다항식 곱셈을 적용하여 알고리즘 성 능을 향상시킬 수 있다는 연구 결과가 발표된 바 있다. 해당 논문에서는 Cortex-M4, Apple M2 기반 실험 환경을 구축하여 검증을 진행했으나, 다른 ARM 계열 CPU 환경에서도 속도를 향상시킬 수 있는지에 대한 성능 검증은 이 루어지지 않았다. 이에, 본 논문에서는 다른 ARM 계열 CPU 환경에서도 희소 다항식 곱셈을 적용할 경우에 대한 CRYSTALS-Dilithium의 성능을 검증하고자 Dilithium2, Dilithium3, Dilithium5 알고리즘 각각에 대해 세 가지 코드(레퍼런스 코드, 희소 다항식 곱셈 알고리즘, SIMD를 적용한 희소 다항식 곱셈 알고리즘)를 구현하고 이 에 대한 성능을 검증하였다.

영어

The emergence of Shor and Grover algorithms following the development of quantum computing is threatening existing public key encryption algorithms. As a result, the National Institute of Standards and Technology (NIST) is preparing for security threats caused by the development of quantum computing through a competition for standardization of post quantum cryptography. The four types of standardized post quantum cryptography. selected through the standardization contest are being studied in various ways in terms of security and agility, and CRYSTALS-Dilithium, a grid- based digital signature algorithm, uses NTT operation for polynomial multiplication, but recently a research result has been published that shows that algorithm performance can be improved by applying sparse polynomial multiplication [8]. In this paper, Cortex-M4 and Apple M2 based experimental environments were built and verified, but performance verification has not been made on whether speed can be improved in other ARM-based CPU environments. Therefore, in this paper, three codes (reference code, sparse polynomial multiplication algorithm, and sparse polynomial multiplication algorithm with SIMD) were implemented and their performance was verified for each of the Dilithium2, Dilithium3, and Dilithium5 algorithms to verify the performance of CRYSTALSDilithium when applying sparse polynomial multiplication in other ARM-based CPU environments.

목차

요약
Abstract
1. 서론
2. 배경
2.1 기호 정의
2.2 Dilithium 구조
3. 희소 다항식 곱셈 알고리즘
3.1 Dilithium 내 희소 다항식의 특징
3.2 희소 다항식 변환
3.3 희소 다항식 곱셈 알고리즘 구현
4. 희소 다항식 곱셈과 SIMD 기법을 통한 Dilithium 최적화
4.1 Dilithium 내 희소 다항식 곱셈 알고리즘 적용
4.2 SIMD 기법을 활용한 희소 다항식 곱셈 알고리즘 최적화
5. 실험 결과
5.1 실험 환경
5.2 실험 결과
5.3 결과 분석
6. 결론
Acknowledgement
참고문헌

저자

• 윤성우 [ Sungwoo Yun | 가천대학교 ]
• 박지민 [ Jimin Park | 가천대학교 ]
• 목정현 [ Junghyun Mok | 가천대학교 ]
• 이석준 [ Sokjoon Lee | 가천대학교 ]

참고문헌