Podpisy CRYSTALS-Dilithium i Falcon

Podpisy RSA i ECDSA są łamane przez algorytm Shora. Podpisy postkwantowe muszą je zastąpić w: certyfikatach TLS, podpisywaniu kodu, podpisywaniu wiadomości e-mail (S/MIME, PGP) oraz uwierzytelnianiu aktualizacji oprogramowania. NIST ustandaryzował dwa schematy oparte na kratach: ML-DSA i FN-DSA.

Dilithium opiera się na trudności problemów Module-LWE i Module-SIS (Short Integer Solution). Dowód bezpieczeństwa sformułowano w kwantowym modelu losowej wyroczni (QROM). Dostępne są trzy warianty: Dilithium2 (~128 bitów), Dilithium3 (~192 bity), Dilithium5 (~256 bitów). Prosta ścieżka podpisywania bez próbkowania z odrzucaniem.

Klucz prywatny: tajne macierze s1, s2. Klucz publiczny: t = As1 + s2. Podpisywanie: należy wylosować y; obliczyć w = Ay; obliczyć wyzwanie c = H(mu || w1), gdzie w1 = HighBits(w); obliczyć z = y + cs1; jeśli ||z|| lub ||r0|| jest zbyt duże, odrzucić wynik i spróbować ponownie. Wynik: (z, c, hint).

Aby zweryfikować (z, c, hint), należy sprawdzić, czy ||z|| jest małe; obliczyć w' = Az - ct; użyć hint do odzyskania w1; zweryfikować c == H(mu || w1). Hint to niewielka liczba bitów pochodząca z MakeHint(). Odrzucanie zapewnia, że z nie ujawnia s1 — uzasadnienie bezpieczeństwa ma postać argumentu „aborts-then-uniform”.

ML-DSA-65 (Dilithium3, bezpieczeństwo 192-bitowe): klucz publiczny 1952 bajty, klucz prywatny 4000 bajtów, podpis 3293 bajty. Dla porównania ECDSA-P256: klucz publiczny 64 bajty, podpis 64 bajty. Podpisy Dilithium są około 40–50 razy większe, ale zapewniają odporność na ataki kwantowe.

Falcon opiera się na kratach NTRU i wykorzystuje próbnik gaussowski nad kratą NTRU. Podpisy są znacznie mniejsze niż w Dilithium, ale podpisywanie wymaga zmiennoprzecinkowego próbnika gaussowskiego — trudniejszego do zaimplementowania w stałym czasie i bardziej złożonego pod względem bezpiecznego kodowania.

Falcon-512 (bezpieczeństwo 128-bitowe): klucz publiczny 897 bajtów, podpis 666 bajtów — znacznie mniej niż w Dilithium. Kompromis: Falcon jest trudniejszy do bezpiecznego zaimplementowania (próbkowanie gaussowskie jest podatne na ataki czasowe). Nadaje się do środowisk o ograniczonej przepustowości, ale wymaga starannej implementacji.

SPHINCS+ to schemat podpisu oparty na funkcjach skrótu — zachowawczy wybór bez strukturalnych założeń algebraicznych. Bezpieczeństwo opiera się wyłącznie na bezpieczeństwie funkcji skrótu. Rozmiar podpisu: około 8–50 KB (duży). Podpisywanie jest powolne. Stosuje się go tam, gdzie kluczowe jest długoterminowe zaufanie, a wydajność ma drugorzędne znaczenie.

ML-DSA (Dilithium): ogólnego zastosowania, prosta implementacja, odpowiedni do certyfikatów TLS i podpisywania kodu. FN-DSA (Falcon): środowiska o ograniczonej przepustowości (IoT, LPWAN). SLH-DSA (SPHINCS+): ultrazachowawczy, przeznaczony do długotrwałych kluczy głównych (offline'owe klucze CA, główny element zaufania oprogramowania).

Dilithium: próbkowanie z odrzucaniem może ujawniać informacje poprzez czas wykonania gałęzi — należy używać porównania w stałym czasie. Falcon: próbnik gaussowski wykorzystuje arytmetykę zmiennoprzecinkową — należy zapewnić deterministyczność obliczeń zmiennoprzecinkowych. W obu przypadkach należy unikać kanałów bocznych w arytmetyce wielomianowej. Należy używać implementacji referencyjnych z pakietów zgłoszeniowych NIST.

NIST FIPS 204: ML-DSA (Dilithium). NIST FIPS 205: SLH-DSA (SPHINCS+). NIST FIPS 206: FN-DSA (Falcon). Wszystkie opublikowano w sierpniu 2024 roku. Biblioteki OpenSSL 3.x, BoringSSL i liboqs (projekt Open Quantum Safe) implementują wszystkie trzy schematy.

ML-DSA (Dilithium): oparty na kratach, prosty, podpisy o rozmiarze około 3 KB. FN-DSA (Falcon): oparty na NTRU, podpisy o rozmiarze około 700 bajtów, złożona implementacja. SLH-DSA (SPHINCS+): oparty na funkcjach skrótu, zachowawczy, duży. Wszystkie ustandaryzowano w dokumentach FIPS 204/205/206. Dalej: migracja do PQC z wykorzystaniem podejść hybrydowych.