다변수 이차식 기반 서명 기법 Rainbow의 공격 기법 및 보안강도 분석
Analysis of Attacks and Security Level for Multivariate Quadratic Based Signature Scheme Rainbow
0
조회
0
다운로드
0
인용
0
참고문헌
키워드
초록
양자적 특성을 활용한 Shor 알고리즘은 인수분해 및 이산대수 문제를 효율적으로 풀 수 있다. 이로 인해 RSA, 타원곡선(ECC: Elliptic Curve Cryptography) 등 인수분해와 이산대수 문제의 어려움에 기반하고 있는 기존 공개키 암호 시스템이 위협받고 있다. 이에 미국 국립표준기술연구소(NIST)에서는 양자 컴퓨터의 강력한 연산 능력에도 안전한 새로운 공개키 암호 체계의 표준인 양자 내성 암호(PQC: Post Quantum Cryptography)를 선정하는 공모를 진행하고 있다. 양자 내성 암호 후보군 중 다변수 이차식 기반 서명 기법은 짧은 서명 길이와 빠른 서명 및 검증으로 인해 사물인터넷(IoT) 등 제한된 자원을 갖는 기기에 적합하다. 이에 본 논문에서는 다변수 이차식 기반 서명 중 유일하게 3 라운드까지 최종 선정된 Rainbow에 대한 클래식 공격 기법과 양자적 특성을 이용한 공격 기법들을 분석하고, 현재 3라운드에 제시된 레인보우 파라미터에 대한 공격 복잡도를 계산하여 양자 내성 암호 표준화 후보 알고리즘인 레인보우 서명기법이 제공하는 보안 강도를 분석한다.
Abstract
Using Shor algorithm, factoring and discrete logarithm problem can be solved effectively. The public key cryptography, such as RSA and ECC, based on factoring and discrete logarithm problem can be broken in polynomial time using Shor algorithm. NIST has been conducting a PQC(Post Quantum Cryptography) standardization process to select quantum-resistant public key cryptography. The multivariate quadratic based signature scheme, which is one of the PQC candidates, is suitable for IoT devices with limited resources due to its short signature and fast sign and verify process. We analyzes classic attacks and quantum attacks for Rainbow which is the only multivatiate quadratic based signature scheme to be finalized up to the round 3. Also we compute the attack complexity for the round 3 Rainbow parameters, and analyzes the security level of Rainbow, one of the PQC standardization candidates.
참고문헌 (21)
- R. Feynman, "Simulating physics with computers", International Journal of Theoretical Physics, 21, pp.467~488 (1982)
- F. Arute, "Quantum supremacy using a programmable superconducting processor", Nature, 574(779), pp.505~510 (2019)
- D. Deutsch, "Quantum theory, the church-turing principle and the universal quantum computer", Proceedings of the Royal Society of London A, Mathematical and Physical Sciences, 400(1818), pp.97~117 (1985)
- L. K. Grover, "A fast quantum mechanical algorithm for database search", Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, pp.212~219 (1996)
- P. W. Shor, "Algorithms for quantum computation : discrete logarithms and factoring", Proceedings 35th Annual Symposium on Foundations of Computer Science, pp.124~134 (1994)
- J. Ding, "Rainbow, a new multivariable polynomial signature scheme", Applied Cryptography and Network Security, LNCS, 3531, pp.164~175 (2005)
- M. Mosca, "Cybersecurity in an era with quantum computers: will we be ready?", IEEE Security & Privacy, 16(5), pp.38~41 (2018)
- M.R. Garey, "Computers and intractability: a guide to the theory of np-completeness" (1979), W. H. Freeman and Company
- J. Ding, "Rainbow – round 3", Round 3 submission for NIST Post Quantum Cryptography Standardization, ~ (2020)
- D. Lazard, "Resolution des systemes d’equations algebriques", Theoretical Computer Science, 15(1), pp.77~110 (1981)
- J-C. Faugere, "A new efficient algorithm for computing grobner bases(F4)", Journal of Pure and Applied Algebra, 139(1-3), pp.61~88 (1999)
- C-M. Cheng, "Solving quadratic equations with xl on parallel architectures,”Cryptographic Hardware and Embedded Systems", LNCS, 7428, pp.356~373 (2012)
- J. Ding, "New differential-algebraic attacks and reparametrization of Rainbow", LNCS, 5037, pp.242~257 (2008)
- A. Kipnis, "Cryptanalysis of the oil and vinegar signature scheme", LNCS, 1462, pp.257~266 (1998)
- M. Bardet, "Improvements of algebraic attacks for solving the rank decoding and minrank problems", LNCS, 12491, pp.507~536 (2020)
- D. Wiedemann, "Solving sparse linear equations over finite fields", IEEE Transactions on Information Theory, 32(1), pp.54~62 (1986)
- P. Czypek, "Efficient implementations of mqpks on constrained devices", LNCS, 7428, pp.374~389 (2012)
- P. Schwabe, "Solving binary mq with grover’s algorithm", International Conference on Security, Privacy, and Applied Cryptography Engineering, SPACE 2016, pp.303~322 (2016)
- D.J. Berstein, "Asymptotically faster quantum algorithms to solve multivariate quadratic equations", LNCS, 10786, pp.487~5016 (2018)
- J-C. Faugere, "Grobner bases of bihomogeneous ideals generated by polynomials of bidegree (1, 1): algorithms and complexity", Journal of Symbolic Computation, 46(4), pp.406~437 (2011)
- KISA, "The guide to using cryptographic algorithm and key sizes", KISA-GD-2018-0034, Korea Internet &Security Agency, ~ (2018)