NIST 포스트 퀀텀 암호 표준

NIST Post-Quantum Cryptography Standardization

Post-Quantum Cryptography Standardization은[1] NIST가 그들의 표준을 포스트 Quantum 암호화를 포함하도록 갱신하기 위한 프로그램 및 경쟁이다.[2]2016년 PQCrypto에서 발표되었으며,[3] 2017년[4] 말 최초 제출 마감일까지 23개의 서명 방식과 59개의 암호화/KEM 방식이 제출되었으며, 이 중 총 69개가 완전하고 적절하다고 판단되어 1차에 참여하였다.이 중 3개가 시그니처 제도인 7개가 2020년 7월 22일 발표된 3차전에 진출했다.

배경

양자컴퓨팅의 잠재적 영향에 대한 학문적 연구는 적어도 2001년으로 거슬러 올라간다.[5]NIST는 2016년 4월에 발표한 보고서를 통해 2030년까지 일반적으로 사용되는 RSA 알고리즘을 불안정하게 만들 수 있는 양자 기술의 가능성을 인정하는 전문가를 인용하고 있다.[6]그 결과, 양자 보안 암호 원효 표준화 필요성이 추진되었다.대부분의 대칭 원형은 양자 내성을 갖는 방식으로 비교적 쉽게 수정할 수 있기 때문에, 노력은 공개키 암호법, 즉 디지털 서명과 키 캡슐화 메커니즘에 집중되어 왔다.2016년 12월 NIST는 제안서 호출을 발표함으로써 표준화 절차를 개시하였다.[7]

이 대회는 이제 예상된 4라운드 중 3라운드에서 각 라운드에서 일부 알고리즘은 폐기되고 다른 알고리즘은 보다 면밀하게 연구된다.NIST는 표준화 문서를 2024년까지 출판하기를 희망하지만 양자 컴퓨팅의 중대한 돌파구가 만들어질 경우 이 과정을 가속화할 수 있다.

미래 표준을 FIPS로 발행할지, NIST 특별 간행물(SP)으로 발행할지는 현재 미정이다.

라운드 원

고려 대상:[8]
(스트라이크로는 철회되었음을 의미한다)

유형 PKE/KEM 서명 시그니처 & PKE/KEM
격자
  • 컴팩트 LWE
  • 크리스털-케이버
  • 딩키익스체인지
  • 엠블럼과 R.엠블럼
  • 프로도켐
  • HILA5(끌어서 5라운드로 병합)
  • KCL(pka OKCN/AKCN/CNKE)
  • 킨디
  • LAC
  • 리마
  • 도마뱀
  • 로터스
  • 뉴홉
  • NTRUEncrypt[9]
  • NTRU-HRSS-KEM
  • NTRU 프라임
  • 오드 맨해튼
  • 라운드2(그라운드로 표시되고 라운드5로 병합
  • 라운드5(2018년 8월 4일 발표)[10]
  • 세이버
  • 곰 세 마리
  • 티타늄
코드 기반
  • 빅 지진
  • 자전거
  • 클래식 맥엘리스 + NTS-KEM
  • DAGS
  • 에돈케이
  • HQC
  • LEACH(끌어서 롤로로 병합)
  • LEDAkem
  • LEDApkc
  • 렙톤
  • LOCKER(끌어서 롤로로 병합)
  • 맥니
  • NTS-KEM
  • 롤로(오로보로스-R, 레이크 및 라커)
  • Ouroboros-R(끌어서 롤로로 병합)
  • QC-DPC 켐
  • 람스타케
  • RLCE-KEM
  • RQC
  • pqsigRM
  • 라코스
  • 랭크사인
해시 기반
  • 중력-SPHINCS
  • 스핑크스+
Multivariate
  • CFPKM
  • 지오판투스
  • 듀얼 모드MS
  • 게MSS
  • 구이
  • 하이엠큐-3
  • 뤄브
  • MQDSS
  • 레인보우
  • SRTPI
  • DME
브레이드 그룹
  • 호두DSA
초대칭 타원곡선 이등생성
풍자적 제출
기타
  • 다시 맞춰 보세요.
  • HK17
  • 메르센-756839
  • RVB
  • 피크닉

게시된 공격을 한 번에 한 개씩 제출

  • 로렌츠 패니로 다시 추측하기
  • 로렌츠 패니별[15] RVB
  • RaCoSS by Daniel J. Bernstein, Andreas Hülsing, Tanja Lange, Lorrenz Panny[16]
  • HK17: Daniel J. Bernstein과 Tanja Lange[17]
  • 양보인별 SRTPI[18]
  • 호두DSA
    • 워드 벌렌스와 사이먼 R.블랙번[19]
    • 마트베이 코토프, 안톤 멘쇼프, 알렉산더 우샤코프[20]
  • DRS: Yang Yu 및 Léo Ducas
  • DAGS: 엘리스 바렐리, 알랭 쿠브뢰르[22]
  • 마티외 레퀴스네와 장피에르 틸리히의[23] 에돈-K
  • 알랭 쿠브뢰르, 마티외 레크네, 장피에르 틸리히의[24] RLCE
  • Hila5 by Daniel J. Bernstein, Leon Groot Bruinderink, Tanja Lange, Lorenz Panny[25]
  • Ward Beullens, Wouter Castryck, Frederik Vercauteren에[26] 의한 지오판투스
  • 랭크사인 by 토마스 파편-앨러자드와 장 피에르 틸리히
  • 필립 가보릿의 맥니;[28] 테리 슈 치엔 라우와 치크 하우 탄

2라운드

2019년 1월 30일 2라운드로 넘어가는 후보들이 발표되었다.다음 구성 요소:[30]

유형 PKE/KEM 서명
격자
  • 크리스털-케이버[31]
  • 프로도켐
  • LAC
  • 뉴홉[33]
  • NTRU(NTRUEncrypt 및 NTRU-HRSS-KEM의 멀티거)[9]
  • NTRU 프라임[34]
  • 라운드5(2018년 8월 4일 발표)[10]
  • 세이버[35]
  • 곰[36] 세 마리
  • 크리스털-딜리튬[31]
  • 매[37]
  • 퀘슬라
코드 기반
해시 기반
Multivariate
초대칭 타원곡선 이등생성
영지식증거

3라운드

2020년 7월 22일, NIST는 최종 결승선 7개("첫 트랙")와 8개의 대체 알고리즘("두 번째 트랙")을 발표했다.1차 트랙은 가장 가능성이 높은 것으로 보이는 알고리즘을 포함하고 있으며, 3차 라운드의 마지막에 표준화를 위해 검토될 것이다.두 번째 트랙의 알고리즘은 3라운드가 끝난 후에도 표준의 일부가 될 수 있다.[51]NIST는 4라운드에서 대체 후보 중 일부가 검토될 것으로 예상하고 있다.NIST는 또한 향후 새로운 제도 제안에 대한 서명 범주를 다시 열 수 있다고 제안한다.[52]

NIST는 2021년 6월 7일부터 9일까지 제3차 PQC 표준화 회의를 사실상 실시하였다.[53]컨퍼런스에는 후보들의 업데이트와 구현, 성과, 보안 문제에 대한 토론이 포함되었다.지적 재산에 대한 우려에 소량의 집중을 할애했다.

결승전

유형 PKE/KEM 서명
격자[a]
코드 기반
Multivariate

대체 후보

유형 PKE/KEM 서명
격자
  • 프로도켐
  • NTRU 프라임
코드 기반
  • 자전거
  • HQC
해시 기반
  • 스핑크스+
Multivariate
  • 게MSS
초대칭 타원곡선 이등생성
영지식증거
  • 피크닉

지적 재산에 대한 우려

NIST가 최종 후보자와 대체 후보자에 대해 발표한 후, 특히 카이버와 뉴홉과 같은 격자 기반 계획을 둘러싼 다양한 지적 재산에 대한 우려의 목소리가 나왔다.NIST는 단체 제출 시 서명된 성명서를 보유하고 있으며, 제3자가 청구를 제기할 수 있다는 우려가 여전히 존재한다.NIST는 그들이 승리 알고리즘을 선택하는 동안 그러한 고려를 고려할 것이라고 주장한다.[54]

적응

이번 라운드에서 일부 후보들은 일부 공격 벡터에 취약한 것으로 나타났다.따라서 이 후보자들은 다음과 같이 적응해야 한다.

크리스탈-키버와 세이버
보안 청구를 유지하기 위해 제안서에 사용된 중첩된 해시를 변경할 수 있다.[55]
매
측면 채널에 의한 공격. 공격에 저항하기 위해 마스킹이 추가될 수 있다.이 적응은 성능에 영향을 미치므로 표준화 중에 고려해야 한다.[56]

참고 항목

메모들

  1. ^ NIST는 이러한 격자 기반 PKE/KEM 체계 중 하나와 격자 기반 서명 체계 중 하나를 표준화하고자 한다.[51]

참조

  1. ^ "Post-Quantum Cryptography PQC". 3 January 2017.
  2. ^ "Post-Quantum Cryptography Standardization – Post-Quantum Cryptography". Csrc.nist.gov. 3 January 2017. Retrieved 31 January 2019.
  3. ^ "The Future Is Now: Spreading the Word About Post-Quantum Cryptography". 24 November 2020.
  4. ^ "Archived copy". Archived from the original on 2017-12-29. Retrieved 2017-12-29.{{cite web}}: CS1 maint: 타이틀로 보관된 사본(링크)
  5. ^ Hong, Zhu (2001). "Survey of Computational Assumptions Used inCryptography Broken or Not by Shor's Algorithm" (PDF). {{cite journal}}:Cite 저널은 필요로 한다. journal=(도움말)
  6. ^ "NIST Released NISTIR 8105, Report on Post-Quantum Cryptography". 21 December 2016. Retrieved 5 November 2019.
  7. ^ "NIST Asks Public to Help Future-Proof Electronic Information". 20 December 2016. Retrieved 5 November 2019.
  8. ^ Computer Security Division, Information Technology Laboratory (3 January 2017). "Round 1 Submissions – Post-Quantum Cryptography – CSRC". Csrc.nist.gov. Retrieved 31 January 2019.
  9. ^ a b c "Archived copy". Archived from the original on 2017-12-29. Retrieved 2017-12-29.{{cite web}}: CS1 maint: 타이틀로 보관된 사본(링크)
  10. ^ a b "Google Groups". Groups.google.com. Retrieved 31 January 2019.
  11. ^ a b "ROLLO". Pqc-rollo.org. Retrieved 31 January 2019.
  12. ^ RSA는 총 키 크기 1TiB에 대해 2개의31 4096비트 프리타임을 사용한다."하드 드라이브에 거의 맞는 키"
  13. ^ Bernstein, Daniel; Heninger, Nadia (2017-04-19). "Post-quantum RSA" (PDF). Retrieved 2019-12-10.
  14. ^ "Dear all, the following Python script quickly recovers the message from a given "Guess Again" ciphertext without knowledge of the private key" (PDF). Csrc.nist.gov. Retrieved 30 January 2019.
  15. ^ Panny, Lorenz (25 December 2017). "Fast key recovery attack against the "RVB" submission to #NISTPQC: t …. Computes private from public key". Twitter. Retrieved 31 January 2019.
  16. ^ "Archived copy". Archived from the original on 2017-12-26. Retrieved 2018-01-04.{{cite web}}: CS1 maint: 타이틀로 보관된 사본(링크)
  17. ^ "Archived copy". Archived from the original on 2018-01-05. Retrieved 2018-01-04.{{cite web}}: CS1 maint: 타이틀로 보관된 사본(링크)
  18. ^ "Dear all, We have broken SRTPI under CPA and TPSig under KMA" (PDF). Csrc.nist.gov. Retrieved 30 January 2019.
  19. ^ Beullens, Ward; Blackburn, Simon R. (2018). "Practical attacks against the Walnut digital signature scheme". Eprint.iacr.org.
  20. ^ Kotov, Matvei; Menshov, Anton; Ushakov, Alexander (2018). "AN ATTACK ON THE WALNUT DIGITAL SIGNATURE ALGORITHM". Eprint.iacr.org.
  21. ^ Yu, Yang; Ducas, Léo (2018). "Learning strikes again: the case of the DRS signature scheme". Eprint.iacr.org.
  22. ^ Barelli, Elise; Couvreur, Alain (2018). "An efficient structural attack on NIST submission DAGS". arXiv:1805.05429 [cs.CR].
  23. ^ Lequesne, Matthieu; Tillich, Jean-Pierre (2018). "Attack on the Edon-K Key Encapsulation Mechanism". arXiv:1802.06157 [cs.CR].
  24. ^ Couvreur, Alain; Lequesne, Matthieu; Tillich, Jean-Pierre (2018). "Recovering short secret keys of RLCE in polynomial time". arXiv:1805.11489 [cs.CR].
  25. ^ Bernstein, Daniel J.; Groot Bruinderink, Leon; Lange, Tanja; Lange, Lorenz (2017). "Hila5 Pindakaas: On the CCA security of lattice-based encryption with error correction". {{cite journal}}:Cite 저널은 필요로 한다. journal=(도움말)
  26. ^ "Official Comments" (PDF). Csrc.nist.gov. 13 September 2018.
  27. ^ Debris-Alazard, Thomas; Tillich, Jean-Pierre (2018). "Two attacks on rank metric code-based schemes: RankSign and an Identity-Based-Encryption scheme". arXiv:1804.02556 [cs.CR].
  28. ^ "I am afraid the parameters in this proposal have at most 4 to 6‐bits security under the Information Set Decoding (ISD) attack" (PDF). Csrc.nist.gov. Retrieved 30 January 2019.
  29. ^ Lau, Terry Shue Chien; Tan, Chik How (31 January 2019). "Key Recovery Attack on McNie Based on Low Rank Parity Check Codes and Its Reparation". In Inomata, Atsuo; Yasuda, Kan (eds.). Advances in Information and Computer Security. Lecture Notes in Computer Science. Vol. 11049. Springer International Publishing. pp. 19–34. doi:10.1007/978-3-319-97916-8_2. ISBN 978-3-319-97915-1.
  30. ^ Computer Security Division, Information Technology Laboratory (3 January 2017). "Round 2 Submissions – Post-Quantum Cryptography – CSRC". Csrc.nist.gov. Retrieved 31 January 2019.
  31. ^ a b Schwabe, Peter. "CRYSTALS". Pq-crystals.org. Retrieved 31 January 2019.
  32. ^ "FrodoKEM". Frodokem.org. Retrieved 31 January 2019.
  33. ^ Schwabe, Peter. "NewHope". Newhopecrypto.org. Retrieved 31 January 2019.
  34. ^ "Archived copy". Archived from the original on 2019-09-01. Retrieved 2019-01-30.{{cite web}}: CS1 maint: 타이틀로 보관된 사본(링크)
  35. ^ "SABER". Retrieved 17 June 2019.
  36. ^ "ThreeBears". SourceForge.net. Retrieved 31 January 2019.
  37. ^ "Falcon". Falcon. Retrieved 26 June 2019.
  38. ^ "qTESLA – Efficient and post-quantum secure lattice-based signature scheme". Retrieved 31 January 2019.
  39. ^ "BIKE – Bit Flipping Key Encapsulation". Bikesuite.org. Retrieved 31 January 2019.
  40. ^ "HQC". Pqc-hqc.org. Retrieved 31 January 2019.
  41. ^ "LEDAkem Key Encapsulation Module". Ledacrypt.org. Retrieved 31 January 2019.
  42. ^ "LEDApkc Public Key Cryptosystem". Ledacrypt.org. Retrieved 31 January 2019.
  43. ^ "Archived copy". Archived from the original on 2017-12-29. Retrieved 2017-12-29.{{cite web}}: CS1 maint: 타이틀로 보관된 사본(링크)
  44. ^ "RQC". Pqc-rqc.org. Retrieved 31 January 2019.
  45. ^ [1]
  46. ^ "Archived copy". Archived from the original on 2019-01-31. Retrieved 2019-01-30.{{cite web}}: CS1 maint: 타이틀로 보관된 사본(링크)
  47. ^ "LUOV -- An MQ signature scheme". Retrieved 22 January 2020.
  48. ^ "MQDSS post-quantum signature". Mqdss.org. Retrieved 31 January 2019.
  49. ^ "SIKE – Supersingular Isogeny Key Encapsulation". Sike.org. Retrieved 31 January 2019.
  50. ^ "Picnic. A Family of Post-Quantum Secure Digital Signature Algorithms". microsoft.github.io. Retrieved 26 February 2019.
  51. ^ a b Moody, Dustin; Alagic, Gorjan; Apon, Daniel C.; Cooper, David A.; Dang, Quynh H.; Kelsey, John M.; Liu, Yi-Kai; Miller, Carl A.; Peralta, Rene C.; Perlner, Ray A.; Robinson, Angela Y.; Smith-Tone, Daniel C.; Alperin-Sheriff, Jacob (2020). "Status Report on the Second Round of the NIST Post-Quantum Cryptography Standardization Process". doi:10.6028/NIST.IR.8309. S2CID 243755462. Retrieved 2020-07-23. {{cite journal}}:Cite 저널은 필요로 한다. journal=(도움말)
  52. ^ Third PQC Standardization Conference - Session I Welcome/Candidate Updates, retrieved 2021-07-06
  53. ^ Computer Security Division, Information Technology Laboratory (2021-02-10). "Third PQC Standardization Conference CSRC". CSRC NIST. Retrieved 2021-07-06.
  54. ^ "Submission Requirements and Evaluation Criteria" (PDF).
  55. ^ Grubbs, Paul; Maram, Varun; Paterson, Kenneth G. (2021). "Anonymous, Robust Post-Quantum Public Key Encryption". {{cite journal}}:Cite 저널은 필요로 한다. journal=(도움말)
  56. ^ Karabulut, Emre; Aysu, Aydin (2021). "Falcon Down: Breaking Falcon Post-Quantum Signature Scheme through Side-Channel Attacks". {{cite journal}}:Cite 저널은 필요로 한다. journal=(도움말)

외부 링크