Стандартизація постквантової криптографії 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] |
|---|---|---|---|
| На основі ґраток |
|
||
| На основі кодів |
|
|
|
| На основі хешів |
|
||
| Багатовимірні[en] |
|
|
|
| На основі групи кіс |
|
||
| На основі ізогеній суперсингулярних еліптичних кривих | |||
| Інші |
|
|
- Guess Again[17]
- RVB[18]
- RaCoSS[19]
- HK17[20]
- SRTPI[21]
- WalnutDSA[22][23]
- DRS[24]
- DAGS[25]
- Edon-K[26]
- RLCE[27]
- Hila5[28]
- Giophantus[29]
- RankSign[30]
- McNie[31][32]
Кандидати, які пройшли до другого раунду, були оголошені 30 січня 2019 року.[33]
| Тип | PKE/KEM | Цифровий підпис |
|---|---|---|
| На основі ґраток | ||
| На основі кодів | ||
| На основі хешів |
| |
| Багатовимірні | ||
| На основі ізогеній суперсингулярних еліптичних кривих |
|
|
| На основі доведення з нульовим розголошенням |
|
22 липня 2020 року NIST оголосив сім фіналістів («перший трек»), а також вісім альтернативних алгоритмів («другий трек»). Перший трек містив алгоритми, які виглядали найбільш перспективними, та були розглянуті для стандартизації в кінці третього раунду. Алгоритми з другого треку все ще могли стати частиною стандарту після завершення третього раунду.[53] NIST розраховував, що деякі з альтернативних кандидатів будуть розглянуті в четвертому раунді.[54]
7-9 червня 2021 року NIST провів віртуально третю конференцію зі стандартизації постквантової криптографії. Конференція включала в себе презентації кандидатів та дискусії щодо впровадження, виконання та питань безпеки кандидатів. Увагу було приділено питанням інтелектуальної власності.[55]
| Тип | PKE/KEM | Цифровий підпис |
|---|---|---|
| На основі ґраток | ||
| На основі кодів | ||
| Багатовимірні[en] |
| Тип | PKE/KEM | Цифровий підпис |
|---|---|---|
| На основі ґраток |
|
|
| На основі кодів | ||
| На основі хешів |
| |
| Багатовимірні |
| |
| На основі ізогеній суперсингулярних еліптичних кривих | ||
| На основі доведення з нульовим розголошенням |
|
Після оголошення фіналістів та альтернативних кандидатів було висловлено різні занепокоєння щодо інтелектуальної власності, зокрема, навколо схем на основі ґраток, таких як Kyber та NewHope. Хоч NIST має підписані заяви від груп, які брали участь у конкурсі, що вони відмовляються від будь-яких юридичних претензій, але все ще існують занепокоєння, що треті сторони можуть втрутитись. NIST заявив, що вони візьмуть до уваги такі міркування при виборі алгоритмів-переможців.[56]
- Rainbow (на класичному комп'ютері)[57]
Під час цього раунду у наступних кандидатів виявили вразливості до певних атак, але їх виправили:
5 липня 2022 року NIST оголосив першу групу переможців шестирічного конкурсу.[60][61]
| Тип | PKE/KEM | Цифровий підпис |
|---|---|---|
| На основі ґраток |
|
|
| На основі хешів |
5 липня 2022 року NIST оголосив чотирьох кандидатів на участь у четвертому раунді стандартизації постквантової криптографії.[62]
| Тип | PKE/KEM |
|---|---|
| На основі кодів | |
| На основі ізогеній суперсингулярних еліптичних кривих |
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 оголосив про розгляд додаткових пропозицій в категорії цифрових підписів у процесі стандартизації постквантової криптографії, щоб урізноманітнити свій набір постквантових підписів.[66]
NIST отримав 50 заявок та визнав 40 з них відповідними до вимог участі.[67] На розгляді були такі алгоритми:[68]
| Тип | Цифровий підпис |
|---|---|
| На основі ґраток | |
| На основі кодів | |
| MPC-in-the-Head | |
| Багатовимірні |
|
| На основі ізогеній суперсингулярних еліптичних кривих | |
| На основі симетрій |
|
| Інші |
|
- 3WISE[80]
- EagleSign[88]
- KAZ-SIGN[89][90]
- Xifrat1-Sign.I[91]
- eMLE-Sig 2.0[92]
- HPPC[93][94]
- ALTEQ[95]
- Biscuit[96]
- MEDS[97]
- FuLeeca[98]
- LESS[99]
- DME-Sign[100][101]
- EHTv3[102][103]
- Удосконалений pqsigRM[104][105]
- HAETAE[106]
- HuFu[107]
- SDitH[108][109]
- VOX[110]
- AIMer[111]
- SNOVA[112]
- PROV[113]
Кандидати, які пройшли до другого раунду, були оголошені 24 жовтня 2024 року.[114]
| Тип | Цифровий підпис |
|---|---|
| На основі ґраток |
|
| На основі кодів | |
| MPC-in-the-Head | |
| Багатовимірні | |
| На основі ізогеній суперсингулярних еліптичних кривих |
|
| На основі симетрій |
|
- ↑ Post-Quantum Cryptography PQC. 3 січня 2017.
- ↑ Post-Quantum Cryptography Standardization – Post-Quantum Cryptography. Csrc.nist.gov. 3 січня 2017.
- ↑ Moody, Dustin (24 листопада 2020). The Future Is Now: Spreading the Word About Post-Quantum Cryptography. NIST.
- ↑ Final Submission received. Архів оригіналу за 29 грудня 2017.
- ↑ а б NIST Releases First 3 Finalized Post-Quantum Encryption Standards, NIST, August 13, 2024
- ↑ Hong, Zhu (2001). Survey of Computational Assumptions Used in Cryptography Broken or Not by Shor's Algorithm (PDF).
- ↑ NIST Released NISTIR 8105, Report on Post-Quantum Cryptography. 21 грудня 2016.
- ↑ NIST Asks Public to Help Future-Proof Electronic Information. NIST. 20 грудня 2016.
- ↑ Computer Security Division, Information Technology Laboratory (3 січня 2017). Round 1 Submissions – Post-Quantum Cryptography – CSRC. Csrc.nist.gov. Архів оригіналу за 24 червня 2022.
- ↑ а б в NIST Post Quantum Crypto Submission. Архів оригіналу за 29 грудня 2017.
- ↑ а б Google Groups. Groups.google.com.
- ↑ qTESLA team. Efficient and post-quantum secure lattice-based signature scheme. qTESLA.org. Архів оригіналу за 9 грудня 2023.
- ↑ qTESLA. Microsoft Research (амер.). Архів оригіналу за 31 грудня 2022.
- ↑ а б ROLLO. Pqc-rollo.org.
- ↑ RSA з використанням 231 4096-бітових ключів із загальним розміром ключа 1 ТіБ. «Ключ ледве вміщається на жорсткому диску» Bernstein, Daniel (28 травня 2010). McBits and Post-Quantum RSA (PDF).
- ↑ Bernstein, Daniel; Heninger, Nadia (19 квітня 2017). Post-quantum RSA (PDF).
- ↑ 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.
- ↑ Panny, Lorenz [@yx7__] (25 грудня 2017). Fast key recovery attack against the "RVB" submission to #NISTPQC: t .... Computes private from public key (Твіт) — через Твіттер.
- ↑ Comments on RaCoSS. Архів оригіналу за 26 грудня 2017.
- ↑ Comments on HK17. Архів оригіналу за 5 січня 2018.
- ↑ Dear all, We have broken SRTPI under CPA and TPSig under KMA (PDF). Csrc.nist.gov.
- ↑ Beullens, Ward; Blackburn, Simon R. (2018). Practical attacks against the Walnut digital signature scheme. Cryptology ePrint Archive.
- ↑ Kotov, Matvei; Menshov, Anton; Ushakov, Alexander (2018). An attack on the walnut digital signature algorithm. Cryptology ePrint Archive.
- ↑ Yu, Yang; Ducas, Léo (2018). Learning strikes again: the case of the DRS signature scheme. Cryptology ePrint Archive.
- ↑ Barelli, Elise; Couvreur, Alain (2018). An efficient structural attack on NIST submission DAGS. arXiv:1805.05429 [cs.CR].
- ↑ Lequesne, Matthieu; Tillich, Jean-Pierre (2018). Attack on the Edon-K Key Encapsulation Mechanism. arXiv:1802.06157 [cs.CR].
- ↑ Couvreur, Alain; Lequesne, Matthieu; Tillich, Jean-Pierre (2018). Recovering short secret keys of RLCE in polynomial time. arXiv:1805.11489 [cs.CR].
- ↑ 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.
- ↑ Official Comments (PDF). Csrc.nist.gov. 13 вересня 2018.
- ↑ 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].
- ↑ 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.
- ↑ 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.
- ↑ Computer Security Division, Information Technology Laboratory (3 січня 2017). Round 2 Submissions – Post-Quantum Cryptography – CSRC. Csrc.nist.gov.
- ↑ а б Schwabe, Peter. CRYSTALS. Pq-crystals.org.
- ↑ FrodoKEM. Frodokem.org.
- ↑ Schwabe, Peter. NewHope. Newhopecrypto.org.
- ↑ NTRU Prime: Intro. Архів оригіналу за 1 вересня 2019.
- ↑ SABER.
- ↑ ThreeBears. SourceForge.net.
- ↑ Falcon. Falcon.
- ↑ BIKE – Bit Flipping Key Encapsulation. Bikesuite.org.
- ↑ HQC. Pqc-hqc.org.
- ↑ LEDAkem Key Encapsulation Module. Ledacrypt.org.
- ↑ LEDApkc Public Key Cryptosystem. Ledacrypt.org.
- ↑ NTS-Kem. Архів оригіналу за 29 грудня 2017.
- ↑ RQC. Pqc-rqc.org.
- ↑ Sphincs. Sphincs.org.
- ↑ GeMSS. Архів оригіналу за 31 січня 2019.
- ↑ LUOV -- An MQ signature scheme.
- ↑ MQDSS post-quantum signature. Mqdss.org.
- ↑ SIKE – Supersingular Isogeny Key Encapsulation. Sike.org.
- ↑ Picnic. A Family of Post-Quantum Secure Digital Signature Algorithms. microsoft.github.io.
- ↑ 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.
- ↑ Third PQC Standardization Conference - Session I Welcome/Candidate Updates (англ.), 10 червня 2021
- ↑ Computer Security Division, Information Technology Laboratory (10 лютого 2021). Third PQC Standardization Conference | CSRC. CSRC | NIST (англ.).
- ↑ Submission Requirements and Evaluation Criteria (PDF).
- ↑ Beullens, Ward (2022). Breaking Rainbow Takes a Weekend on a Laptop (PDF). Eprint.iacr.org.
- ↑ Grubbs, Paul; Maram, Varun; Paterson, Kenneth G. (2021). Anonymous, Robust Post-Quantum Public Key Encryption. Cryptology ePrint Archive.
- ↑ Karabulut, Emre; Aysu, Aydin (2021). Falcon Down: Breaking Falcon Post-Quantum Signature Scheme through Side-Channel Attacks. Cryptology ePrint Archive.
- ↑ NIST Announces First Four Quantum-Resistant Cryptographic Algorithms. NIST (англ.). 5 липня 2022.
- ↑ Selected Algorithms 2022. CSRC | NIST (англ.). 5 липня 2022.
- ↑ Round 4 Submissions. CSRC | NIST (англ.). 5 липня 2022.
- ↑ SIKE Team - Foreword and postscript (PDF).
- ↑ Goodin, Dan (2 серпня 2022). Post-quantum encryption contender is taken out by single-core PC and 1 hour. Ars Technica.
- ↑ Status Report on the Fourth Round of the NIST Post-Quantum Cryptography Standardization Process (PDF). nvlpubs.nist.gov.
- ↑ Request for Additional Digital Signature Schemes for the Post-Quantum Cryptography Standardization Process. csrc.nist.gov. 6 вересня 2022.
- ↑ Moody, Dustin (17 липня 2023). Onramp submissions are posted!.
- ↑ Digital Signature Schemes. csrc.nist.gov. 29 серпня 2022.
- ↑ SMAUG-T & HAETAE - HAETAE. kpqc.cryptolab.co.kr.
- ↑ Hufu.
- ↑ RACCOON – Not just a signature, a whole family of it !.
- ↑ masksign/raccoon: Raccoon Signature Scheme -- Reference Code. GitHub.
- ↑ Squirrels - Introduction. www.squirrels-pqc.org.
- ↑ CROSS crypto.
- ↑ FuLeeca: A Lee-based Signature Scheme. www.ce.cit.tum.de.
- ↑ MEDS. www.meds-pqc.org.
- ↑ Macan33 – Link Akses Gudang Jackpot Perkalian 500 & 1000. Macan33.
- ↑ MIRA. pqc-mira.org.
- ↑ MIRITH. pqc-mirith.org.
- ↑ а б Smith-Tone, Daniel (17 липня 2023). OFFICIAL COMMENT: 3WISE.
- ↑ Home. www.biscuit-pqc.org.
- ↑ OFFICIAL COMMENT: DME Key Recovery Attack. groups.google.com.
- ↑ PROV. prov-sign.github.io.
- ↑ SOFTAX - News That Connects, Informs, and Empowers.
- ↑ VOX. vox-sign.com.
- ↑ AIMer Signature. aimer-signature.org.
- ↑ ALTEQ. pqcalteq.github.io.
- ↑ Tibouchi, Mehdi (17 липня 2023). Round 1 (Additional Signatures) OFFICIAL COMMENT: EagleSign.
- ↑ Bernstein, D.J. (17 липня 2023). OFFICIAL COMMENT: KAZ-SIGN.
- ↑ Fluhrer, Scott (17 липня 2023). KAZ-SIGN.
- ↑ Panny, Lorenz (17 липня 2023). Round 1 (Additional Signatures) OFFICIAL COMMENT: Xifrat1-Sign.I.
- ↑ Tibouchi, Mehdi (18 липня 2023). Round 1 (Additional Signatures) OFFICIAL COMMENT: EagleSign.
- ↑ Beullens, Ward (18 липня 2023). Round 1 (Additional Signatures) OFFICIAL COMMENT: HPPC.
- ↑ Perlner, Ray (21 липня 2023). Round 1 (Additional Signatures) OFFICIAL COMMENT: HPPC.
- ↑ Saarinen, Markku-Juhani O. (18 липня 2023). OFFICIAL COMMENT: ALTEQ.
- ↑ Bouillaguet, Charles (19 липня 2023). Round 1 (Additional Signatures) OFFICIAL COMMENT: Biscuit.
- ↑ Niederhagen, Ruben (19 липня 2023). Round 1 (Additional Signatures) OFFICIAL COMMENT: MEDS.
- ↑ van Woerden, Wessel (20 липня 2023). Round 1 (Additional Signatures) OFFICIAL COMMENT: FuLeeca.
- ↑ Persichetti, Edoardo (21 липня 2023). OFFICIAL COMMENT: LESS.
- ↑ Saarinen, Markku-Juhani O. Round 1 (Additional Signatures) OFFICIAL COMMENT: DME-Sign.
- ↑ OFFICIAL COMMENT: DME Key Recovery Attack. groups.google.com.
- ↑ van Woerden, Wessel (Jul 25, 2023). Round 1 (Additional Signatures) OFFICIAL COMMENT: EHTv3.
- ↑ Suhl, Adam (Jul 29, 2023). Round 1 (Additional Signatures) OFFICIAL COMMENT: EHT.
- ↑ VASSEUR, Valentin (Jul 29, 2023). Round 1 (Additional Signatures) OFFICIAL COMMENT: Enhanced pqsigRM.
- ↑ Round 1 (Additional Signatures) OFFICIAL COMMENT: Enhanced pqsigRM. groups.google.com.
- ↑ Saarinen, Markku-Juhani O. (Jul 27, 2023). Buffer overflows in HAETAE / On crypto vs implementation errors.
- ↑ Saarinen, Markku-Juhani O. (Jul 29, 2023). HuFu: Big-flipping forgeries and buffer overflows.
- ↑ Carrier, Kevin (Aug 3, 2023). Round 1 (Additional Signatures) OFFICIAL COMMENT: SDitH.
- ↑ Carrier, Kevin; Hatey, Valérian; Tillich, Jean-Pierre (5 Dec 2023). Projective Space Stern Decoding and Application to SDitH. arXiv:2312.02607 [cs.IT].
- ↑ Furue, Hiroki (Aug 28, 2023). Round 1 (Additional Signatures) OFFICIAL COMMENT: VOX.
- ↑ Liu, Fukang; Mahzoun, Mohammad; Øygarden, Morten; Meier, Willi (10 листопада 2023). Algebraic Attacks on RAIN and AIM Using Equivalent Representations. IACR ePrint (2023/1133).
- ↑ Ikematsu, Yasuhiko; Akiyama, Rika (2024), Revisiting the security analysis of SNOVA
- ↑ Ferreira, River Moreira; Perret, Ludovic (2024), Polynomial-Time Key-Recovery Attack on the ${\tt NIST}$ Specification of ${\tt PROV}$
- ↑ Moody, Dustin (24 жовтня 2024). Status Report on the First Round of the Additional Digital Signature Schemes for the NIST Post-Quantum Cryptography Standardization Process. doi:10.6028/NIST.IR.8528.
- ↑ Hawk. hawk-sign.info.
- ↑ CROSS crypto. cross-crypto.com.
- ↑ LESS project. LESS project.
- ↑ Mirath. pqc-mirath.org.
- ↑ MQOM. www.mqom.org.
- ↑ PERK. pqc-perk.org.
- ↑ RYDE. pqc-ryde.org.
- ↑ SD-in-the-Head. sdith.org.
- ↑ MAYO. pqmayo.org.
- ↑ QR-UOV.
- ↑ SNOVA. snova.pqclab.org.
- ↑ UOV. www.uovsig.org.
- ↑ SQIsign. sqisign.org.
- ↑ Team, FAEST. Come and join the FAEST. FAEST Signature Algorithm.