Konkurs NIST PQC: przebieg i kryteria

NIST uruchomił projekt standaryzacji kryptografii postkwantowej (PQC) w 2016 roku w bezpośredniej odpowiedzi na zagrożenie stwarzane przez komputery kwantowe. Algorytm Shora może złamać RSA i kryptografię krzywych eliptycznych w czasie wielomianowym na dostatecznie dużym komputerze kwantowym. NIST uznał, że przejście na nową infrastrukturę kryptograficzną zajmuje dekady, dlatego rozpoczął ten proces na długo przed pojawieniem się bezpośredniego zagrożenia ze strony komputerów kwantowych.

W grudniu 2016 roku NIST opublikował wezwanie do zgłaszania propozycji i do listopada 2017 roku otrzymał 82 kompletne zgłoszenia. Po wstępnej ocenie 69 z nich zaakceptowano jako kandydatów pierwszej rundy. Zgłoszenia obejmowały szeroki zakres założeń matematycznych: problemy kratowe, funkcje skrótu, kryptografię opartą na kodach, kryptografię opartą na izogeniach oraz wielomiany wielu zmiennych. Różnorodność założeń była jednym z głównych celów, aby nie uzależniać całego rozwiązania od jednego założenia.

Podczas rundy 1 NIST i cała społeczność kryptograficzna przeprowadziły intensywną analizę wszystkich 69 kandydatów. Kryteria obejmowały bezpieczeństwo (odporność na ataki klasyczne i kwantowe), wydajność (rozmiary kluczy i szyfrogramów, szybkość obliczeń), elastyczność (zestawy parametrów dla różnych poziomów bezpieczeństwa) oraz prostotę implementacji. Do stycznia 2019 roku do rundy 2 awansowało 26 kandydatów.

26 kandydatów rundy 2 poddano dokładniejszej analizie kryptograficznej i testom wydajności. W tej rundzie kilka schematów złamano lub osłabiono, w tym Rainbow (wielomianowy) i SIKE (oparty na izogeniach, choć SIKE złamano dopiero w rundzie 3). Do lipca 2020 roku do rundy 3 awansowało 15 kandydatów, podzielonych na 7 finalistów i 8 alternatyw.

Finalistami rundy 3 było 7 schematów: Kyber, NTRU, SABER (KEM-y) oraz Dilithium, FALCON, Rainbow i SPHINCS+ (schematy podpisu). SIKE był kandydatem alternatywnym, ale został spektakularnie złamany w 2022 roku. NIST wybrał Kybera do standaryzacji KEM ze względu na przejrzystą konstrukcję, mocne dowody bezpieczeństwa i znakomitą wydajność. Do zastosowań związanych z podpisami wybrano Dilithium, FALCON i SPHINCS+.

NIST celowo wybrał algorytmy oparte na różnych problemach matematycznych, aby zabezpieczyć się przed przyszłymi przełomami. ML-KEM i ML-DSA opierają się na Module-LWE (kratach). FALCON opiera się na kratach NTRU i próbkowaniu gaussowskim. SLH-DSA opiera się wyłącznie na bezpieczeństwie funkcji skrótu. Gdyby nastąpił przełom w atakach na kraty, SLH-DSA pozostałby bezpieczny, zapewniając różnorodność algorytmiczną w standaryzowanym zestawie.

W 2022 roku NIST otworzył czwartą rundę, której celem było pozyskanie dodatkowych kandydatów na schematy podpisu. Motywacją była potrzeba większej różnorodności podpisów wykraczającej poza schematy oparte na kratach. Wśród kandydatów znalazły się MAYO, CROSS, UOV i inne schematy oparte na założeniach wielomianowych oraz kodowych. Proces ten przebiegał równolegle z finalizowaniem trzech pierwszych standardów (FIPS 203, 204 i 205).

W sierpniu 2024 roku NIST opublikował ostateczne standardy PQC: FIPS 203 (ML-KEM, oparty na Kyberze), FIPS 204 (ML-DSA, oparty na Dilithium) oraz FIPS 205 (SLH-DSA, oparty na SPHINCS+). Oczekuje się, że w dalszej kolejności zostanie opublikowany FIPS 206 (FN-DSA, oparty na FALCON). Standardy te muszą być obecnie uwzględniane przez amerykańskie agencje federalne i wpływają na standardy na całym świecie za pośrednictwem ISO, ETSI i IETF.

IETF szybko włączyła PQC do protokołów. Do 2024 roku trwały prace nad szkicami RFC dotyczącymi ML-KEM w TLS 1.3, SSH i certyfikatach X.509. Cloudflare, Google i Amazon ogłosiły plany wdrożenia ML-KEM w swoich stosach TLS. Apple ogłosiło PQ3 dla iMessage, wykorzystujące ML-KEM do zapewnienia postkwantowej utajnionej poufności w przód opartej na mechanizmie ratchet; rozwiązanie wdrożono na ponad miliardzie urządzeń.

Konkurs NIST PQC pokazał, że otwarta i oparta na współpracy standaryzacja kryptograficzna działa skutecznie. W trakcie procesu złamano kilka wysoko cenionych schematów (GeMSS, SIKE, Rainbow), co potwierdziło znaczenie szeroko zakrojonej publicznej analizy kryptograficznej. Konkurs przyczynił się również do opracowania wydajnych implementacji sprzętowych i bibliotek open source (liboqs, PQClean), które przyspieszyły wdrażanie tych rozwiązań.

Standaryzacja postkwantowa nie została jeszcze zakończona. NIST nadal ocenia dodatkowe schematy podpisu w celu zapewnienia różnorodności. Organizacja normalizacyjna X9 zajmująca się sektorem finansowym opracowuje standardy PQC dla bankowości. ETSI i ISO dostosowują swoje prace do standardów NIST FIPS. Opracowywane są wytyczne migracji dla konkretnych sektorów: ochrony zdrowia (konsekwencje wynikające z HIPAA), obronności (zestaw NSA CNSA 2.0) i telekomunikacji (3GPP dla sieci 5G/6G).

Ilu kandydatów przeszło z etapu początkowych zgłoszeń do 2. rundy konkursu NIST PQC?

NIST uruchomił projekt standaryzacji PQC w 2016 roku i otrzymał 69 kompletnych zgłoszeń. Trzy rundy oceny zawęziły grono kandydatów na podstawie bezpieczeństwa, wydajności i różnorodności. Ostatecznie wybrano Kyber (ML-KEM, FIPS 203), Dilithium (ML-DSA, FIPS 204), SPHINCS+ (SLH-DSA, FIPS 205) oraz FALCON (FN-DSA, FIPS 206). Konkurs potwierdził wartość otwartej kryptanalizy i doprowadził do powstania szeroko stosowanych standardów, które są obecnie integrowane z protokołami TLS, SSH i przesyłania wiadomości.