Стандартизація постквантової криптографії NIST

Стандартизація постквантової криптографії[1] — це програма, організована Національним інститутом стандартів і технологій США (NIST) для включення постквантової криптографії у свої стандарти.[2] Її було оголошено на PQCrypto 2016.[3] 23 схеми підпису та 59 схем шифрування або механізмів інкапсуляції ключів[en] були подані до кінцевого терміну подачі заявок в кінці 2017 року, з яких 69 відповідали базовим вимогам та потрапили до першого раунду конкурсу, який проводився в рамках цієї програми.[4]

13 серпня 2024 року Інститут випустив фінальні версії перших трьох постквантових криптографічних стандартів: FIPS 203, FIPS 204 та FIPS 205.[5]

Передумови

[ред. | ред. код]

Наукові дослідження потенційного впливу квантових комп'ютерів почалися щонайменше з 2001 року.[6] У звіті NIST, опублікованому у квітні 2016 року, наводяться слова експертів, які визнають, що квантові технології зможуть взломувати широко використовуваний алгоритм RSA до 2030 року.[7] Як наслідок, виникла потреба у стандартизації квантово-стійких криптографічних алгоритмів. Оскільки більшість симетричних криптографічних алгоритмів відносно легко модифікувати таким чином, щоб зробити їх квантово-стійкими, то зусилля були зосереджені на криптографії з відкритим ключем, зокрема на цифрових підписах та механізмах інкапсуляції ключів. У грудні 2016 року NIST ініціював процес стандартизації, оголосивши конкурс.[8]

Перший раунд

[ред. | ред. код]

На розгляді були такі алгоритми:[9]
(закресленим позначаються зняті з конкурсу)

Тип PKE/KEM Цифровий підпис Цифровий підпис & PKE/KEM[en]
На основі ґраток
  • Compact LWE
  • CRYSTALS-Kyber[en]
  • Ding Key Exchange
  • EMBLEM та R.EMBLEM
  • FrodoKEM
  • HILA5 (знятий та об'єднаний з Round5)
  • KCL (pka OKCN/AKCN/CNKE)
  • KINDI
  • LAC
  • LIMA
  • Lizard
  • LOTUS
  • NewHope
  • NTRUEncrypt[en][10]
  • NTRU-HRSS-KEM
  • NTRU Prime
  • Odd Manhattan
  • Round2 (знятий та об'єднаний з Round5)
  • Round5 (об'єднаний з Round2 та Hila5, 4 серпня 2018 року)[11]
  • SABER
  • Three Bears
  • Titanium
На основі кодів
  • BIG QUAKE
  • BIKE
  • Класичний McEliece[en] + NTS-KEM
  • DAGS
  • Edon-K
  • HQC
  • LAKE (знятий та об'єднаний з ROLLO)
  • LEDAkem
  • LEDApkc
  • Lepton
  • LOCKER (знятий та об'єднаний з ROLLO)
  • McNie
  • NTS-KEM
  • ROLLO (об'єднаний з Ouroboros-R, LAKE та LOCKER)[14]
  • Ouroboros-R (знятий та об'єднаний з ROLLO)
  • QC-MDPC KEM
  • Ramstake
  • RLCE-KEM
  • RQC
  • pqsigRM
  • RaCoSS
  • RankSign
На основі хешів
  • Gravity-SPHINCS
  • SPHINCS+
Багатовимірні[en]
  • CFPKM
  • Giophantus
  • DualModeMS
  • GeMSS
  • Gui
  • HiMQ-3
  • LUOV
  • MQDSS
  • Rainbow
  • SRTPI
  • DME
На основі групи кіс
  • WalnutDSA
На основі ізогеній суперсингулярних еліптичних кривих
Гумористичні
Інші
  • Guess Again
  • HK17
  • Mersenne-756839
  • RVB
  • Picnic

Алгоритми, для яких знайшли вразливості під час першого раунду

[ред. | ред. код]

Другий раунд

[ред. | ред. код]

Кандидати, які пройшли до другого раунду, були оголошені 30 січня 2019 року.[33]

Тип PKE/KEM Цифровий підпис
На основі ґраток
  • CRYSTALS-Dilithium[34]
  • FALCON[40]
  • qTESLA
На основі кодів
  • BIKE[41]
  • Classic McEliece
  • HQC[42]
  • LEDAcrypt (об'єднання LEDAkem[43] та LEDApkc[44])
  • NTS-KEM[45]
  • ROLLO (об'єднання Ouroboros-R, LAKE та LOCKER)[14]
  • RQC[46]
На основі хешів
Багатовимірні
На основі ізогеній суперсингулярних еліптичних кривих
На основі доведення з нульовим розголошенням

Третій раунд

[ред. | ред. код]

22 липня 2020 року NIST оголосив сім фіналістів («перший трек»), а також вісім альтернативних алгоритмів («другий трек»). Перший трек містив алгоритми, які виглядали найбільш перспективними, та були розглянуті для стандартизації в кінці третього раунду. Алгоритми з другого треку все ще могли стати частиною стандарту після завершення третього раунду.[53] NIST розраховував, що деякі з альтернативних кандидатів будуть розглянуті в четвертому раунді.[54]

7-9 червня 2021 року NIST провів віртуально третю конференцію зі стандартизації постквантової криптографії. Конференція включала в себе презентації кандидатів та дискусії щодо впровадження, виконання та питань безпеки кандидатів. Увагу було приділено питанням інтелектуальної власності.[55]

Фіналісти

[ред. | ред. код]
Тип PKE/KEM Цифровий підпис
На основі ґраток
На основі кодів
Багатовимірні[en]

Альтернативні кандидати

[ред. | ред. код]
Тип PKE/KEM Цифровий підпис
На основі ґраток
  • FrodoKEM
  • NTRU Prime
На основі кодів
На основі хешів
  • SPHINCS+
Багатовимірні
  • GeMSS
На основі ізогеній суперсингулярних еліптичних кривих
На основі доведення з нульовим розголошенням
  • Picnic

Питання інтелектуальної власності

[ред. | ред. код]

Після оголошення фіналістів та альтернативних кандидатів було висловлено різні занепокоєння щодо інтелектуальної власності, зокрема, навколо схем на основі ґраток, таких як Kyber та NewHope. Хоч NIST має підписані заяви від груп, які брали участь у конкурсі, що вони відмовляються від будь-яких юридичних претензій, але все ще існують занепокоєння, що треті сторони можуть втрутитись. NIST заявив, що вони візьмуть до уваги такі міркування при виборі алгоритмів-переможців.[56]

Алгоритми, для яких знайшли вразливості під час третього раунду

[ред. | ред. код]
  • Rainbow (на класичному комп'ютері)[57]

Адаптації

[ред. | ред. код]

Під час цього раунду у наступних кандидатів виявили вразливості до певних атак, але їх виправили:

Перша група переможців

[ред. | ред. код]

5 липня 2022 року NIST оголосив першу групу переможців шестирічного конкурсу.[60][61]

Тип PKE/KEM Цифровий підпис
На основі ґраток
  • CRYSTALS-Kyber
На основі хешів

Четвертий раунд

[ред. | ред. код]

5 липня 2022 року NIST оголосив чотирьох кандидатів на участь у четвертому раунді стандартизації постквантової криптографії.[62]

Тип PKE/KEM
На основі кодів
На основі ізогеній суперсингулярних еліптичних кривих

Алгоритми, для яких знайшли вразливості під час четвертого раунду

[ред. | ред. код]
  • SIKE (на класичному комп'ютері)[64]

Перший випуск стандартів

[ред. | ред. код]

13 серпня 2024 року NIST випустив фінальні версії своїх перших трьох постквантових криптографічних стандартів.[5] Згідно з анонсом до релізу:

Хоча в порівнянні з чорновими версіями стандартів не було внесено суттєвих змін, NIST змінив назви алгоритмів, щоб вказати версії, які фігурують у трьох фіналізованих стандартах, а саме:

  • Федеральний стандарт обробки інформації (FIPS) 203, призначений як основний стандарт для загального шифрування. Серед його переваг — порівняно невеликі ключі шифрування, якими дві сторони можуть легко обмінюватися, а також швидкість роботи. В основі стандарту лежить алгоритм CRYSTALS-Kyber, який був перейменований на ML-KEM, скорочення від Module-Lattice-Based Key-Encapsulation Mechanism (Механізм інкапсуляції ключів на основі модулярної ґратки).
  • FIPS 204, призначений як основний стандарт для цифрових підписів. Стандарт використовує алгоритм CRYSTALS-Dilithium, який було перейменовано на ML-DSA, скорочення від Module-Lattice-Based Digital Signature Algorithm (Алгоритм цифрового підпису на основі модулярної ґратки).
  • FIPS 205, також призначений для цифрових підписів. Стандарт використовує алгоритм Sphincs+, який було перейменовано на SLH-DSA, скорочення від Stateless Hash-Based Digital Signature Algorithm. Стандарт базується на іншому математичному підході, ніж ML-DSA, і призначений як резервний метод на випадок, якщо ML-DSA виявиться вразливим.
  • Аналогічно, коли буде випущено стандарт FIPS 206, побудований на основі FALCON, алгоритм отримає назву FN-DSA, скорочення від FFT (швидке перетворення Фур'є) над NTRU-Lattice-Based Digital Signature Algorithm (Алгоритм цифрового підпису на основі NTRU-ґратки).

Додаткові схеми цифрового підпису

[ред. | ред. код]

У вересні 2022 року NIST оголосив про розгляд додаткових пропозицій в категорії цифрових підписів у процесі стандартизації постквантової криптографії, щоб урізноманітнити свій набір постквантових підписів.[65]

Перший раунд

[ред. | ред. код]

NIST отримав 50 заявок та визнав 40 з них відповідними до вимог участі.[66] На розгляді були такі алгоритми:[67]

Тип Цифровий підпис
На основі ґраток
На основі кодів
MPC-in-the-Head
Багатовимірні
  • 3WISE («Заявник погоджується з тим, що схема є вразливою, але вважає за краще не відкликати заявку в надії, що вивчення схеми сприятиме розвитку криптоаналізу»[84])
  • Biscuit[85]
  • DME-Sign («Наше перше враження — атака працює, і ми перевіряємо деталі атаки. Ми працюємо над варіантом DME, який може протистояти атаці, але ми повинні перевірити його.»[86])
  • HPPC
  • MAYO[87]
  • PROV[88]
  • QR-UOV[89]
  • SNOVA[90]
  • TUOV[91]
  • UOV[92]
  • VOX[93]
На основі ізогеній суперсингулярних еліптичних кривих
На основі симетрій
  • AIMer[95]
  • Ascon-Sign
  • FAEST[96]
  • SPHINCS-alpha
Інші
  • ALTEQ[97]
  • eMLE-Sig 2.0
  • KAZ-SIGN
  • Preon
  • Xifrat1-Sign.I

Алгоритми, для яких знайшли вразливості під час першого раунду

[ред. | ред. код]

Другий раунд

[ред. | ред. код]

Кандидати, які пройшли до другого раунду, були оголошені 24 жовтня 2024 року.[124]

Тип Цифровий підпис
На основі ґраток
  • HAWK
На основі кодів
MPC-in-the-Head
Багатовимірні
На основі ізогеній суперсингулярних еліптичних кривих
На основі симетрій

Примітки

[ред. | ред. код]
  1. Post-Quantum Cryptography PQC. 3 січня 2017.
  2. Post-Quantum Cryptography Standardization – Post-Quantum Cryptography. Csrc.nist.gov. 3 січня 2017.
  3. Moody, Dustin (24 листопада 2020). The Future Is Now: Spreading the Word About Post-Quantum Cryptography. NIST.
  4. Final Submission received. Архів оригіналу за 29 грудня 2017.
  5. а б NIST Releases First 3 Finalized Post-Quantum Encryption Standards, NIST, August 13, 2024
  6. Hong, Zhu (2001). Survey of Computational Assumptions Used in Cryptography Broken or Not by Shor's Algorithm (PDF).
  7. NIST Released NISTIR 8105, Report on Post-Quantum Cryptography. 21 грудня 2016.
  8. NIST Asks Public to Help Future-Proof Electronic Information. NIST. 20 грудня 2016.
  9. Computer Security Division, Information Technology Laboratory (3 січня 2017). Round 1 Submissions – Post-Quantum Cryptography – CSRC. Csrc.nist.gov.
  10. а б в NIST Post Quantum Crypto Submission. Архів оригіналу за 29 грудня 2017.
  11. а б Google Groups. Groups.google.com.
  12. qTESLA team. Efficient and post-quantum secure lattice-based signature scheme. qTESLA.org. Архів оригіналу за 9 грудня 2023.
  13. qTESLA. Microsoft Research (амер.). Архів оригіналу за 31 грудня 2022.
  14. а б ROLLO. Pqc-rollo.org.
  15. RSA з використанням 231 4096-бітових ключів із загальним розміром ключа 1 ТіБ. «Ключ ледве вміщається на жорсткому диску» Bernstein, Daniel (28 травня 2010). McBits and Post-Quantum RSA (PDF).
  16. Bernstein, Daniel; Heninger, Nadia (19 квітня 2017). Post-quantum RSA (PDF).
  17. 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.
  18. Panny, Lorenz [@yx7__] (25 грудня 2017). Fast key recovery attack against the "RVB" submission to #NISTPQC: t .... Computes private from public key (Твіт) — через Твіттер.
  19. Comments on RaCoSS. Архів оригіналу за 26 грудня 2017.
  20. Comments on HK17. Архів оригіналу за 5 січня 2018.
  21. Dear all, We have broken SRTPI under CPA and TPSig under KMA (PDF). Csrc.nist.gov.
  22. Beullens, Ward; Blackburn, Simon R. (2018). Practical attacks against the Walnut digital signature scheme. Cryptology ePrint Archive.
  23. Kotov, Matvei; Menshov, Anton; Ushakov, Alexander (2018). An attack on the walnut digital signature algorithm. Cryptology ePrint Archive.
  24. Yu, Yang; Ducas, Léo (2018). Learning strikes again: the case of the DRS signature scheme. Cryptology ePrint Archive.
  25. Barelli, Elise; Couvreur, Alain (2018). An efficient structural attack on NIST submission DAGS. arXiv:1805.05429 [cs.CR].
  26. Lequesne, Matthieu; Tillich, Jean-Pierre (2018). Attack on the Edon-K Key Encapsulation Mechanism. arXiv:1802.06157 [cs.CR].
  27. Couvreur, Alain; Lequesne, Matthieu; Tillich, Jean-Pierre (2018). Recovering short secret keys of RLCE in polynomial time. arXiv:1805.11489 [cs.CR].
  28. Bernstein, Daniel J.; Groot Bruinderink, Leon; Lange, Tanja; Lange, Lorenz (2017). Hila5 Pindakaas: On the CCA security of lattice-based encryption with error correction. Cryptology ePrint Archive.
  29. Official Comments (PDF). Csrc.nist.gov. 13 вересня 2018.
  30. 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].
  31. 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.
  32. Lau, Terry Shue Chien; Tan, Chik How (31 січня 2019). Key Recovery Attack on McNie Based on Low Rank Parity Check Codes and Its Reparation. У Inomata, Atsuo; Yasuda, Kan (ред.). Advances in Information and Computer Security. Lecture Notes in Computer Science. Т. 11049. Springer International Publishing. с. 19—34. doi:10.1007/978-3-319-97916-8_2. ISBN 978-3-319-97915-1.
  33. Computer Security Division, Information Technology Laboratory (3 січня 2017). Round 2 Submissions – Post-Quantum Cryptography – CSRC. Csrc.nist.gov.
  34. а б Schwabe, Peter. CRYSTALS. Pq-crystals.org.
  35. FrodoKEM. Frodokem.org.
  36. Schwabe, Peter. NewHope. Newhopecrypto.org.
  37. NTRU Prime: Intro. Архів оригіналу за 1 вересня 2019.
  38. SABER.
  39. ThreeBears. SourceForge.net.
  40. Falcon. Falcon.
  41. BIKE – Bit Flipping Key Encapsulation. Bikesuite.org.
  42. HQC. Pqc-hqc.org.
  43. LEDAkem Key Encapsulation Module. Ledacrypt.org.
  44. LEDApkc Public Key Cryptosystem. Ledacrypt.org.
  45. NTS-Kem. Архів оригіналу за 29 грудня 2017.
  46. RQC. Pqc-rqc.org.
  47. Sphincs. Sphincs.org.
  48. GeMSS. Архів оригіналу за 31 січня 2019.
  49. LUOV -- An MQ signature scheme.
  50. MQDSS post-quantum signature. Mqdss.org.
  51. SIKE – Supersingular Isogeny Key Encapsulation. Sike.org.
  52. Picnic. A Family of Post-Quantum Secure Digital Signature Algorithms. microsoft.github.io.
  53. 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.
  54. Third PQC Standardization Conference - Session I Welcome/Candidate Updates (англ.), 10 червня 2021
  55. Computer Security Division, Information Technology Laboratory (10 лютого 2021). Third PQC Standardization Conference | CSRC. CSRC | NIST (англ.).
  56. Submission Requirements and Evaluation Criteria (PDF).
  57. Beullens, Ward (2022). Breaking Rainbow Takes a Weekend on a Laptop (PDF). Eprint.iacr.org.
  58. Grubbs, Paul; Maram, Varun; Paterson, Kenneth G. (2021). Anonymous, Robust Post-Quantum Public Key Encryption. Cryptology ePrint Archive.
  59. Karabulut, Emre; Aysu, Aydin (2021). Falcon Down: Breaking Falcon Post-Quantum Signature Scheme through Side-Channel Attacks. Cryptology ePrint Archive.
  60. NIST Announces First Four Quantum-Resistant Cryptographic Algorithms. NIST (англ.). 5 липня 2022.
  61. Selected Algorithms 2022. CSRC | NIST (англ.). 5 липня 2022.
  62. Round 4 Submissions. CSRC | NIST (англ.). 5 липня 2022.
  63. SIKE Team - Foreword and postscript (PDF).
  64. Goodin, Dan (2 серпня 2022). Post-quantum encryption contender is taken out by single-core PC and 1 hour. Ars Technica.
  65. Request for Additional Digital Signature Schemes for the Post-Quantum Cryptography Standardization Process. csrc.nist.gov. 6 вересня 2022.
  66. Moody, Dustin (17 липня 2023). Onramp submissions are posted!.
  67. Digital Signature Schemes. csrc.nist.gov. 29 серпня 2022.
  68. SMAUG & HAETAE - HAETAE.
  69. Hufu.
  70. RACCOON – Not just a signature, a whole family of it !.
  71. masksign/raccoon: Raccoon Signature Scheme -- Reference Code. GitHub.
  72. Squirrels - Introduction.
  73. CROSS crypto.
  74. FuLeeca: A Lee-based Signature Scheme - Lehrstuhl für Nachrichtentechnik.
  75. LESS project.
  76. MEDS.
  77. WAVE.
  78. MIRA.
  79. MiRitH.
  80. MQOM.
  81. PERK.
  82. RYDE.
  83. SD-in-the-Head.
  84. а б Smith-Tone, Daniel (17 липня 2023). OFFICIAL COMMENT: 3WISE.
  85. Home.
  86. OFFICIAL COMMENT: DME Key Recovery Attack. groups.google.com.
  87. MAYO.
  88. PROV.
  89. QR-UOV.
  90. SNOVA. snova.pqclab.org.
  91. TUOV.
  92. UOV.
  93. VOX.
  94. SQIsign.
  95. AIMer Signature.
  96. Come and join the FAEST | FAEST Signature Algorithm.
  97. ALTEQ.
  98. Tibouchi, Mehdi (17 липня 2023). Round 1 (Additional Signatures) OFFICIAL COMMENT: EagleSign.
  99. Bernstein, D.J. (17 липня 2023). OFFICIAL COMMENT: KAZ-SIGN.
  100. Fluhrer, Scott (17 липня 2023). KAZ-SIGN.
  101. Panny, Lorenz (17 липня 2023). Round 1 (Additional Signatures) OFFICIAL COMMENT: Xifrat1-Sign.I.
  102. Tibouchi, Mehdi (18 липня 2023). Round 1 (Additional Signatures) OFFICIAL COMMENT: EagleSign.
  103. Beullens, Ward (18 липня 2023). Round 1 (Additional Signatures) OFFICIAL COMMENT: HPPC.
  104. Perlner, Ray (21 липня 2023). Round 1 (Additional Signatures) OFFICIAL COMMENT: HPPC.
  105. Saarinen, Markku-Juhani O. (18 липня 2023). OFFICIAL COMMENT: ALTEQ.
  106. Bouillaguet, Charles (19 липня 2023). Round 1 (Additional Signatures) OFFICIAL COMMENT: Biscuit.
  107. Niederhagen, Ruben (19 липня 2023). Round 1 (Additional Signatures) OFFICIAL COMMENT: MEDS.
  108. van Woerden, Wessel (20 липня 2023). Round 1 (Additional Signatures) OFFICIAL COMMENT: FuLeeca.
  109. Persichetti, Edoardo (21 липня 2023). OFFICIAL COMMENT: LESS.
  110. Saarinen, Markku-Juhani O. Round 1 (Additional Signatures) OFFICIAL COMMENT: DME-Sign.
  111. OFFICIAL COMMENT: DME Key Recovery Attack. groups.google.com.
  112. van Woerden, Wessel (Jul 25, 2023). Round 1 (Additional Signatures) OFFICIAL COMMENT: EHTv3.
  113. Suhl, Adam (Jul 29, 2023). Round 1 (Additional Signatures) OFFICIAL COMMENT: EHT.
  114. VASSEUR, Valentin (Jul 29, 2023). Round 1 (Additional Signatures) OFFICIAL COMMENT: Enhanced pqsigRM.
  115. Round 1 (Additional Signatures) OFFICIAL COMMENT: Enhanced pqsigRM. groups.google.com.
  116. Saarinen, Markku-Juhani O. (Jul 27, 2023). Buffer overflows in HAETAE / On crypto vs implementation errors.
  117. Saarinen, Markku-Juhani O. (Jul 29, 2023). HuFu: Big-flipping forgeries and buffer overflows.
  118. Carrier, Kevin (Aug 3, 2023). Round 1 (Additional Signatures) OFFICIAL COMMENT: SDitH.
  119. Carrier, Kevin; Hatey, Valérian; Tillich, Jean-Pierre (5 Dec 2023). Projective Space Stern Decoding and Application to SDitH. arXiv:2312.02607 [cs.IT].
  120. Furue, Hiroki (Aug 28, 2023). Round 1 (Additional Signatures) OFFICIAL COMMENT: VOX.
  121. Liu, Fukang; Mahzoun, Mohammad; Øygarden, Morten; Meier, Willi (10 листопада 2023). Algebraic Attacks on RAIN and AIM Using Equivalent Representations. IACR ePrint (2023/1133).
  122. Ikematsu, Yasuhiko; Akiyama, Rika (2024), Revisiting the security analysis of SNOVA
  123. Ferreira, River Moreira; Perret, Ludovic (2024), Polynomial-Time Key-Recovery Attack on the ${\tt NIST}$ Specification of ${\tt PROV}$
  124. Moody, Dustin (24 жовтня 2024). Status Report on the First Round of the Additional Digital Signature Schemes for the NIST Post-Quantum Cryptography Standardization Process.
  125. CROSS crypto.
  126. LESS project.
  127. Mirath.
  128. MQOM.
  129. PERK.
  130. RYDE.
  131. SD-in-the-Head.
  132. MAYO.
  133. QR-UOV.
  134. SNOVA. snova.pqclab.org.
  135. UOV.
  136. SQIsign.
  137. Come and join the FAEST | FAEST Signature Algorithm.

Посилання

[ред. | ред. код]