[논문]양자컴퓨터에 안전한 짧은 비밀키를 갖는 효율적인 다변수 이차식 기반 전자서명 알고리즘 설계

심경아

doi:10.13089/jkiisc.2023.33.2.211

양자컴퓨터에 안전한 짧은 비밀키를 갖는 효율적인 다변수 이차식 기반 전자서명 알고리즘 설계
An Efficient Post-Quantum Signature Scheme Based on Multivariate-Quadratic Equations with Shorter Secret Keys 원문보기

情報保護學會論文誌 = Journal of the Korea Institute of Information Security and Cryptology, v.33 no.2, 2023년, pp.211 - 222

심경아 (국가수리과학연구소 (공공기반연구본부))

초록
AI-Helper

다변수 이차식 기반 암호알고리즘은 양자컴퓨터에 안전하다고 믿어지는 수학적 난제에 기반을 둔 공개키 암호알고리즘 중의 하나로 현재 사용하고 있는 공개키 암호를 대체할 수 있는 양자내성암호 중의 하나이다. NIST 양자내성암호 공모 3라운드 최종 후보 알고리즘으로 선정되었던 다변수 이차식 기반 전자서명 알고리즘 Rainbow의 다중레이어를 사용하는 구조에 대한 진화된 공격이 대두된 후에 단일 레이어를 이용하는 UOV의 구조에 관심이 집중되고 있다. 본 논문에서는 단일 레이어를 갖는 UOV 구조를 유지하면서 일차식의 특별한 구조, 희소다항식, 랜덤다항식의 다양한 조합을 통해 비밀키의 길이를 대폭 줄이고, 블록 부분 행렬의 역행렬을 이용하여 선형 시스템의 해를 구하는 방법을 적용한 효율적인 다변수 이차식 기반 전자서명 알고리즘을 제안한다. 제안한 전자서명의 안전성 분석을 통해 안전한 파라미터를 설정하고 각 파라미터에서의 키길이와 서명 길이를 비교 분석한다. 제안한 다변수 이차식 기반 전자서명 알고리즘은 서명의 길이가 양자내성 전자서명 중 가장 짧고, 기존 다변수 이차식 기반 전자서명에 비해 비밀키 길이가 최대 97%의 축소 효과를 가진다.

Abstract ▼ AI-Helper

Multivariate quadratic equations (MQ)-based public-key cryptographic algorithms are one of promising post-quantumreplacements for currently used public-key cryptography. After selecting to NIST Post-Quantum Cryptography StandardizationRound 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 blockmatrices 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-quantumsignature schemes based on other hard problems and its secret key size is reduced by up to 97% compared to UOV.

주제어

표/그림 (3)

표 Table 1. Suggested Parameters and Complexities of Our Scheme against Known Attacks(o: the number of equations, v: the number of Vinegar values)
표 Table 2. Key Sizes and Signature Sizes of Our Schemes (Bytes)
표 Table 3. Comparison of Signature Sizes (Bytes)

AI 본문요약
AI-Helper

제안 방법

본 논문에서는 단일 레이어를 갖는 UOV 구조를 유지하면서 일차식의 특별한 구조, 희소 다항식, 랜덤 다항식의 다양한 조합을 통해 비밀키의 길이를 대폭 줄이고, 블록 부분 행렬의 역행렬을 이용하여 선형 시스템의 해를 구하는 방법을 적용한 효율적인 다변수 이차식 기반 전자서명 알고리즘을 제안한다. 제안한 전자서명의 안전성 분석을 통해 안전한 파라미터를 설정하고 각 파라미터에서의 키길이와 서명 길이를 비교 분석한다.
본 논문에서는 단일 레이어를 갖는 UOV의 구조를 유지하면서 일차식의 특별한 구조, 희소 다항식, 랜덤 다항식의 다양한 조합을 통해 비밀키의 길이를 줄이고, 블록 행렬의 역행렬을 이용하여 선형 시스템의 해를 구하는 방법을 적용한 효율적인 다변수 이차식 기반 전자서명 알고리즘을 제안하였다. 제안한 전자서명의 위조 불가능성을 증명하고 여러 대수적인 공격에 대한 안전성 분석을 통해 안전한 파라미터를 설정하고 각 파라미터에서의 키길이와 서명 길이를 비교 분석하였다.
이 절에서는 IV절의 안전성 분석을 바탕으로 세개의 안전도에서 안전한 파라미터를 설정하고 각 파라미터에서의 키길이와 서명 길이를 비교 분석한다.
이 절에서는 제안한 다변수 이차식 기반 전자서명 알고리즘의 위조불가능성을 증명하고 알려진 대수적인 공격에 대한 안전성 분석을 제공한다.
제안한 전자서명 알고리즘에서는 키생성과 서명 생성에서 연산량이 감소하여 효율성이 향상되는데, 여기서 각 연산량을 비교한다.
다변수 이차식 기반 전자서명 알고리즘의 알려진 대수적인 공격은 기반 문제인 다변수 이차식의 시스템의 해를 구하는 문제를 풀어주는 알고리즘을 이용하는 direct 공격과 알고리즘의 대수적인 구조를 이용한 불변 부분 공간을 찾는 Kipnis-Shamir 공격, 동치키와 good key를 이용한 키복구 공격, 두 공격의 조합으로 이루어진 intersection 공격으로 이루어져 있다. 제안한 전자서명 알고리즘은 UOV의 구조를 유지하면서 특별한 비밀키의 형태를 제공하고, UOV에서처럼 공개키와 비밀키의 이차항 부분에 대응되는 대칭 행렬이 전체 랭크를 가지고 있어 안전성 분석이 UOV와 거의 유사하고, 새로운 형태로 인한 가능한 공격을 포함하여 안전성을 분석한다.
본 논문에서는 단일 레이어를 갖는 UOV 구조를 유지하면서 일차식의 특별한 구조, 희소 다항식, 랜덤 다항식의 다양한 조합을 통해 비밀키의 길이를 대폭 줄이고, 블록 부분 행렬의 역행렬을 이용하여 선형 시스템의 해를 구하는 방법을 적용한 효율적인 다변수 이차식 기반 전자서명 알고리즘을 제안한다. 제안한 전자서명의 안전성 분석을 통해 안전한 파라미터를 설정하고 각 파라미터에서의 키길이와 서명 길이를 비교 분석한다.
본 논문에서는 단일 레이어를 갖는 UOV의 구조를 유지하면서 일차식의 특별한 구조, 희소 다항식, 랜덤 다항식의 다양한 조합을 통해 비밀키의 길이를 줄이고, 블록 행렬의 역행렬을 이용하여 선형 시스템의 해를 구하는 방법을 적용한 효율적인 다변수 이차식 기반 전자서명 알고리즘을 제안하였다. 제안한 전자서명의 위조 불가능성을 증명하고 여러 대수적인 공격에 대한 안전성 분석을 통해 안전한 파라미터를 설정하고 각 파라미터에서의 키길이와 서명 길이를 비교 분석하였다. 랜덤한 이차식을 이차항을 이용하는 RR에 비해 LES의 비밀키는 안전도 1, 3, 5에서 각각 약 6.

데이터처리

선택된 파라미터를 기준으로 제안한 전자서명 알고리즘의 키길이와 전자서명 길이를비교한다.

성능/효과

제안한 전자서명의 위조 불가능성을 증명하고 여러 대수적인 공격에 대한 안전성 분석을 통해 안전한 파라미터를 설정하고 각 파라미터에서의 키길이와 서명 길이를 비교 분석하였다. 랜덤한 이차식을 이차항을 이용하는 RR에 비해 LES의 비밀키는 안전도 1, 3, 5에서 각각 약 6.3%, 4%, 3% 정도에 지나지 않아 최대 97%의 키길이 축소 효과를 보였으며, NIST 양자내성암호 표준화 대상 전자서명 알고리즘으로 선정된 Dilithium의 약 6%, Falcon의 20% 정도로, 양자내성 전자서명 중에서 서명 길이가 가장 짧다는 특징을 가지고 있다. 안전성 분석 측면에서는 UOV의 안전성 분석의 핵심적인 부분 중 하나는 이차 다항식의 이차항에 대응되는 대칭 행렬의 랭크가 전체 랭크를 가지느냐 그렇지 않느냐로 결정되므로 제안된 전자서명 알고리즘은 전체 랭크를 가지도록 설계되어 알려진 공격에 대한 UOV의 안전성 분석이 그대로 적용되고 있다.
여기서는 제안한 전자서명 알고리즘의 키길이와 전자서명 길이를 비교를 제공한다. 제안한 다변수 이차식 기반 전자서명 RR, LER, LES는 공개키 길이와 전자서명의 길이는 동일하고, 비밀키의 크기만 차이가 난다. 여기서 RR의 이차항은 랜덤하게 선택한 것으로 UOV 서명과 이차항 부분은 동일하고 나머지 부분이 다르다.

후속연구

안전성 분석 측면에서는 UOV의 안전성 분석의 핵심적인 부분 중 하나는 이차 다항식의 이차항에 대응되는 대칭 행렬의 랭크가 전체 랭크를 가지느냐 그렇지 않느냐로 결정되므로 제안된 전자서명 알고리즘은 전체 랭크를 가지도록 설계되어 알려진 공격에 대한 UOV의 안전성 분석이 그대로 적용되고 있다. 제안된 특수 구조를 이용한 새로운 대수적인 공격은 4.2.4 일차식 대체 공격이 있고, 다른 새로운 공격에 대한 유무는 계속 연구가 필요하다. 향후 새로운 형태의 대수적인 공격의 유무와 설정된 안전한 파라미터를 바탕으로 최적 구현을 수행할 계획이다.
4 일차식 대체 공격이 있고, 다른 새로운 공격에 대한 유무는 계속 연구가 필요하다. 향후 새로운 형태의 대수적인 공격의 유무와 설정된 안전한 파라미터를 바탕으로 최적 구현을 수행할 계획이다.

참고문헌 (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, J. Patarin, and L. Goubin,？"Unbalanced Oil and Vinegar？signature schemes", Advances in？Cryptology, CRYPTO'99, LNCS 1592,？pp. 206-222, 1999.
J. Ding and D. Schmidt. "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, P. Briaud, M. Bros, P.？Gaborit, V. Neiger, O. Ruatta, and？J-P. Tillich, "An algebraic attack on？rank metric code-based cryptosystems", Advances in Cryptology,？EUROCRYPT 2020, Part III, LNCS？12107, pp. 64-93, 2020.
M. Bardet, M. Bros, D. Cabarcas, P.？Gaborit, R. A. Perlner, D.？Smith-Tone, J-P. Tillich, and J. A.？Verbel, "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.
D. Smith-Tone and R. Perlner,"Rainbow band separation is better than we thought", IACRePrint2020-702, June 2020.
J. A. Verbel, J. Baena, D. Cabarcas, R. A. Perlner, and D. Smith-Tone,"On the complexity of？superdetermined" minrank instances, Proc. of the International Conferenceon 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.
J. Ding, M-S. Chen, A. Petzoldt, D.Schmidt, and B-Y. Yang, "Rainbowtechnical report", National Institute of？Standards and Technology, 2019.
A. Petzoldt, S. Bulygin, andJ.Buchmann, "CyclicRainbow: A multivariate signature scheme with a partially cyclic public key", Proc. of？the International Conference on Cryptology in India, LNCS 6498, pp33-48, 2010.
NIST Computer Security Resource Center, "Post-quantum cryptography,round 2 submissions", https://csrc.nist.gov/ Projects/ Post-QuantumCryptography/Round-2-Submissions, Feb. 3,2023.
W. Beullens and B. Preneel, "Fieldlifting for smaller UOV public keys",Proc. of the International Conferenceon Cryptology in India, LNCS10698, pp. 227-246, 2017.
Z. Peng and S. Tang, "Circulant UOV:？a new UOV variant with shorter？private key and faster signature？generation", KSII Transactions on？Internet and Information Systems？(TIIS), vol. 12, no. 3, pp. 1376-1395,？2018.
Z. Peng and S. Tang, "Circulant？Rainbow: A new Rainbow variant？with shorter private key and faster？signature generation", IEEE Access,？vol. 5, pp. 11877-11886, 2017.

상세보기
A. Szepieniec and B. Preneel,？"Block-anti-circulant unbalanced Oil？and Vinegar", Proc. of Selected Areas？in Cryptography, LNCS 11959, pp.？574-588, 2020.
Y. Hashimoto, "On the security of？Circulant UOV/Rainbow", IACR ePrint？2018-947, Oct. 2018.
J. Ding, J. Deaton, Vishakha and？Bo-Yin Yang, "The nested subset？differential attack: a practical direct？attack against LUOV which forges a？signature within 210 minutes". IACR？ePrint 2020-967, Aug. 2020.
H. Furue, K. Kinjo, Y. Ikematsu, Y.？Wang, and T. Takagi, "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, S. Lee, N. Koo, "Efficientimplementations of Rainbow and UOV using AVX2", IACR Trans. Cryptogr.Hardw. Embed. Syst. vol. 2022, no. 1,pp. 245-269, 2022.
K. Sakumoto, T. Shirai, H. Hiwatari:"On provable security of UOV and HFE signature schemes against chosen-message attack", Proc. of the International Conference on Post-Quantum Cryptography, LNCS7071, pp 68-82. 2011.
L. Bettale, J.-C. Faugere andL.Perret, "Hybrid approach for solving multivariate systems over finitefields", Journal of Mathematical？Cryptology, vol. 3, pp. 177-197, 2009.
C. Wolf and B. Preneel, "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 keyschemes", Dissertation Thesis, RUB,June 2013.
NIST Computer Security Resource Center, "Post-quantum cryptography, round 3 submissions", https://csrc.nist.gov/Projects/Post-QuantumCryptography/Round-3-Submissions, Feb. 3, 2023.

LOADING...

표제어: PCR

동의어: Packet Collision Rate

용어 설명 출처 목록 (6)

용어 설명: PCR은 세균 특이성이 있는 primer를 이용하여 적은 수의 세균이 있을지라도 쉽게 검출할 수 있는 유용한 방법이며, 이를 이용하여 구강 내 치면세균막이나 타액에서 직접 세균을 검출할 수 있게 되었다[8].

내보내기 구분	파일저장 인쇄 메일전송
구성항목	기본정보 상세정보 관리번호, 논문명, 저널/프로시딩명, 저자 , 발행년, 권, 호, 시작페이지, 끝페이지, 발행기관 관리번호, 논문명, 대등논문명, 저자 , 저널/프로시딩명, 발행기관, 발행년, 발행언어, 권, 호, 시작페이지, 끝페이지, ISBN, ISSN, 주제분야, 키워드, 초록(한글), 초록(영문), 저자(소속기관)
저장형식	Text(ASCII format) Excel format RefWorks Direct Export RIS format (for Reference Manager, ProCite, EndNote), Scholar's Aids, Mendeley
메일정보	받는사람 (필수) @ 보내는사람 (선택) @ 제목 내용 KISTI 검색결과 이메일 서비스
안내	총 건의 자료가 검색되었습니다. 다운받으실 자료의 인덱스를 입력하세요. (1-10,000) 검색결과의 순서대로 최대 10,000건 까지 다운로드가 가능합니다. 데이타가 많을 경우 속도가 느려질 수 있습니다.(최대 2~3분 소요) 다운로드 파일은 UTF-8 형태로 저장됩니다. 파일의 내용이 제대로 보이지 않을실 때는 웹브라우저 상단의 보기 -> 인코딩 -> 자동선택 여부를 확인하십시오. ~ Text(ASCII format) Excel format

연합인증