Od 2016 roku do FIPS 203: jak NIST wybierał kryptografię postkwantową

National Institute of Standards and Technology prowadzi od 2017 roku proces wyboru i standaryzacji kryptografii postkwantowej. Powód jest konkretny: według szacunków rozpowszechniony algorytm RSA mógłby zostać złamany przez komputer kwantowy już około 2030 roku. Proces NIST uchodzi za najważniejsze wspólne przedsięwzięcie na rzecz opracowania i oceny algorytmów odpornych na ataki kwantowe. Prowadzony jest w kilku rundach, z których każda obejmuje także konferencję. W każdej z rund część algorytmów zostaje wykluczona, a inne poddane dokładniejszym badaniom.

Większość symetrycznych prymitywów kryptograficznych można stosunkowo łatwo przystosować do bezpieczeństwa kwantowego, na przykład przez podwojenie długości klucza, co neutralizuje przyspieszenie dające algorytm Grovera. Dlatego wysiłki skupiają się na kryptografii asymetrycznej, w szczególności na podpisach cyfrowych i mechanizmach otoczki klucza. Przyszłe standardy publikowane są jako Federal Information Processing Standard, między innymi FIPS 203, FIPS 204 i FIPS 205.

Wzorzec wzięty z AES

Sprawdzony, otwarty i przejrzysty format przedsięwzięcia wzorowano na procesie standaryzacji AES z lat 1997-2000, chwalonym przez środowisko kryptologiczne. Akademickie badania nad potencjalnym wpływem informatyki kwantowej sięgają co najmniej 2001 roku. W 2015 roku amerykańskie władze federalne ogłosiły plany przeniesienia wszystkich rządowych systemów przetwarzania informacji objętych wymogami poufności na kryptografię odporną na komputery kwantowe. Dlatego na konferencji PQCrypto w 2016 roku NIST zapowiedział standaryzację kwantowo bezpiecznych prymitywów kryptograficznych. W grudniu 2016 roku proces standaryzacji zainaugurowano wezwaniem do zgłaszania propozycji.

Do zamknięcia naboru pod koniec 2017 roku zgłoszono 23 systemy podpisu cyfrowego oraz 59 metod szyfrowania i otoczki klucza. Z tej liczby 69 uznano za kompletne i nadające się do udziału w pierwszej rundzie. W niej do dalszych prac przeszły 23 kandydatury. Drugą rundę przeszło siedem algorytmów oraz osiem kandydatur alternatywnych. 22 lipca 2020 roku NIST ogłosił siedmiu finalistów, w tym trzy systemy podpisu, oraz osiem rozwiązań alternatywnych.

Kto wygrał, kto poległ

W trzeciej rundzie zwyciężyły algorytmy CRYSTALS-Kyber jako mechanizm otoczki klucza oraz CRYSTALS-Dilithium, FALCON i SPHINCS+ jako systemy podpisu cyfrowego. To one są obecnie standaryzowane przez NIST. Ogłoszona w lipcu 2022 roku czwarta runda, w której sprawdzane są cztery dalsze algorytmy, wciąż trwała w marcu 2024 roku. W 2024 roku NIST opublikował ostateczne wersje swoich pierwszych trzech standardów kryptografii postkwantowej. Dwa algorytmy oparte na kratach, ML-KEM znany powszechnie jako Kyber oraz ML-DSA znany jako Dilithium, znalazły się wśród pierwszych standaryzowanych rozwiązań postkwantowych. Nie wszystkie konstrukcje przetrwały. Szeroko komentowana konstrukcja SIDH/SIKE została spektakularnie złamana w 2022 roku, choć atak dotyczył wyłącznie tej rodziny schematów i nie uogólnia się na inne konstrukcje oparte na izogeniach.