terSIDH의 성능 분석 및 상수 시간 구현
Performance Analysis and Constant-Time Implementation of terSIDH
0
조회
0
다운로드
0
인용
0
참고문헌
키워드
초록
2022년 CD-MM-R 공격을 통해 SIDH의 취약성이 드러난 이후, 이에 대응하기 위한 다양한 아이소제니 기반 암호 기법들이 등장하였다. 그중 Basso와 Fouotsa가 제안한 binSIDH와 terSIDH는 새로운 비밀키 형태를 도입하여 적절한 파라미터 크기와 실행 속도를 제공한다. terSIDH는 다른 아이소제니 기반 암호 기법들과 비교해도 속도 경쟁력을 가진다. 그러나 기존 terSIDH의 구현물은 아이소제니의 차수에 따른 계산량 차이로 인해 실행 시간의 변동성이 발생하는 문제를 가졌다. 이에 본 연구에서는 더미 연산을 도입하여 모든 개인키에 대해 상수 시간 구현을 가능하게 하는 알고리즘을 제안한다. 기존 구현에서는 개인키에 따라 소요 시간이 최소 120.1ms, 최대 4064.4ms 걸릴 만큼 차이가 심했으나, 본 연구에서는 이 범위의 크기를 6.6ms로 줄이는 데 성공하였다.
Abstract
After the vulnerability of SIDH was revealed by the CD-MM-R attack in 2022, various isogeny-based cryptographic schemes have emerged as countermeasures. Among them, binSIDH and terSIDH, developed by Basso and Fououtsa, provide appropriate parameter sizes and execution speeds with new forms of secret keys. terSIDH demonstrates competitive speed compared to other isogeny-based cryptographic schemes. However, the existing implementation of terSIDH faces an issue of execution time variability due to the difference in computational load based on the degree of the isogeny. In this study, we propose an algorithm that enables constant-time implementation across all secret keys by introducing dummy operations. In our approach, the execution time varied significantly depending on the private key, ranging from a minimum of 120.1ms to a maximum of 4064.4ms. However, in this study, we successfully reduced this variation to within 6.6ms.
참고문헌 (8)
- Azarderakhsh, Reza, "Supersingular Isogeny Key Encapsulation, NIST Post-Quant um Cryptography Standardization Pro ject", ~ (2017)
- L, De Feo, "Towards quantum-resistant cryptosyst ems from supersingular elliptic curve isogenies", Journal of Mathematical C ryptology, 8(3), pp.209~247 (2014)
- W, Castryck, "An efficien t key recovery attack on SIDH", Ad vances in Cryptology – EUROCRYPT 2023, pp.423~447 (2023), Springer Nature Switzerland
- A, Basso, "New SID H countermeasures for a more efficien t key exchange", Advances in Crypt ology – ASIACRYPT 2023, pp.208~233 (2023), Springer Nature Singapore
- C, Costello, "A simple an d compact algorithm for SIDH with ar bitrary degree isogenies", Advances in Cryptology – ASIACRYPT 2017, pp.303~329 (2017), Springer International Publishing
- An att ack on SIDH with arbitrary starting curve, "L. Maino", Cryptology ePrint Archive, ~, pp.Rep ort 2022 (2022), 1026
- D. Robert, "Breaking SIDH in polyno mial time", Advances in Cryptology– EUROCRYPT 2023, pp.472~503 (2023), Springer Nature Switzerland
- J. Vélu, "Isogénies entre courbes ellipt iques", C. R. Acad. Sci. Paris Sér. AB, 273, pp.A238~A241 (1971)