Krata (ang. lattice) w kryptografii to wielowymiarowa struktura geometryczna składająca się z regularnie rozmieszczonych, dyskretnych punktów w przestrzeni, przypominająca nieskończoną, uporządkowaną sieć. Wyobraź sobie regularną, nieskończoną siatkę punktów rozciągającą się we wszystkich kierunkach, jak trójwymiarowa siatka krystaliczna, tylko że w praktyce kryptograficznej operuje się w setkach lub tysiącach wymiarów. W 2D łatwo opisać pozycję dowolnego punktu. Jeśli jednak dodamy przykładowo 1024 wymiary, siatka zamienia się w niewyobrażalnie złożony, wielowymiarowy labirynt punktów.
Kryptografia oparta na kratach (ang. Lattice-based cryptography) jest obecnie jednym z najważniejszych fundamentów kryptografii postkwantowej. Bezpieczeństwo kryptografii opartej na kratach opiera się na założeniu, że pewne zadania geometryczne w przestrzeniach wielowymiarowych są niemal niemożliwe do rozwiązania w rozsądnym czasie. Dwa najważniejsze z nich to:
- SVP (Shortest Vector Problem) to fundamentalny problem obliczeniowy w matematyce i kryptografii polegający na znalezieniu najbliższego niezerowego punktu (wektora) od początku układu współrzędnych w wielowymiarowej kracie. Wraz ze wzrostem wymiarowości przestrzeni (np. do setek lub tysięcy wymiarów), znalezienie takiego najkrótszego wektora staje się ekstremalnie trudne dla tradycyjnych oraz dla post-kwantowych komputerów
- CVP (Closest Vector Problem) to drugi fundamentalny problem obliczeniowy w teorii krat oraz kryptografii opartej na kratach, polegający na znalezieniu w danej kracie (sieci punktów w przestrzeni wielowymiarowej) punktu, który znajduje się najbliżej zadanego punktu docelowego spoza tej kraty
| Cecha | SVP (Shortest Vector Problem) | CVP (Closest Vector Problem) |
| Dane wejściowe | Jedynie baza kraty Λ | Baza kraty Λ oraz zewnętrzny wektor docelowy t |
| Cel matematyczny | Znaleźć niezerowy wektor ν ∈ Λ, który minimalizuje długość ||ν|| | Znaleźć niezerowy wektor ν ∈ Λ, który minimalizuje długość ||t - ν|| |
| Punkt odniesienia | Środek układu współrzędnych (0,0,....,0) | Dowolny punkt w przestrzeni wielowymiarowej |
| Złożoność | NP-trudny w sensie redukcji losowych | Uznawany za nieco trudniejszy; NP-trudny (NP-Hard) w sensie deterministycznym |
| Intuicja geometryczna | Znalezienie najbliższego sąsiada punktu startowego (0,0) | Znalezienie najbliższego punktu siatki dla "zagubionego" poza nią punktu |
Problem SVP można łatwo sprowadzić do problemu CVP. Jeśli ustawimy punkt docelowy t dokładnie w początku układu współrzędnych (0,0,....,0) i zrobimy założenie wykluczające wektor zerowy, rozwiązanie CVP da nam automatycznie najkrótszy niezerowy wektor kraty (SVP). W drugą stronę (redukcja CVP do SVP) jest znacznie trudniejsza i nie zawsze bezpośrednio wykonalna bez drastycznego zwiększenia wymiaru kraty. W praktyce kryptograficznej (np. w algorytmach LWE używanych w standardach NIST (National Institute of Standards and Technology) rzadko szuka się idealnie najkrótszego lub najbliższego wektora. Algorytmy szyfrujące opierają swoje bezpieczeństwo na fakcie, że nawet znalezienie wektora w przybliżeniu najbliższego lub najkrótszego (w granicach określonego czynnika γ) jest dla komputerów zbyt trudne w mnogości wymiarów.
ML-KEM (Module-Lattice-Based Key-Encapsulation Mechanism), dawniej CRYSTALS-Kyber. Algorytm kryptografii postkwantowej służący do bezpiecznej wymiany kluczy. Wybrany w sierpniu 2024 roku przez NIST (FIPS 203) jako standard postkwantowy. Kyber opiera się na konkretnym problemie matematycznym zwanym LWE (Learning with Errors), a dokładniej na jego wersji modułowej (M-LWE). Działa to następująco:
- Równania liniowe. Wyobraź sobie zestaw bardzo prostych równań z wieloma niewiadomymi. Gdyby dysponować ich wystarczającą liczbą i byłyby idealne, zwykły komputer rozwiązałby je w ułamku sekundy metodą eliminacji Gaussa.
- Dodanie błędu (szumu). W kryptografii kratowej do każdego takiego równania dodaje się malutki, losowy błąd. W efekcie równania przestają być "czyste" — a to sprawia, że nawet mając ich sporo, bez znajomości sekretu nie da się ich po prostu odwrócić. Zamiast szukać dokładnego rozwiązania, trzeba znaleźć najbliższy punkt w wielowymiarowej kracie punktów całkowitych do otrzymanego (zaszumionego) wyniku, a to jest zupełnie inny, znacznie trudniejszy problem niż rozwiązywanie układu równań.
- Wersja modułowa (M-LWE). Zamiast operować na pojedynczych liczbach, Kyber pracuje na wielomianach, dzięki temu klucze i szyfrogramy są dużo mniejsze, przy zachowaniu tego samego poziomu bezpieczeństwa. To właśnie ta wydajność sprawiła, że M-LWE, a nie "zwykłe" LWE, zostało wybrane jako podstawa standaryzowanego przez NIST algorytmu Kyber (obecnie znanego jako ML-KEM).
- Skala trudności. W najsilniejszym wariancie, Kyber-1024, krata ma aż 1024 wymiary. Znaleziony wynik jest przesunięty o losowy wektor błędu względem najbliższego punktu kraty, a znalezienie tego punktu w tak wielowymiarowej przestrzeni, bez znajomości sekretu, przypomina szukanie igły w stogu siana wielkości całej galaktyki. Dla komputera — zarówno klasycznego, jak i kwantowego — rozwiązanie takiego układu wymagałoby przeszukania przestrzeni o astronomicznej liczbie kombinacji.
ML-DSA (Module-Lattice-Based Digital Signature Algorithm), wcześniej znany jako CRYSTALS-Dilithium, to standaryzowany algorytm podpisu cyfrowego oparty na problemach kratowych: M-LWE opisanym wyżej w ustępie o Kyber oraz Module-SIS (Module Short Integer Solution), zatwierdzony (FIPS 204) w sierpniu 2024 roku.
- Skąd bierze się bezpieczeństwo. O ile Kyber (ML-KEM) służy do wymiany kluczy, czyli do tego, by dwie strony mogły ustalić wspólny tajny klucz, to ML-DSA odpowiada za podpisywanie potwierdzenie, że dana wiadomość, plik lub certyfikat pochodzi od konkretnego posiadacza klucza prywatnego i nie został zmieniony. To rola, którą dziś pełnią RSA i ECDSA, algorytmy, które komputer kwantowy uzbrojony w algorytm Shora byłby w stanie złamać. ML-DSA opiera się na problemach kratowych, dla których nie znamy do tej pory, żadnego efektywnego ataku kwantowego, stąd jego odporność. Dlaczego to ma znaczenie już teraz. Podpisy cyfrowe muszą czasem zachować wiarygodność przez wiele lat, np. podpisy pod firmware'em urządzeń albo długoterminowymi certyfikatami. Jeśli powstaną dziś przy użyciu RSA/ECDSA, w przyszłości (gdy komputery kwantowe dorosną do zadania) będzie można je podważyć retroaktywnie. Stąd migracja na ML-DSA nie jest tylko teoretycznym ćwiczeniem na przyszłość.
Szyfrowanie homomorficzne (Homomorphic Encryption) to technika kryptograficzna, która pozwala na wykonywanie obliczeń matematycznych bezpośrednio na zaszyfrowanych danych, bez konieczności ich wcześniejszego odszyfrowywania. Metoda bazująca często bazuje na problemach kratowych (np. schemat oparty na Learning With Errors)
- Częściowo vs w pełni - nie każde szyfrowanie homomorficzne jest sobie równe. Schematy partially homomorphic obsługują tylko jedną operację, np. RSA "z natury" obsługuje mnożenie zaszyfrowanych wartości. Prawdziwym przełomem było fully homomorphic encryption (FHE) czyli schemat obsługujący dowolną kombinację dodawania i mnożenia, a więc w praktyce dowolny obwód logiczny. Pierwszy praktyczny schemat FHE zaproponował Craig Gentry w 2009 roku, co przez lata uważano za problem otwarty.
- Skąd biorą się kraty. Podobnie jak Kyber i ML-DSA, większość dzisiejszych schematów FHE (Fully Homomorphic Encryption) opiera się na wariantach problemu Learning With Errors, w praktyce najczęściej na jego wersji pierścieniowej Ring-LWE (Ring Learning with Errors) ze względu na tę samą korzyść wydajnościową, która stoi za Module-LWE w Kyberze: operowanie na wielomianach zamiast pojedynczych liczb znacznie zmniejsza rozmiar danych. Najbardziej znane rodziny schematów to BGV i BFV (dobre dla liczb całkowitych), CKKS (dla liczb zmiennoprzecinkowych, stąd popularność w uczeniu maszynowym na zaszyfrowanych danych) oraz TFHE (zoptymalizowane pod szybkie odświeżanie szumu, dobre dla obwodów bitowych). FHE wciąż jest o rzędy wielkości wolniejsze niż obliczenia na danych jawnych. To nie jest technologia "plug and play" do każdego zastosowania. Z roku na rok sytuacja się poprawia (dzięki lepszym algorytmom i akceleracji sprzętowej).
- FN-DSA (Falcon) - podpis ma tylko około 666 bajtów
- ML-DSA (Dilithium) - podpis ma około 2420 bajtów (ponad 3,5 raza więcej)
- SLH-DSA (SPHINCS+) - podpis ma około 7856 bajtów (blisko 12 razy więcej)
