KpqC 1 라운드 TiGER KEM의 Meet-LWE 공격에 대한 안전성 분석
Security Analysis on TiGER KEM in KpqC Round 1 Competition Using Meet-LWE Attack
0
조회
0
다운로드
0
인용
0
참고문헌
키워드
초록
최근 양자컴퓨터를 이용한 공격에 안전한 양자내성암호(Post-Quantum Cryptography, PQC)에 대한 연구 및 표준화가 국내외로 활발히 진행되고 있다. 2022년 국내 양자내성암호 표준화 공모인 KpqC 공모전이 시작되었고, 총 16종의 양자내성암호 표준 후보 알고리즘이 제출되어 1라운드 진행 중이다. 본 고에서는 KpqC 공모전 1라운드 후보인 격자 기반 키 캡슐화 알고리즘 TiGER에 대해 Alexander May의 Meet-LWE 공격을 적용하여 구체적인 공격 복잡도를 분석하였다. TiGER의 제안된 파라미터에 대해 Meet-LWE 공격을 적용한 계산 결과, 192-bit 양자 안전성을 목표로 제안된 TiGER192 파라미터가 실제로 170-bit의 classical 안전성을 가진다는 것을 보였다. 또한, 본 고에서는 Meet-LWE 공격에 대한 안전성을 높이기 위한 파라미터 설정 방법을 제언한다.
Abstract
Recently, Post-Quantum Cryptography (PQC), which is secure against attacks using quantum computers, has been actively studied. In 2022, the KpqC competition, a competition for domestic PQC standardization, was launched, and a total of 16 candidate algorithms were received, and the first round is underway. In this paper, we apply Alexander May's Meet-LWE attack to TiGER, a lattice-based key encapsulation mechanism that is a candidate for the first round of the KpqC competition, and analyze its concrete attack complexity. The computational results of applying the Meet-LWE attack to each of the proposed parameters of TiGER show that the proposed TiGER192 parameter, which targets 192-bit quantum security, actually achieves 170-bit classical security. In addition, we propose a parameter setting to increase the attack complexity against the Meet-LWE attack.
참고문헌 (14)
- P. W. Shor, "Algorithms for quantum computation : discrete logarithms and factoring", Proceedings 35th annual symposium on foundations of computer science, pp.124~134 (1994), IEEE
- J. Y. Park, "A survey of polynomial multiplication with RSA-ECC coprocessors and implementations of NIST PQC round3 kem algorithms in Exynos2100", IEEE Access, 10, pp.2546~2563 (2021)
- "KpqC Competition Algorithms" (2023)[URL]
- J. Buchmann, "On the hardness of LWE with binary error : Revisiting the hybrid lattice-reduction and meet-in-the-middle attack", International Conference on Cryptology in Africa (AFRICACRYPT 2016), LNCS, 9646, pp.24~43 (2016)
- V. Lyubashevsky, "On ideal lattices and learning with errors over rings", Advances in Cryptology, EUROCRYPT 2010: 29th Annual International Conference on the Theory and Applications of Cryptographic Techniques, LNCS, 6110, pp.1~23 (2010)
- F. Luo, "Fully homomorphic encryption based on the ring learning with rounding problem", IET Information Security, 13(6), pp.639~648 (2019)
- D. Hofheinz, "A modular analysis of the Fujisaki-Okamoto transformation", Theory of Cryptography Conference (TCC 2017), LNCS, 10677, pp.341~371 (2017)
- H. Baan, "Round5 : Compact and Fast Post-quantum Public-Key Encryption", -Quantum Cryptography (PQCrypto 2019), LNCS, 11505, pp.83~102 (2019)
- E. Alkim, "Post-quantum key Exchange—A new hope", 25th USENIX Security Symposium (USENIX Security 16), pp.327~343 (2016)
- A. May, "How to meet ternary LWE keys", Proceedings of the 2021 Advances in Cryptology-CRYPTO 2021, LNCS, 12826, pp.701~731 (2021)
- M. R. Albrecht, "On the concrete hardness of Learning with Errors", Journal of Mathematical Cryptology, 9(3), pp.169~203 (2015)
- K. Boudgoust, "On the hardness of module-LWE with binary secret", Cryptographers’ Track at the RSA Conference, pp.503~526 (2021)
- "KpqC Bulletin Board" (2023)[URL]
- S. Park, "TiGER : Tiny bandwidth key encapsulation mechanism for easy miGration based on RLWE(R)", IACR ePrint, 2022(1651) (2022)