Standaryzacja kryptografii postkwantowej NIST

Standaryzacja kryptografii postkwantowej to program i konkurs NIST mający na celu aktualizację ich standardów w celu uwzględnienia kryptografii postkwantowej . Zostało to ogłoszone na targach PQCrypto 2016. 23 schematy podpisu i 59 schematów szyfrowania/ KEM zostały przesłane przed pierwotnym terminem składania wniosków pod koniec 2017 r., z czego łącznie 69 uznano za kompletne i prawidłowe i wzięło udział w pierwszej rundzie. Siedem z nich, z czego 3 to schematy podpisów, przeszło do trzeciej rundy, która została ogłoszona 22 lipca 2020 r.

Tło

Badania naukowe nad potencjalnym wpływem obliczeń kwantowych sięgają co najmniej 2001 roku. Raport opublikowany przez NIST z kwietnia 2016 roku cytuje ekspertów, którzy uznają, że technologia kwantowa może sprawić, że powszechnie stosowany algorytm RSA stanie się niebezpieczny do 2030 roku. W rezultacie potrzeba dążono do standaryzacji kwantowo-bezpiecznych prymitywów kryptograficznych. Ponieważ większość prymitywów symetrycznych jest stosunkowo łatwa do zmodyfikowania w sposób, który czyni je odpornymi na kwant, wysiłki skupiły się na kryptografii klucza publicznego, a mianowicie na podpisach cyfrowych i mechanizmach enkapsulacji klucza . W grudniu 2016 r. NIST zainicjował proces standaryzacji, ogłaszając nabór wniosków.

Konkurs jest teraz w trzeciej rundzie z oczekiwanych czterech, w której w każdej rundzie niektóre algorytmy są odrzucane, a inne są dokładniej badane. NIST ma nadzieję opublikować dokumenty standaryzacyjne do 2024 r., ale może przyspieszyć ten proces, jeśli dokonane zostaną znaczące przełomy w komputerach kwantowych .

Obecnie nie zdecydowano, czy przyszłe standardy zostaną opublikowane jako FIPS , czy jako NIST Special Publication (SP).

Runda pierwsza

Rozważane były: ( przekreślenie oznacza, że ​​zostało wycofane)

Typ	PKE/ KEM	Podpis	Podpis i PKE/KEM
Krata	Kompaktowy LWE KRYSZTAŁY-Kyber Wymiana kluczy Ding EMBLEM i R.EMBLEM FrodoKEM HILA5 (wycofany i połączony z Round5) KCL (pka OKCN/AKCN/CNKE) KINDI GUMILAKA LIMA Jaszczurka LOTOS Nowa nadzieja NTRUSzyfruj NTRU-HRSS-KEM NTRU Prime Dziwny Manhattan Runda 2 (wycofana i połączona z Rundą 5) Round5 (fuzja Round2 i Hila5, ogłoszona 4 sierpnia 2018 r.) SZABLA trzy niedźwiedzie Tytan	KRYSZTAŁY-Dilithium DRS SOKÓŁ pqNTRUSign qTESLA
Oparte na kodzie	WIELKIE TRZPIENIE ROWER Klasyczny McEliece + NTS- KEM DAGS Edon-K HQC LAKE (wycofane i połączone w ROLLO) LEDAkem LEDApkc Lepton LOCKER (wycofany i połączony z ROLLO) McNie NTS-KEM ROLLO (fuzja Ouroboros-R, LAKE i LOCKER) Ouroboros-R (wycofany i połączony z ROLLO) QC-MDPC KEM Ramstake RLCE-KEM RQC	pqsigRM RaCoSS Znak rangi
Oparte na haszu		Grawitacja-SPHINCS SPINKI+
Wielowymiarowe	CFPKM Giofant	Podwójny tryb MS GeMSS Gui HiMQ-3 LUOW MQDSS Tęcza	SRTPI DME
Grupa warkoczy		Orzech DSA
Supersingular izogeneza krzywej eliptycznej	SIKE
Poddanie satyryczne			pq RSA
Inny	Zgadnij jeszcze raz HK17 Mersenne-756839 RVB	Piknik

Zgłoszenia w pierwszej rundzie opublikowane ataki

• Zgadnij ponownie Lorenz Panny
• RVB autorstwa Lorenza Panny'ego
• RaCoSS autorstwa Daniela J. Bernsteina , Andreasa Hülsinga, Tanji Lange i Lorenza Panny'ego
• HK17 autorstwa Daniela J. Bernsteina i Tanji Lange
• SRTPI autorstwa Bo-Yin Yang
• Orzech DSA
  • autorstwa Warda Beullensa i Simona R. Blackburna
  • przez Matwieja Kotowa, Antona Mieńszowa i Aleksandra Uszakowa
• DRS autorstwa Yang Yu i Léo Ducasa
• DAGS autorstwa Elise Barelli i Alaina Couvreur
• Edon-K autorstwa Matthieu Lequesne'a i Jean-Pierre'a Tillicha
• RLCE autorstwa Alaina Couvreur, Matthieu Lequesne i Jean-Pierre'a Tillicha
• Hila5 autorstwa Daniela J. Bernsteina, Leona Groota Bruinderinka, Tanji Lange i Lorenza Panny'ego
• Giophantus autorstwa Warda Beullensa, Woutera Castrycka i Frederika Vercauterena
• RankSign autorstwa Thomasa Debrisa-Alazarda i Jean-Pierre'a Tillicha
• McNie autorstwa Philippe'a Gaborita; Terry Shue Chien Lau i Chik How Tan

Runda druga

Kandydatów przechodzących do drugiej tury ogłoszono 30 stycznia 2019 r. Są to:

Typ	PKE/KEM	Podpis
Krata	KRYSZTAŁY-Kyber FrodoKEM GUMILAKA Nowa nadzieja NTRU (fuzja NTRUEncrypt i NTRU-HRSS-KEM) NTRU Prime Round5 (fuzja Round2 i Hila5, ogłoszona 4 sierpnia 2018 r.) SZABLA trzy niedźwiedzie	KRYSZTAŁY-Dilithium SOKÓŁ qTESLA
Oparte na kodzie	ROWER Klasyczny McEliece HQC LEDAcrypt (fuzja LEDAkem i LEDApkc) NTS-KEM ROLLO (fuzja Ouroboros-R, LAKE i LOCKER) RQC
Oparte na haszu		SPINKI+
Wielowymiarowe		GeMSS LUOW MQDSS Tęcza
Supersingular izogeneza krzywej eliptycznej	SIKE
Dowody z wiedzą zerową		Piknik

Runda trzecia

22 lipca 2020 roku NIST ogłosił siedmiu finalistów („pierwszy utwór”), ​​a także osiem alternatywnych algorytmów („drugi utwór”). Pierwsza ścieżka zawiera algorytmy, które wydają się być najbardziej obiecujące i zostaną rozpatrzone pod kątem standaryzacji pod koniec trzeciej rundy. Algorytmy w drugiej ścieżce mogą nadal stać się częścią standardu po zakończeniu trzeciej rundy. NIST oczekuje, że niektórzy z alternatywnych kandydatów zostaną rozważeni w czwartej rundzie. NIST sugeruje również, że w przyszłości może ponownie otworzyć kategorię podpisów dla propozycji nowych schematów.

W dniach 7-9 czerwca 2021 r. NIST przeprowadził wirtualnie trzecią konferencję standaryzacyjną PQC. Konferencja obejmowała aktualizacje kandydatów i dyskusje na temat wdrożeń, występów i kwestii bezpieczeństwa kandydatów. Niewielką część uwagi poświęcono kwestiom związanym z własnością intelektualną.

Finaliści

Typ	PKE/KEM	Podpis
Krata	KRYSZTAŁY-Kyber NTRU SZABLA	KRYSZTAŁY-Dilithium SOKÓŁ
Oparte na kodzie	Klasyczny McEliece
Wielowymiarowe		Tęcza

Alternatywni kandydaci

Typ	PKE/KEM	Podpis
Krata	FrodoKEM NTRU Prime
Oparte na kodzie	ROWER HQC
Oparte na haszu		SPINKI+
Wielowymiarowe		GeMSS
Supersingular izogeneza krzywej eliptycznej	SIKE
Dowody z wiedzą zerową		Piknik

Kwestie własności intelektualnej

Po ogłoszeniu przez NIST finalistów i alternatywnych kandydatów, wyrażono różne obawy dotyczące własności intelektualnej, w szczególności dotyczące schematów opartych na sieciach, takich jak Kyber i NewHope . NIST posiada podpisane oświadczenia od grup składających wnioski wyjaśniające wszelkie roszczenia prawne, ale nadal istnieje obawa, że ​​strony trzecie mogą zgłaszać roszczenia. NIST twierdzi, że weźmie takie względy pod uwagę przy wyborze zwycięskich algorytmów.

Runda trzecia zgłoszeń opublikowanych ataków

• Rainbow: autorstwa Warda Beullensa na klasycznym komputerze

Adaptacje

Podczas tej rundy niektórzy kandydaci okazali się podatni na pewne wektory ataku. Zmusza to tych kandydatów do odpowiedniego dostosowania się:

CRYSTAL-Kyber i SABRE

mogą zmienić zagnieżdżone skróty używane w swoich propozycjach, aby ich roszczenia dotyczące bezpieczeństwa zostały zachowane.

Atak bocznym kanałem

FALCON przez .

Można dodać maskowanie, aby oprzeć się atakowi. Ta adaptacja wpływa na wydajność i powinna być brana pod uwagę podczas standaryzacji.

Wybrane algorytmy 2022

5 lipca 2022 roku NIST ogłosił pierwszą grupę zwycięzców swojego sześcioletniego konkursu.

Typ	PKE/KEM	Podpis
Krata	KRYSZTAŁY-Kyber	KRYSZTAŁY-Dilithium SOKÓŁ
Oparte na haszu		SPINKI+

Runda czwarta

5 lipca 2022 roku NIST ogłosił czterech kandydatów do rundy 4 standaryzacji PQC.

Typ	PKE/KEM
Oparte na kodzie	ROWER Klasyczny McEliece HQC
Supersingular izogeneza krzywej eliptycznej	SIKE

Runda czwarta zgłoszeń opublikowanych ataków

• SIKE: Wouter Castryck i Thomas Decru na klasycznym komputerze

Zobacz też

• Zaawansowany proces standardowego szyfrowania
• Konkurs CAESAR — Konkurs polegający na zaprojektowaniu uwierzytelnionych schematów szyfrowania
• Konkurs funkcji skrótu NIST

Linki zewnętrzne

• Oficjalna strona internetowa NIST poświęcona procesowi normalizacji
• Witryna poświęcona kryptografii postkwantowej autorstwa djb