양자컴퓨터에 안전한 짧은 비밀키를 갖는 효율적인 다변수 이차식 기반 전자서명 알고리즘 설계
An Efficient Post-Quantum Signature Scheme Based on Multivariate-Quadratic Equations with Shorter Secret Keys
0
조회
0
다운로드
0
인용
0
참고문헌
키워드
초록
다변수 이차식 기반 암호알고리즘은 양자컴퓨터에 안전하다고 믿어지는 수학적 난제에 기반을 둔 공개키 암호알고리즘 중의 하나로 현재 사용하고 있는 공개키 암호를 대체할 수 있는 양자내성암호 중의 하나이다. NIST 양자내성암호 공모 3라운드 최종 후보 알고리즘으로 선정되었던 다변수 이차식 기반 전자서명 알고리즘 Rainbow의 다중 레이어를 사용하는 구조에 대한 진화된 공격이 대두된 후에 단일 레이어를 이용하는 UOV의 구조에 관심이 집중되고 있다. 본 논문에서는 단일 레이어를 갖는 UOV 구조를 유지하면서 일차식의 특별한 구조, 희소 다항식, 랜덤 다항식의 다양한 조합을 통해 비밀키의 길이를 대폭 줄이고, 블록 부분 행렬의 역행렬을 이용하여 선형 시스템의 해를 구하는 방법을 적용한 효율적인 다변수 이차식 기반 전자서명 알고리즘을 제안한다. 제안한 전자서명의 안전성 분석을 통해 안전한 파라미터를 설정하고 각 파라미터에서의 키길이와 서명 길이를 비교 분석한다. 제안한 다변수 이차식 기반 전자서명 알고리즘은 서명의 길이가 양자내성 전자서명 중 가장 짧고, 기존 다변수 이차식 기반 전자서명에 비해 비밀키 길이가 최대 97%의 축소 효과를 가진다.
Abstract
Multivariate quadratic equations (MQ)-based public-key cryptographic algorithms are one of promising post-quantum replacements for currently used public-key cryptography. After selecting to NIST Post-Quantum Cryptography Standardization Round 3 as one of digital signature finalists, Rainbow was cryptanalyzed by advanced algebraic attacks due to its multiple layered structure. The researches on MQ-based schemes are focusing on UOV with a single layer. In this paper, we propose a new MQ-signature scheme based on UOV using the combinations of the special structure of linear equations, spare polynomials and random polynomials to reduce the secret key size. Our scheme uses the block inversion method using half-sized block matrices to improve signing performance. We then provide security analysis, suggest secure parameters at three security levels and investigate their key sizes and signature sizes. Our scheme has the shortest signature length among post-quantum signature schemes based on other hard problems and its secret key size is reduced by up to 97% compared to UOV.
참고문헌 (25)
- W. Shor, "Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer", SIAM J. on Computing, pp.1484~1509 (1997)
- A. Kipnis, "Unbalanced Oil and Vinegar signature schemes", Advances in Cryptology, CRYPTO'99, LNCS, 1592, pp.206~222 (1999)
- J. Ding, "Rainbow, a new multivariable polynomial signature scheme", Proc. of the International Conference on Applied Cryptography and Network Security, LNCS, 3531, pp.164~175 (2005)
- M. Bardet, "An algebraic attack on rank metric code-based cryptosystems", Advances in Cryptology, EUROCRYPT 2020, Part III, LNCS, 12107, pp.64~93 (2020)
- M. Bardet, "Improvements of algebraic attacks for solving the rank decoding and MinRank problems", Advances in Cryptology, ASIACRYPT 2020, Part I, LNCS, 12491, pp.507~536 (2020)
- W. Beullens, "Improved cryptanalysis on UOV and Rainbow", Advances in Cryptology, EUROCRYPT 2021, Part I, LNCS, 12696, pp.348~373 (2021)
- Rainbow band separation is better than we thought, "D. Smith-Tone", ~, pp.IACR ePrint 2020-702 (2020)
- J. A. Verbel, "On the complexity of superdetermined", minrank instances, Proc. of the International Conference on Post-Quantum Cryptography, LNCS, 11505, pp.167~186 (2019)
- W. Beullens, "Breaking Rainbow takes a weekend on a laptop", Advances in Cryptology, CRYPTO 2022, Part II, LNCS, 13508, pp.464~479 (2022)
- Rainbow technical report, "J. Ding", National Institute of Standards and Technology, ~ (2019)
- A. Petzoldt, "CyclicRainbow : A multivariate signature scheme with a partially cyclic public key", Proc. of the International Conference on Cryptology in India, LNCS, 6498, pp.33~48 (2010)
- "Post-quantum cryptography, round 2 submissions"[URL]
- W. Beullens, "Field lifting for smaller UOV public keys", Proc. of the International Conference on Cryptology in India, LNCS, 10698, pp.227~246 (2017)
- Zhiniang Peng, "Circulant UOV: a new UOV variant with shorter private key and faster signature generation", KSII Transactions on Internet and Information Systems, 12(3), pp.1376~1395 (2018), 한국인터넷정보학회[DOI]
- Z. Peng, "Circulant Rainbow : A new Rainbow variant with shorter private key and faster signature generation", IEEE Access, 5, pp.11877~11886 (2017)
- A. Szepieniec, "Block-anti-circulant unbalanced Oil and Vinegar", Proc. of Selected Areas in Cryptography, LNCS, 11959, pp.574~588 (2020)
- On the security of Circulant UOV, "Rainbow", Y. Hashimoto, 2018, IACR ePrint 2018-947
- The nested subset differential attack: a practical direct attack against LUOV which forges a signature within 210 minutes, "J. Ding", ~, pp.IACR ePrint 2020-967 (2020)
- H. Furue, "A structural attack on block-anti-circulant UOV at SAC 2019", Proc. of the International Conference on Post-Quantum Cryptography, LNCS, 12100, pp.323~339 (2020)
- K-A. Shim, "Efficient implementations of Rainbow and UOV using AVX2", IACR Trans. Cryptogr. Hardw. Embed. Syst, 2022(1), pp.245~269 (2022)
- K. Sakumoto, "On provable security of UOV and HFE signature schemes against chosen-message attack", Proc. of the International Conference on Post-Quantum Cryptography, LNCS, 7071, pp.68~82 (2011)
- L. Bettale, "Hybrid approach for solving multivariate systems over finite fields", Journal of Mathematical Cryptology, 3, pp.177~197 (2009)
- C. Wolf, "Large superfluous keys in multivariate quadratic asymmetric systems", Proc. of the International Conference on Practice and Theory of Public-Key Cryptography, LNCS, 3386, pp.275~287 (2005)
- E. Thomae, "About the security of multivariate quadratic public key schemes", pp.2013
- "Post-quantum cryptography, round 3 submissions"[URL]