[논문]NIST PQC 공모전 동향 분석 및 표준화 대상 & Round 4 알고리즘 소개

김동천; 김영범; 서석충

[국내논문] NIST PQC 공모전 동향 분석 및 표준화 대상 & Round 4 알고리즘 소개 원문보기

情報保護學會誌 = KIISC review, v.33 no.2, 2023년, pp.39 - 48

김동천 (국민대학교 금융정보보안학과) , 김영범 (국민대학교 금융정보보안학과) , 서석충 (국민대학교 금융정보보안학과)

초록
AI-Helper

소인수 분해 및 이산대수 문제의 난제를 기반으로 설계된 기존의 공개키 암호 및 전자서명 체계가 1994년 제안된 Shor 알고리즘으로부터 안전성에 대한 위협을 받게 되자, NIST에서는 양자컴퓨팅 환경으로부터 보안성이 유지되는암호를 선정하기 위해 양자내성암호 공모전을 개최하였다. 총 3 Round를 통해 PQC 표준화 대상 알고리즘을 채택하였으며, 추가로 채택된 양자내성암호의 기반에 대한 다양성을 두기 위해 Round 4를 진행하였다. 따라서 본 논문에서는 표준화 대상으로 선정된 알고리즘(Selected Algorithms 2022)과 현재 Round 4를 진행하고 있는 알고리즘의 기반이 되는 배경지식과 구조를 설명하고, 알고리즘별 주요 사양을 통해 각각의 장단점을 살펴볼 것이다. 나아가 현재 양자내성연구단을 통해 우리나라에서 제안된 KpqC에 대해서도 간단히 소개할 것이다.

표/그림 (11)

그림 [그림 1] NIST PQC 공모전 연표
표 [표 1] Round 3 Finalists
표 [표 2] Round 3 Alternate Candidates
표 [표 3] Selected Algorithms 2022
표 [표 4] Round 4 Algorithms
표 [표 5] Selected Algorithms Spec
표 [표 6] Selected Algorithms PKE/KEMs 연산 시간
표 [표 7] Selected Algorithms DSA 연산 시간
표 [표 8] Round 4 Algorithms Spec
표 [표 9] Round 4 연산 시간
표 [표 10] KpqC Competition Round 1

AI 본문요약
AI-Helper

문제 정의

본 논문에서는 NIST PQC 공모전의 진행 상황을 설명하고, PQC 표준화 대상 알고리즘(Selected Algorithms) 및 Round 4에 진출한 알고리즘들을 소개하였다. 나아가 NIST는 2024년까지 공모전을 통해 채택된 알고리즘에 대해 상용화 가능한 표준화 초안을 발표할 계획이다.
본 논문에서는 위에서 언급한 NIST PQC 공모전 중 Round 3에 대한 주요 결과와 이를통해 선정된 알고리즘(Selected Algorithms 2022) 및 Round 4에서 후보로 등록된 알고리즘에 대해 분석하여 소개할 것이다.
여기서는 2단원에서 소개한 Selected Algorithms 2022와 Round 4 알고리즘의 배경이 되는 기반 지식을 소개하고자 한다.

제안 방법

나아가 NIST는 KEM 분야에서 표준화 대상 암호 알고리즘의 기반 난제에 대한 다양성을 추구하기 위해 [표 4]와 같이 BIKE, HQC, Classic McEliece, SIKE를 대상으로 Round 4를 진행하였다.
본 단원에서는 NIST PQC Round 4에 진출한 각각의 알고리즘을 소개하고, 특징 및 장단점을 분석하고자 한다. 다만 SIKE의 경우 위에서 언급했듯이 취약점이 발견되었으므로, 본 논문에서는 분석 대상에서 제외하였다.
본 단원에서는 앞서 설명한 배경지식을 기반으로 NIST PQC 표준화 대상 알고리즘(Selected Algorithms 2022) 각각을 소개하고, 특징 및 장단점을 분석하고자 한다.

대상 데이터

NIST PQC Round 3에서는 Public-key Encryption (PKE) and Key Encapsulation Mechanism(KEM)과 Digital Signature Algorithms(DSA), 두 관점에서 Finalists 7개[표 1]와 이를 대체할 수 있는 Alternate Candidates 8개[표 2]를 발표하였다.
더불어 SPHINCS+의 경우 필요한 연산에 있어 격자 기반 서명 알고리즘보다 서명의크기가 훨씬 크고 느리지만 PQC의 안전성을 격자 기반으로 단순화하지 않기 위해 Round 4를 진행하는 대신 표준화 대상으로 바로 선정하였다.

이론/모형

Classic McEliece는 1978년 McEliece에 의해 제안된 선형 오류 수정 코드의 일종인 이진 Goppa 코드를 기반으로 설계되었다.
공개키는 패리티 검사 행렬을 기반으로 생성하며, 개인키는 이진 Goppa 코드를 기반으로 한다.

성능/효과

SIKE의 경우 위에서 언급했듯이 Isogeny 기반 알고리즘에 대한 효율적인 키 복구 공격이 발견되어 취약점이 인정되었지만, NIST가 해당 정보를 보관함으로써 다른 연구자에게 도움이 될 것으로 판단하여 철회되지 않고 현재까지도 NIST 공식 홈페이지 Round 4에서 확인할 수 있다.

후속연구

따라서 향후 연구에서는 현재 사용 중인 암호 및 전자서명에 대한 알고리즘을 GPU 기반 서버 관점에서 최적화에 관한 연구를 진행할 것이다.

참고문헌 (29)

Gorjan Alagic, Jacob Alperin-Sheriff, Daniel Apon, David Cooper, Quynh Dang, John Kelsey, Yi-Kai Liu, Carl Miller, Dustin Moody, Rene Peralta, Ray Peralta, Ray Perlner, Angela Robinson, Daniel Smith-Tone, "Status Report on the Second Round of the NIST Post-Quantum Cryptography Standardization Process", NIST, February 2020.？
이태호, 조영진, 박준우, "NIST PQC 공모전 동향 연구", 한국통신학회, 한국통신학회 학술대회논문집, pp. 575-577, November 2022？
Wouter Castryck, Thomas Decru, "An efficient key recovery attack on SIDH(Preliminary version)", Cryptology ePrint Archive, July 2022？
Chengdong Tao, Albrecht Petzoldt, Jintai Ding, "Improved Key Recovery of the HFEv- Signature Scheme", Cryptology ePrint Archive, November 2020？
Ward Beullens, IBM Research - Zurich, "Breaking Rainbow Takes a Weekend on a Laptop", Advances in Cryptology-CRYPTO 2022, August 2022？
이정환, 김규상, 김희석, "NIST PQC Round 3 격자 기반 암호 KEM에 대한 부채널 분석 기법 동향 분석", 한국정보보호학회, 정보보호학회지, pp. 47-56, February 2022？
박찬희, 윤영여, 박해룡, 최은영, 김호원, "격자기반 양자내성 키 교환 알고리즘 구현", 한국정보보호학회, 정보보호학회지, pp. 11-16, June 2020？
Daniele Miccianocio, Shafi Goldwasser, "Shortest Vector Problem", Complexity of Lattice Problems: A Cryptographic Perspective, pp. 69-90, 2002？
박태환, 배봉진, 김호원, "Stateless 해시 기반 서명 기법 동향 및 전망", 한국정보처리학회, 학술대회논문집, pp. 268-270, January 2016？
Daniel J. Bernstein, Andreas Hulsing, Stefan Kolbl, Ruben Niederhagen, Joost Rijneveld, Peter Schwabe, "The SPHINCS+Signature Framework", CCS '19, November 2019？
최호진, "GPU 환경에서 해시 기반 PQC 알고리즘 SPHINCS+의 효율적인 구현방안", 국민대학교 일반대학원 학위 논문, February 2022？
송경주, 강예준, 장경배, 서화정, "코드기반암호에 대한 ISD 공격 알고리즘 연구 동향", 한국정보처리학회, 춘계학술발표대회 논문집 제28권 제1호, 167-170, May 2021？
장경배, 심민주, 서화정, "코드기반암호를 활용한 IoT 환경 보안 프로토콜 설계", 한국정보처리학회, 춘계학술발표대회 논문집 제27권 제1호, May 2020？
유준수, 윤지원, "LWE와 완전동형암호에 대한 분석 및 동향", 한국정보보호학회, 정보보호학회지, 111-119, October 2020？
Roberto Avanzi, Joppe Bos, Leo Ducas, Eike Kiltz, Tancrede Lepoint, Vadim Lyubashevsky, John M.Schanck, Pter Schwabe, Gregor Seiler, Demien Stehle, "CRYSTALS-KYBER(Algorithm Specifications And Supporting Documentations (version 3.0)), NIST PQC Round, October 1 2020？
김성재, "양자내성암호를 위한 고성능 Crystals-Kyber 암호 아키텍처", 인하대학교 공학 대학원 석사학위논문, February 2022？
김영범, "8-bit AVR 마이크로 컨트롤러에서의 양자내성암호 Crystals-Kyber 최적화 구현 연구", 국민대학교 일반대학원 석사학위논문, February 2022？
김일주, "격자 기반 전자서명 qTESLA, Dilithium의 부채널 분석에 관한 연구", 국민대학교 일반대학원 논문, February 2020？
구자현, 이선용, 노종선, "서로 다른 소수를 모듈러스로 갖는 짧은 정수해 문제들 사이의 관계", 한국통신학회, 학술대회논문집, February 2020？
Shi Bai, Leo Ducas, Eike Kiltz, Tancrede Lepoint, Vadim Lyubashevsky, Peter Schwabe, Gregor Seiler and Damien Stehle, "CRYSTALS-Dilithium", Algorithm Specifications and Supporting Documentation, October 1 2020？
김규상, 박동준, 홍석희, "NIST PQC Round 3 FALCON 전자서명 알고리즘의 전력 분석 취약점 연구", 한국정보보호학회, 정보보호학회지, pp. 57-64, February 2021？
Pierre-Alain Fouque, Jeffrey Hoffstein, Paul Kirchner, Vadim Lyubashevsky, Thomas Pornin, Thomas Prest, Thomas Ricosset, Gregor Seiler, William Whyte, Zhenfei Zhang, "FALCON : Fast-Fourier Lattice-based Compact vSignatures over NTRU", Submission to the NIST's post-quantum cryptography standardization process, October 1 2020？
강태구, "해시기반 포스트 양자 서명 기법 분석", 명지대학교 대학원 석사학위논문, February 2020？
Jean-Philippe Aumasson, Daniel J. Bernstein, Ward Beullens, Christoph Dobraunig, Maria Eichlseder, Scott Fluhrer, Stefan-Lukas Gazdag, Andreas Hulsing, Panos Kampanakis, Stefan Kolbl, Tanja Lange, Martin M. Lauridsen, Florian Mendel, Ruben Niederhagen, Christian Rechberger, Joost Rijneveld, Peter Schwabe, Bas Westerbaan, "SPHICS+ Submission to the NIST post-quantum project, v.3", NIST Submission, October 2020？
Alexandr Kuznetsov, Maria Lutsenko, Nastya Kiian, Tymur Makushenko, Tetiana Kuznetsova, "Code-based key encapsulation mechanisms for post-quantum standardization", IEEE DESSERT, May 2018？
Nicolas Aragon, Paulo S. L. M. Barreto, Slim Bettaieb, Loic Bidoux, Olivier Blazy, Jean-Christophe Deneuville, Philippe Gaborit, Santosh Ghosh, Shay Gueron, Tim Guneysu, Carlos Aguilar Melchor, Rafael Misoczke, Edoardo Persichetti, Jan Richter-Brockmann, Nicolas Sendrier, Jean-Pierre Tillich, Valentin Vasseur, Gilles Zemor, "BIKE:Bit Flipping Key Encapsulation(Round 4 Submission)", NIST Submission, October 2022？
Carlos Aguilar Melchor, Nicolas Aragon, Slim Bettaieb, Loic Bidoux, Olivier Blazy, Jurjen Bos, Jean-Christophe Deneuville, Arnaud Dion, Philippe Gaborit, Jerome Lacan, Edoardo Persichetti, Jean-Marc Robert, Pascal Veron, Gilles Zemor, "Hamming Quasi-Cyclic(HQC) (Fourth round version)", NIST Submission, October 2022？
Martin R. Albrecht, Daniel J. Bernstein, Tung Chou, Carlos Cid, Jan, Gilcher, Tanja Lange, Varun Maram, Ingo von Maurich, Rafael Misoczki, Ruben Niederhagen, Kenneth G., Paterson, Edoardo Persichetti, Christiane Peters, Peter Schwabe, Nicolas Sendrier, Jakub Szefer, Cen, Jung Tjhai, Martin Tomlinson, Wen Wang, "Classic McEliece:conservative code-based cryptography:cryptosystem specification", NIST Submission, October 2022？
최장혁, 박민진, 김동찬, "Classic McEliece 규격 및 파라미터별 성능에 관한 연구", 한국통신학회, 학술대회논문집, pp. 1513-1514 June 2021

표제어: 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

연합인증