Three-level 하이브리드 몽고메리 감산을 통한 ARM Cortex-M7에서의 CSIDH-512 최적화
Optimized Implementation of CSIDH-512 through Three-Level Hybrid Montgomery Reduction on ARM Cortex-M7
0
조회
0
다운로드
0
인용
0
참고문헌
키워드
초록
NIST PQC 표준화 작업 Round 4에 올라 있던 유일한 아이소제니 기반 KEM 알고리즘인 SIKE에 대한 효율적인 키 복구 공격이 발표됨에 따라, 이를 대체할 수 있는 키 교환 알고리즘인 CSIDH가 다시 주목받고 있다. CSIDH는 현재까지 알려진 공격에 안전한 아이소제니 기반 키 교환 알고리즘으로, CRS 스킴을 현대화하여 효율적인 NIKE를 제공한다. 본 논문에서는 CSIDH-512를 ARM Cortex-M7에서 구현하고 three-level 하이브리드 몽고메리 감산을 적용하여 최적화한 성능을 측정한 뒤 그 결과 및 한계에 대해 서술하고 향후 연구 방향을 제시한다. 이는 기존에 제시되지 않았던 32-bit 임베디드 기기에서의 CSIDH 구현으로, 향후 다양한 임베디드 환경에서 CSIDH 및 파생 암호 알고리즘을 구현하는데 본 논문의 결과를 이용할 수 있을 것으로 기대한다.
Abstract
As an efficient key recovery attack on SIDH/SIKE was proposed, CSIDH is drawing attention again. CSIDH is an isogeny-based key exchange algorithm that is safe against known attacks to date, and provide efficient NIKE by modernizing CRS scheme. In this paper, we firstly present the optimized implementation of CSIDH-512 on ARM Cortex-M7. We use three-level hybrid Montgomery reduction and present the results of our implementation, limitations, and future research directions. This is a CSIDH implementation in 32-bit embedded devices that has not been previously presented, and it is expected that the results of this paper will be available to implement CSIDH and derived cryptographic algorithms in various embedded environments in the future.
참고문헌 (9)
- P. W. Shor, "Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer", SIAM Journal Computing, 26(5), pp.1484~1509 (1997)
- R. Azarderakhsh, "Supersingular isogeny key encapsulation", the NIST post-quantum standardiz-ation project, ~ (2017)
- An efficient key recovery attack on SIDH(preliminary version), "W. Castryck", ~, pp.IACR ePrint 2022-975 (2022)
- W. Castryck, "CSIDH : an efficient post-quantum commutative group action", Advances in Cryptology –ASIACRYPT 2018, ASIACRYPT 2018, pp.395~427 (2018)
- Hard homogeneous spaces, "J. M. Couveignes", ~, pp.IACR ePrint 2006-291 (2006)
- A. Stolbunov, "Constructing public-key cryptographic schemes based on class group action on a set of isogenous elliptic curves", Advances in Mathematics of Communications, 4(2), pp.215~235 (2010)
- P. L. Montgomery, "Modular multiplication without trial division", Mathematics of computation, 44(170), pp.519~521 (1985)
- H. Seo, "Hybrid Montgomery reduction", ACM Transactions on Embedded Computing Systems, 15(3), pp.1~13 (2016)
- A. A. Karatsuba, "Multiplication of many-digital numbers by automatic computers", Doklady Akademii Nauk, 145(2), pp.293~294 (1962)