[논문]CSIDH 기반 암호에 대한 뒤틀린 몽고메리 곡선 사용

김수리

doi:10.13089/jkiisc.2021.31.3.497

[국내논문] CSIDH 기반 암호에 대한 뒤틀린 몽고메리 곡선 사용
On the Use of Twisted Montgomery Curves for CSIDH-Based Cryptography 원문보기

情報保護學會論文誌 = Journal of the Korea Institute of Information Security and Cryptology, v.31 no.3, 2021년, pp.497 - 508

김수리 (성신여자대학교)

초록
AI-Helper

본 논문에서는 뒤틀린 몽고메리 곡선을 사용하는 대표적인 암호인 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 ▼ AI-Helper

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.

Keyword

표/그림 (8)

표 Table 1. Computational cost of lower-level functions on Montgomery⁺ curves and Montgomery^- curves
표 Table 2. Computational cost of biquardatic polynomials
그림 Fig. 1. Method of computing consecutive 2-isogenies on $M^-_a$
표 Table 3. Private key exponent range and its securfity
표 Table 4. Performance result of group action of CSURF when various parameter is used
표 Table 5. Performance result of group action of CSURF and sqrt-CSURF
표 Table 6. Performance result of group action when the square-root Velu for mula is used forCSIDH and CSURF
표 Table 7. Performance result of constant-time group action

참고문헌 (23)

J.J. Chi-Domiguez et al. "On new Velu's formulae and their applications to CSIDH and BSIDH constant-time implementations," IACR Cryptology ePrint Archive, 2020:1109, 2020
D. Bernstein et al. "Faster computation of isogenies of large prime degree," IACR Cryptology ePrint Archive, 2020:341, 2020
W. Beullens et al. "CSI-FiSh: efficient isogeny based signatures through class group computations," ASIACRYPT, LNCS 11921, pp. 227-247, Dec. 2019
W. Castryck and T. Decru "CSIDH on the surface," PQCrypto, LNCS 12100, pp.111-129, April, 2020
W. Castryck et al. "CSIDH: An efficient post-quantum commutaitve group action," ASIACRYPT, LNCS 11274, Dec. 2018
D. Cervantes-Vazquez et al. "Stronger and faster side-channel protections for CSIDH," LATINCRYPT, LNCS 11774, Sept. 2019
A. Childs et al. "Constructing elliptic curve isogenies in quantum sub-exponential time," Journal of Mathematical Cryptology, vol. 8, no. 1, pp. 1-29, 2014

상세보기
C. Costello, "B-SIDH supersingular isogeny Diffie-Hellman using twisted torsion," ASIACRYPT, LNCS 12492, pp. 440-463, Dec. 2020
C. Costello and H. Hisil, "A simple and compact algorithm for SIDH with arbitrary degree isogenies," ASIACRYPT, LNCS 10625, pp. 303-329, Dec. 2017
J.M. Couveignes, "Hard homogenous spaces," IACR Cryptology ePrint Archive, 2006:291, 2006
De Feo. et al. "Towards practical key exchange from ordinary isogeny graphs," ASIACRYPT, LNCS 11274, Dec. 2018
D. Heo et al. "On the performance analysis for CSIDH-based cryptosystems," Applied Sciences, vol. 10, no. 19, 2020
D. Heo et al. "Optimized CSIDH implementation using a 2-torsion point," Cryptography, vol. 4, no. 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, L. De Feo "Towards quantum-resistant cryptosystems from super-singular elliptic curve isogenies," PQCrypto, LNCS 7071, pp. 19-34, Aug. 2011
T. Kawashima, "An efficient authenticated key exchange from random self-reducibility on CSIDH," IACR Cryptology ePrint Archive, 2020:1178, 2020
S. Kim et al. "New hybrid method for isogeny-based cryptosystems using Edwards curves," IEEE transactions on Information Theory, vol. 66, no. 3, pp. 1934-1943, 2020

상세보기
M. Meyer et al. "On lions and elligators: An efficient constant-time implementations of CSIDH", PQCrypto, LNCS 11505, pp. 307-325, 2019
M. Meyer and S. Reith "A faster way to the CSIDH," INDOCRYPT, LNCS 11356, pp. 137-152, 2018
M. Meyer et al. "On hybrid SIDH schemes using Edwards and Montgomery curve arithmetic," IACR Cryptology ePrint Archive, 2017:1213, 2017
D. Moody and D. Shumow, "Analogues of Velu's formula for isogenies on alternate models of elliptic curves," Mathematics of Computations, vol. 85, no. 300, pp. 1929-1951, 2016
H. Onuki et al. "A constant-time algorithm of CSIDH keeping two points," IEICE Transactions on Fundamentals of Electronics, Communications, and Computer Sciences, vol. E103.A, no. 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, vol. 4, no. 2, pp. 215-235, 2010

내보내기 구분	파일저장 인쇄 메일전송
구성항목	기본정보 상세정보 관리번호, 논문명, 저널/프로시딩명, 저자 , 발행년, 권, 호, 시작페이지, 끝페이지, 발행기관 관리번호, 논문명, 대등논문명, 저자 , 저널/프로시딩명, 발행기관, 발행년, 발행언어, 권, 호, 시작페이지, 끝페이지, ISBN, ISSN, 주제분야, 키워드, 초록(한글), 초록(영문), 저자(소속기관)
저장형식	Text(ASCII format) Excel format RefWorks Direct Export RIS format (for Reference Manager, ProCite, EndNote), Scholar's Aids, Mendeley
메일정보	받는사람 (필수) @ 보내는사람 (선택) @ 제목 내용 KISTI 검색결과 이메일 서비스
안내	총 건의 자료가 검색되었습니다. 다운받으실 자료의 인덱스를 입력하세요. (1-10,000) 검색결과의 순서대로 최대 10,000건 까지 다운로드가 가능합니다. 데이타가 많을 경우 속도가 느려질 수 있습니다.(최대 2~3분 소요) 다운로드 파일은 UTF-8 형태로 저장됩니다. 파일의 내용이 제대로 보이지 않을실 때는 웹브라우저 상단의 보기 -> 인코딩 -> 자동선택 여부를 확인하십시오. ~ Text(ASCII format) Excel format

연합인증