M-SIDH 구현 및 성능 평가를 통한 효율성 연구
Implementing M-SIDH: Performance and Efficiency Evaluation
0
조회
0
다운로드
0
인용
0
참고문헌
키워드
초록
최근 Castryck-Decru에 의해 SIDH 기반 암호가 다항시간 안에 개인키를 복구할 수 있음에 따라 이에 대응하기 위한 여러 방법이 제안되었다. 이 중, Fouotsa 등이 제안한 M-SIDH는 상대방에게 전달하는 torsion point 정보를 마스킹하여 Castryck-Decru 공격에 대응한다. 본 논문에서는 처음으로 C를 이용해 M-SIDH를 구현하였으며, 최적화를 통해 효율성을 평가한다. 본 논문은 M-SIDH의 성능을 확인하기 위해 1024비트 소수를 사용하여 파라미터를 선택하는 방법을 제시하였으며, square-root Velu 공식의 확장체에서의 구현을 통해 M-SIDH를 최적화하였다. 본 논문의 결과 고전 64비트 보안강도를 가지는 MSIDH-1024의 경우 키 교환하는데 대략 1129ms 정도가 필요하다.
Abstract
Due to the recent attack by Castryck-Decru, the private key of SIDH can be recovered in polynomial time so several methods have been proposed to prevent the attack. Among them, M-SIDH proposed by Fouotsa et al, counteracts the attack by masking the torsion point information during the key exchange. In this paper, we implement M-SIDH and evaluate its performance. To the best of our knowledge, this is the first implementation of M-SIDH in C language. Toward that end, we propose a method to select parameters for M-SIDH instantiation and propose a 1024-bit prime for implementation. We implemented the square-root Velu formula over the extension field for further optimization. As a result, 1129 ms is required for a key exchange in the case of MSIDH-1024, providing the classic 64-bit security level.
참고문헌 (10)
- J. M. Couveignes, "Hard homogenous spaces", IACR Cryptology ePrint Archive, 2006, pp.291~ (2006)
- A. Childs, "Constructing elliptic curve isogenies in quantum subexponential time", Journal of Mathematical Cryptology, 8(1), pp.1~29 (2014)
- D. Jao, "Towards quantum-resistant cyprosystems from supersingular elliptic curve isogenies", PQCrypto, LNCS, 7071, pp.19~34 (2011)
- W. Castryck, "An efficient key recovery attack on SIDH", IACR Cryptology ePrint Archive, 2022, pp.975~ (2022)
- T. Fouotsa, "M-SIDH and MD-SIDH : countering SIDh attacks by masking information", Cryptology ePrint Archive, 2023, pp.013~ (2023)
- D. Kohel, "On the quarternion-isogeny path problem", LMS Journal of COmputation and Mathematics, pp.418~432 (2014)
- T. Fouotsa, "On the isogeny problem with torsion point information", PKC 2022, LNCS, 13177, pp.142~161 (2022)
- D. Bernstein, "Faster computation of isogenies of large prime degree", IACR Cryptology ePrint Archive, 2020, pp.341~ (2020)
- H. Onuki, "A constant-time algorithm of CSIDH keeping two points", IEICE Transanctions on Fundamentals of Electronics, Communications, and Computer Sciences, E103A(10), pp.1174~1182 (2020)
- J. Chaves-Saab, "The SQALE of CSIDH: sublinear Velu quantum-resistant isogeny action with low exponents", Journal of Cryptographic Engineering, 12(3), pp.349~368 (2022)