Przejdź do treści
Wróć do wyników wyszukiwania

Kryptografia oparta na kratach

Autor metody
Miklós Ajtai
Rok
1996
Typ
public-key cryptosystem based on lattice hardness
Rodzina
Post-quantum cryptography

Ten tekst jest tłumaczeniem maszynowym i nie został jeszcze sprawdzony. Przeczytaj oryginał po angielsku

Rozmiar czcionki

Do czego służy?

Kryptografia oparta na kratach to klasa kryptosystemów, których bezpieczeństwo wynika z obliczeniowej trudności problemów kratowych, w szczególności problemu najkrótszego wektora (SVP) i uczenia się z błędami (LWE).

Zaproponowane po raz pierwszy przez Miklósa Ajtaia w 1996 roku, podejścia oparte na kratach zyskały na znaczeniu jako wiodący kandydaci do kryptografii postkwantowej. W przeciwieństwie do RSA i ECC, które są podatne na komputery kwantowe, uważa się, że problemy kratowe pozostają trudne nawet dla algorytmów kwantowych.

Intuicja stojąca za metodą

Siatka to dyskretna podgrupa przestrzeni euklidesowej utworzona przez całkowite kombinacje liniowe wektorów bazowych. Kryptografia oparta na kratach wykorzystuje lukę między dwoma problemami: znalezienie krótkiego wektora w kracie jest obliczeniowo trudne, ale przy dodatkowych informacjach (tajna baza) krótki wektor można znaleźć szybko. Kryptografia klucza publicznego jest budowana poprzez publikowanie trudnej bazy i utrzymywanie tajnej łatwej bazy. Dodanie małego losowego szumu (paradygmat uczenia się z błędami) dodatkowo wzmacnia bezpieczeństwo, sprawiając, że problem przypomina hałaśliwy system liniowy, który jest trudny do rozwiązania.

Historia

Fundamentalna praca Ajtaia z 1996 roku połączyła trudność krat z kryptografią. Ramy uczenia się z błędami (LWE) Regeva z 2005 roku stanowiły praktyczną i wszechstronną podstawę kryptografii kratowej. Dziedzina przyspieszyła po tym, jak instytucje akademickie i rządowe rozpoznały zagrożenie ze strony komputerów kwantowych dla obecnej infrastruktury kryptograficznej. W 2022 roku NIST zestandaryzował algorytmy kryptografii postkwantowej, wybierając schematy oparte na kratach (CRYSTALS-Kyber do szyfrowania, CRYSTALS-Dilithium do podpisów) jako główne rekomendacje.

Kiedy stosować

Kryptografia oparta na kratach jest niezbędna dla systemów zaprojektowanych tak, aby pozostały bezpieczne przed przyszłymi komputerami kwantowymi. Jest zalecana do długoterminowej poufności wrażliwych danych, komunikacji rządowej i wojskowej oraz infrastruktury, która musi pozostać bezpieczna przez dziesięciolecia. W miarę dojrzewania standaryzowanych algorytmów postkwantowych (NIST niedawno zestandaryzował ML-KEM i ML-DSA), metody kratowe stają się powszechne w nowoczesnych systemach kryptograficznych.

Ograniczenia i uwagi

  • Większe rozmiary kluczy i szyfrogramów w porównaniu do tradycyjnych RSA lub ECC, co zwiększa narzut związany z przechowywaniem i transmisją
  • Bardziej nowe i mniej powszechnie wdrożone niż RSA lub ECC, więc doświadczenie w rzeczywistym wdrożeniu jest ograniczone
  • Niektóre schematy oparte na kratach mają subtelne wybory parametrów, które znacząco wpływają na bezpieczeństwo; nieprawidłowe parametry mogą być katastrofalne

Warunki podane w źródle nie zastępują niezależnego przeglądu naukowego ani walidacji przez silnik analityczny.

Mocne strony

  • Uważa się, że jest odporna na ataki komputerów kwantowych, w tym algorytm Shor'a
  • Silne podstawy matematyczne oparte na dobrze zbadanych problemach kratowych
  • Obsługuje zarówno szyfrowanie, jak i podpisy cyfrowe w ramach tego samego systemu
  • Dostępne praktyczne implementacje z rozsądnymi kosztami obliczeniowymi dla nowoczesnego sprzętu

Zastosowania

  • Bezpieczeństwo transportu postkwantowego w celu ochrony komunikacji przed przyszłym deszyfrowaniem kwantowym
  • Długoterminowe szyfrowanie archiwalne dokumentów i danych, które muszą pozostać tajne przez dziesięciolecia
  • Systemy komunikacji rządowej i wojskowej odporne na zagrożenia kwantowe
  • Systemy blockchain i kryptowalut zaprojektowane z myślą o bezpieczeństwie kwantowym
  • Systemy IoT i wbudowane, w których odporność kwantowa jest wymogiem projektowym
  • Systemy kryptograficzne hybrydowe łączące algorytmy kratowe i tradycyjne w okresie przejściowym kryptograficznym

Jak to działa

Jak to działa

1

Wybierz wymiary kraty n, moduł q i rozkład błędów. Wygeneruj tajną krótką bazę i wyprowadź z niej bazę publiczną za pomocą transformacji kratowych.

2

Klucz publiczny jest wyprowadzany z trudnej bazy kratowej; z obliczeniowego punktu widzenia nie dostarcza on żadnych informacji o tajnej bazie.

3

Aby zaszyfrować, dodaj tekst jawny do zaszumionej kombinacji liniowej wektorów bazy publicznej, tworząc punkt kratowy plus szum.

4

Używając tajnej krótkiej bazy, zredukuj zaszumiony punkt kratowy i wyodrębnij tekst jawny.

Częste pułapki

  • Wybór parametrów kraty (wymiar, moduł, rozkład błędów) nie jest trywialny; zdecydowanie zaleca się stosowanie standardowych parametrów zatwierdzonych przez NIST
  • Ataki bocznym kanałem (czasowe, analiza mocy) na operacje kratowe wymagają starannej implementacji; algorytmy stałoczasowe są niezbędne
  • Mylenie algorytmów opartych na kratach z klasycznymi algorytmami może tworzyć systemy hybrydowe z nieoczekiwanymi słabościami

Najczęściej zadawane pytania

Czym jest problem uczenia się z błędami (LWE)?

LWE to problem obliczeniowy, w którym otrzymuje się zaszumione równania liniowe nad ciałem skończonym. Odzyskanie x z równań postaci a·x + e (mod q), gdzie a jest losowe, x jest tajne, a e jest małym szumem, jest obliczeniowo trudne.

Dlaczego klucze oparte na kratach są większe niż klucze RSA?

Bazy kratowe i macierze je kodujące zawierają więcej informacji niż pojedyncza liczba złożona. Kodowanie bazy kratowej kryptograficznie wymaga więcej bitów, chociaż niedawne schematy zoptymalizowały reprezentacje.

Czy problemy kratowe są odporne na kwanty?

Nie jest znany żaden algorytm kwantowy szybszy niż algorytmy klasyczne dla problemów kratowych, takich jak SVP lub LWE, chociaż pozostaje to aktywnym obszarem badań. Uważa się, że trudność kratowa przetrwa komputery kwantowe.

Jakie są zalecenia NIST dotyczące kryptografii kratowej?

NIST zestandaryzował ML-KEM (Module-Lattice-Based Key-Encapsulation Mechanism) do szyfrowania i ML-DSA (Module-Lattice-Based Digital Signature Algorithm) do podpisów jako główne algorytmy postkwantowe w FIPS 203 i FIPS 204.

Czy mogę dziś używać kryptografii kratowej?

Tak. Wiele nowoczesnych bibliotek kryptograficznych obsługuje teraz zestandaryzowane algorytmy kratowe NIST. Organizacje przetwarzające wrażliwe dane z długimi okresami retencji powinny rozpocząć planowanie migracji.

Pokrewne metody

Źródła

  1. Ajtai, M. (1996). Generating hard instances of the short basis problem. In Proceedings of the 28th Annual ACM Symposium on Theory of Computing, pp. 99-108.

    Otwórz odnośnik do publikacji
    Skopiowano.
  2. Regev, O. (2005). On lattices, learning with errors, hard instances, and public key cryptography. In Proceedings of STOC 2005, pp. 84-93.

    Otwórz odnośnik do publikacji
    Skopiowano.