CSIDH 기반 암호에 대한 뒤틀린 몽고메리 곡선 사용
On the Use of Twisted Montgomery Curves for CSIDH-Based Cryptography
0
조회
0
다운로드
1
인용
0
참고문헌
키워드
초록
본 논문에서는 뒤틀린 몽고메리 곡선을 사용하는 대표적인 암호인 CSURF의 최적화 구현에 대해 분석한다. Projective 형태의 타원곡선 연산은 몽고메리 곡선보다 뒤틀린 몽고메리 곡선이 더 느려서, CSURF는 hybrid 형태의 CSIDH 보다 성능이 느리다. 하지만, square-root Velu 공식을 사용할 경우 타원곡선 연산량을 줄일 수 있으므로 최적화할 여지가 있다. 본 논문에서는 처음으로 뒤틀린 몽고메리 곡선에서의 square-root Velu 공식을 제안하고, 2-isogeny 공식을 최적화하였다. 본 논문의 결과, 제안하는 CSURF는 기존보다 23.3% 빠르고, CSIDH 보다는 10.8% 느리다. 또한, 제안하는 constant-time CSURF의 경우 constant-time CSIDH 보다 6.8% 느리다. 제안하는 결과 CSURF는 CSIDH 보다 느리지만, 기존 뒤틀린 몽고메리를 이용한 구현과 비교하면 상당한 향상으로, 향후 뒤틀린 몽고메리 곡선에 적합한 구현에 본 논문의 결과를 이용할 수 있을 것으로 전망한다.
Abstract
In this paper, we focus on optimizing the performance of CSURF, which uses the tweaked Montgomery curves. The projective version of elliptic curve arithmetic is slower on tweaked Montgomery curves than on Montgomery curves, so that CSURF is slower than the hybrid version of CSIDH. However, as the square-root Velu formula uses less number of ellitpic curve arithmetic than the standard Velu formula, there is room for optimization We optimize the square-root Velu formula and 2-isogeny formula on tweaked Montgomery curves. Our CSURFis 14% faster than the standard CSURF, and 10.8% slower than the CSIDH using the square-root Velu formula. The constant-time CSURF is 6.8% slower than constant-time CSIDH. Compared to the previous implementations, this is a remarkable result.
참고문헌 (23)
- 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), ASIACRYPT
- W. Castryck, "CSIDH on the surface", LNCS, 12100, pp.111~129 (2020)
- W. Castryck, "CSIDH: An efficient post-quantum commutaitve group action", LNCS, 11274 (2018), ASIACRYPT
- D. Cervantes-Vazquez, "Stronger and faster side-channel protections for CSIDH", LNCS, 11774 (2019), LATINCRYPT
- 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), ASIACRYPT
- C. Costello, "A simple and compact algorithm for SIDH with arbitrary degree isogenies", LNCS, 10625, pp.303~329 (2017), ASIACRYPT
- 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 (2018), ASIACRYPT
- 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), PQCrypto
- 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), PQCrypto
- M. Meyer, "A faster way to the CSIDH", LNCS, 11356, pp.137~152 (2018), INDOCRYPT
- M. Meyer, "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.A(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)