CSIDH 성능 향상을 위한 Radical Isogeny 적용 분석
On the Use of Radical Isogenies for CSIDH Implementation
0
조회
0
다운로드
0
인용
0
참고문헌
키워드
초록
CSIDH 기반 암호를 구현하는 데 있어서 가장 큰 단점은 Velu 공식을 활용하여 isogeny를 연산하기 위해 작은 소수 위수를 가지는 커널의 생성점을 선택하는 부분이다. 이 과정은 작은 위수의 경우 실패확률이 크기 때문에 연산량이 많이 들어서, 최근에 radical isogeny를 사용하는 부분에 관한 연구가 진행되었다. 본 논문에서는 CSIDH 기반 암호 구현에 있어서 radical isogeny를 사용하는 최적 방안에 대해 제시한다. 본 논문에서는 Montgomery 곡선과 Tate 곡선 사이의 변환을 최적하였으며, 2-, 3-, 5-, 7-isogeny에 대한 공식을 최적화하였다. 본 논문의 결과, CSIDH-512의 경우 radical isogeny를 7차까지 사용할 경우 기존 constant-time CSIDH에 비해서 15.3% 빠른 결과를 얻을 수 있었다. CSIDH-4096의 경우 radical isogeny를 2차까지 사용하는 것이 최적이라는 결론을 얻을 수 있었다.
Abstract
The main obstacle for implementing CSIDH-based cryptography is that it requires generating a kernel of a small prime order to compute the group action using Velu's formula. As this is a quite painstaking process for small torsion points, a new approach called radical isogeny is recently proposed to compute chains of isogenies from a coefficient of an elliptic curve. This paper presents an optimized implementation of radical isogenies and analyzes its ideal use in CSIDH-based cryptography. We tailor the formula for transforming Montgomery curves and Tate normal form and further optimized the radical 2- and 3- isogeny formula and a projective version of radical 5- and 7- isogeny. For CSIDH-512, using radical isogeny of degree up to 7 is 15.3% faster than standard constant-time CSIDH. For CSIDH-4096, using only radical 2-isogeny is the optimal choice.
참고문헌 (28)
- J. J. Chi-Domiguez, "On new Velu’s formulae and their applications to CSIDH and BSIDH constant-time implementations", IACR Cryptology ePrint Archive, 2020 : 1109, ~ (2020)
- D. Bernstein, "Faster computation of isogenies of large prime degree", IACR Cryptology ePrint Archive, 2020:341, ~ (2020)
- W. Beullens, "CSI-FiSh: efficient isogeny based signatures through class group computations", LNCS, 11921, pp.227~247 (2019)
- W. Castryck, "CSIDH on the surface", LNCS, 12100, pp.111~129 (2020)
- W. Castryck, "CSIDH: An efficient post-quantum commutaitve group action", LNCS, 11274, pp.395~427 (2018)
- D. Cervantes-Vazquez, "Stronger and faster side-channel protections for CSIDH", LNCS, 11774, pp.173~193 (2019)
- A. Childs, "Constructing elliptic curve isogenies in quantum subexponential time", Journal of Mathematical Cryptology, 8(1), pp.1~29 (2014)
- C. Costello, "B-SIDH supersingular isogeny Diffie-Hellman using twisted torsion", LNCS, 12492, pp.440~463 (2020)
- C. Costello, "A simple and compact algorithm for SIDH with arbitrary degree isogenies", LNCS, 10625, pp.303~329 (2017)
- J.M. Couveignes, "Hard homogenous spaces", IACR Cryptology ePrint Archive, 2006:291, ~ (2006)
- De Feo, "Towards practical key exchange from ordinary isogeny graphs", LNCS, 11274, pp.365~394 (2018)
- D. Heo, "On the performance analysis for CSIDH-based cryptosystems", Applied Sciences, 10(19) (2020)
- D. Heo, "Optimized CSIDH implementation using a 2-torsion point", Cryptography, 4(3) (2020)
- A. Jalali, "Towards optimized and constant-time CSIDH on embedded devices", International Workshop on Constructive Side-Channel Analysis and Secure Design, pp.215~231 (2019)
- D. Jao, "Towards quantum-resistant cryptosystems from supersingular elliptic curve isogenies", LNCS, 7071, pp.19~34 (2011)
- T. Kawashima, "An efficient authenticated key exchange from random self-reducibility on CSIDH", IACR Cryptology ePrint Archive, 2020:1178, ~ (2020)
- S. Kim, "New hybrid method for isogeny-based cryptosystems using Edwards curves", IEEE transactions on Information Theory, 66(3), pp.1934~1943 (2020)
- M. Meyer, "On lions and elligators: An efficient constant-time implementations of CSIDH", LNCS, 11505, pp.307~325 (2019)
- M. Meyer, "A faster way to the CSIDH", LNCS, 11356, pp.137~152 (2018)
- M. M, "On hybrid SIDH schemes using Edwards and Montgomery curve arithmetic", IACR Cryptology ePrint Archive, 2017:1213, ~ (2017)
- D. Moody, "Analogues of Velu’s formula for isogenies on alternate models of elliptic curves", Mathematics of Computations, 85(300), pp.1929~1951 (2016)
- H. Onuki, "A constant-time algorithm of CSIDH keeping two points", IEICE Transactions on Fundamentals of Electronics, Communications, and Computer Sciences, E103(10), pp.1174~1182 (2020)
- A. Stolbunov, "Constructing public-key cryptographic schemes based on class group action on a set of isogenous ellitpic curves", Advances in Mathematics of Communication, 4(2), pp.215~235 (2010)
- W. Casrtyck, "Radical isogenies", LNCS, 12492, pp.440~463 (2020)
- J.J. Chi-Domiguez, "Fully projective radical isogenies in constant-time", IACR Cryptology ePrint Archive, 2021:259, ~ (2021)
- 김수리, "CSIDH 기반 암호에 대한 뒤틀린 몽고메리 곡선 사용", 정보보호학회논문지, 31(3), pp.497~508 (2021), 한국정보보호학회[DOI]
- H. Onuki, "Radical isogenies on Montgomery curves", IACR Cryptology ePrint Archive, 2021:699, ~ (2021)
- J.J. Chi-Domiguez, "The SQALE of CSIDH: Square-root Velu quantum-resistant isogeny action with low exponents", IACR Cryptology ePrint Archive, 2020:1520, ~ (2020)