ML-DSA (FIPS 204) i SLH-DSA (FIPS 205)

ML-DSA (oparty na kratach modułowych algorytm podpisu cyfrowego), standaryzowany jako FIPS 204, wywodzi się z CRYSTALS-Dilithium. Dilithium został zaprojektowany przez Ducasa, Kiltza, Lepointa, Lyubashevsky'ego, Schwabego, Seilera i Stehlego, a następnie zgłoszony do NIST w 2017 roku. Wykorzystuje schemat Fiat-Shamir z odrzucaniem zastosowany do Module-LWE, tworząc praktyczny schemat podpisu z silnymi dowodami bezpieczeństwa.

Klasyczne przekształcenie Fiat-Shamira zamienia interaktywne protokoły identyfikacji w podpisy. W przypadku schematów kratowych bezpośrednie zastosowanie ujawnia informacje o kluczu tajnym poprzez wektor odpowiedzi. Technika z odrzucaniem opracowana przez Lyubashevsky'ego dodaje próbkowanie z odrzuceniem: podpisujący sprawdza, czy odpowiedź ujawniłaby informacje, a jeśli tak, odrzuca ją i ponawia próbę. Zwiększa to nieznacznie koszt podpisywania, ale ma kluczowe znaczenie dla bezpieczeństwa.

Aby utworzyć podpis, ML-DSA losuje wektor maskujący y z rozkładu jednostajnego, oblicza zobowiązanie w = Ay, haszuje parę (message, w), aby uzyskać wielomian wyzwania c, i oblicza odpowiedź z = y + cs. Próbkowanie z odrzuceniem sprawdza, czy z ujawnia informacje o s. Jeśli sprawdzenie się powiedzie, podpis ma postać (c, z) wraz ze wskazówką ułatwiającą wydajną weryfikację. W przeciwnym razie proces jest powtarzany.

ML-DSA definiuje trzy zestawy parametrów: ML-DSA-44 (2. poziom bezpieczeństwa NIST, ~128-bitowy), ML-DSA-65 (3. poziom, ~192-bitowy) oraz ML-DSA-87 (5. poziom, ~256-bitowy). Liczby odnoszą się do rang modułów w schemacie. Rozmiary kluczy publicznych wynoszą odpowiednio 1312, 1952 i 2592 bajty. Podpis ML-DSA-65 ma rozmiar 3293 bajtów, w porównaniu z 64 bajtami dla Ed25519 przy 128-bitowym poziomie bezpieczeństwa.

Najistotniejszą wadą ML-DSA w porównaniu z ECDSA lub EdDSA jest rozmiar podpisu. Podpisy ML-DSA-65 mają 3293 bajty, podczas gdy podpisy Ed25519 mają 64 bajty. W protokołach, które przesyłają wiele podpisów (łańcuchy certyfikatów TLS, podpisywanie kodu), zwiększa to zapotrzebowanie na przepustowość. Jednak podpisywanie i weryfikacja ML-DSA są bardzo szybkie (porównywalne z ECDSA lub szybsze), dlatego kompromis dotyczy przede wszystkim kosztu komunikacji.

SLH-DSA (bezwstanowy algorytm podpisu cyfrowego oparty na funkcjach skrótu), standaryzowany jako FIPS 205, wywodzi się z SPHINCS+. W przeciwieństwie do schematów kratowych bezpieczeństwo SLH-DSA zależy wyłącznie od odporności bazowej funkcji skrótu na kolizje i znalezienie drugiego obrazu wstępnego (SHA-256 lub SHAKE-256). Dzięki temu SLH-DSA jest niezwykle konserwatywny: pozostaje bezpieczny nawet w przypadku złamania założeń dotyczących krat.

SLH-DSA opiera się na WOTS+ (jednorazowym podpisie Winternitza), schemacie opartym na funkcjach skrótu, w którym klucz prywatny jest zbiorem losowych ciągów, a klucz publiczny powstaje przez wielokrotne haszowanie każdego z nich. Podpisywanie polega na częściowym haszowaniu zależnym od bitów wiadomości. Z jednej pary kluczy WOTS+ można bezpiecznie skorzystać tylko raz; dwukrotne użycie ujawnia informacje. SLH-DSA umożliwia wielokrotne podpisywanie na bazie WOTS+ dzięki wykorzystaniu drzew.

SLH-DSA wykorzystuje hiperdrzewo, czyli drzewo drzew Merkle'a. Każdy liść jest kluczem publicznym jednej instancji WOTS+. Korzeń stanowi klucz publiczny SLH-DSA. Podpis składa się z podpisu WOTS+ wiadomości oraz ścieżki uwierzytelniania prowadzącej od liścia do korzenia. Struktura hiperdrzewa umożliwia tworzenie wielu podpisów z jednej pary kluczy dzięki wykorzystaniu różnych liści WOTS+.

SLH-DSA ma 12 zestawów parametrów łączących funkcję skrótu (SHA-256 lub SHAKE-256), poziom bezpieczeństwa (128s/128f, 192s/192f, 256s/256f) oraz optymalizację (s = małe podpisy, f = szybkie podpisywanie). Wariant 128f ma podpisy o rozmiarze 7856 bajtów i zapewnia szybkie podpisywanie, natomiast 128s ma podpisy o takim samym rozmiarze, ale działa wolniej. Wszystkie podpisy są znacznie większe niż w ML-DSA, ale opierają się na najsilniejszym możliwym założeniu bezpieczeństwa.

ML-DSA jest preferowany, gdy istotne są wydajność i przepustowość oraz można zaufać założeniom dotyczącym krat. SLH-DSA jest preferowany w niezwykle konserwatywnych wdrożeniach, w których ufa się wyłącznie bezpieczeństwu funkcji skrótu, lub jako zabezpieczenie na przyszłość przed ewentualnym złamaniem założeń dotyczących krat. Urzędy certyfikacji i systemy rządowe, które podpisują rzadko, ale wymagają maksymalnej gwarancji bezpieczeństwa, mogą preferować SLH-DSA, podczas gdy serwery TLS podpisujące często będą preferować ML-DSA.

FN-DSA (FIPS 206, oparty na FALCON) zapewnia mniejsze podpisy niż ML-DSA (897 bajtów dla FALCON-512 przy 128-bitowym poziomie bezpieczeństwa), wykorzystując kraty NTRU i próbkowanie gaussowskie. FALCON wymaga jednak starannej implementacji ze stałym czasem wykonania, aby uniknąć ataków kanałami bocznymi ze strony próbnika gaussowskiego. Oczekuje się, że FIPS 206 zostanie ustandaryzowany po FIPS 203–205 i zapewni wysokowydajną opcję dla środowisk o ograniczonych zasobach.

Jaka jest główna przewaga bezpieczeństwa SLH-DSA nad ML-DSA?

ML-DSA (FIPS 204) wykorzystuje schemat Fiat-Shamir z odrzucaniem oparty na Module-LWE i zapewnia szybkie podpisywanie przy podpisach o rozmiarze 3 KB (przy 192-bitowym poziomie bezpieczeństwa). SLH-DSA (FIPS 205) wykorzystuje oparte na funkcjach skrótu drzewa Merkle'a (WOTS+) i opiera się wyłącznie na bezpieczeństwie funkcji skrótu, ale generuje podpisy o rozmiarze 7–50 KB. ML-DSA jest preferowany w zastosowaniach, w których kluczowa jest wydajność, a SLH-DSA — gdy najważniejsza jest maksymalna ostrożność. FN-DSA (FALCON, FIPS 206) doda kratową opcję z mniejszymi podpisami.