Cortex-M7에서의 Falcon 키 생성 및 서명 생성 최적화
Optimizing Falcon Key Generation and Sign Algorithm on Cortex-M7
박현주(고려대학교); 이명훈(고려대학교); 장지훈(고려대학교); 김수리(성신여자대학교); 홍석희(컨텍)
35권 6호, 1285~1295쪽
초록
본 논문에서는 NIST PQC 표준으로 선정된 격자 기반 전자 서명 알고리즘 Falcon에 대해 Cortex-M7에서 키 생성 및 서명 생성 단계의 최적화 방안을 제안한다. Falcon의 키 생성 과정에서는 NTRUSolve 알고리즘을 이용하여 NTRU 방정식을 만족하는 를 구하고 Reduce 알고리즘을 통해 그 크기를 줄인다. 서명 생성 과정에서는 이산 가우시안 분포를 기반으로 타겟 벡터에 가까운 격자점을 선택하기 위해 ffSampling 알고리즘을 사용한다. 본 연구에서는 Cortex-M7에서 NTRUSolve와 ffSampling 알고리즘을 최적화하는 방안을 제안한다. 구체적으로, Cortex-M7에서 Thomas Pornin(2025)이 제안한 Reduce 방식의 성능을 비교하고 고정소수점과 부동소수점 표현 방식에 따른 성능 차이를 분석하였다. 또한, 서명 생성 단계의 ffSampling에서 기존의 재귀 기반 구조를 분석하여 저차원 샘플링 단계에서 재귀 구조를 제거하고 알고리즘을 비재귀적으로 전개함으로써 개선하였다. 제안 기법을 Falcon에 적용한 결과, Cortex-M7에서 Falcon-512의 키 생성 단계에서 약 12.65%의 성능 향상을 보였으며, 서명 생성 단계에서도 Falcon-512와 Falcon-1024에서 각각 약 2.37%, 2.48%의 성능 개선이 나타났다.
Abstract
In this paper, we propose an optimization method for key and signature generation on the Cortex-M7 for Falcon, a lattice-based digital signature algorithm selected as the NIST PQC standard. During key generation, Falcon uses NTRUSolve to obtain F and G that satisfy the NTRU equation, then reduces their size using Reduce. During signature generation, ffSampling is used to select lattice points close to the target vector based on a discrete Gaussian distribution. In this study, we propose an optimization method for NTRUSolve and ffSampling on the Cortex-M7. Specifically, we compare the performance of the Reduce method proposed by Thomas Pornin (2025) and analyze the performance differences between fixed point and floating point representations. Furthermore, we analyze the existing recursive structure in ffSampling during the signature generation. By eliminating the recursive structure in the low-dimensional sampling step and implementing the algorithm non-recursively, we improve efficiency. Applied to Falcon, a performance improvement of approximately 12.65% was observed in the key generation step of Falcon-512. In addition, the performance was improved by about 2.37% and 2.48% in the signature generation of Falcon-512 and Falcon-1024, respectively.
- 발행기관:
- 한국정보보호학회
- 분류:
- 컴퓨터학