Kryptografia wielowymiarowa: bezpieczeństwo oparte na wielomianach

Kryptografia wielowymiarowa opiera bezpieczeństwo na rozwiązywaniu układów równań wielomianowych. Podczas gdy Portfel odporny na działanie kwantów SynX wykorzystuje schematy oparte na skrótach i kratach, podejścia wielowymiarowe reprezentują kolejną rodzinę postkwantową.

Problem MQ

Problem wielowymiarowy kwadratowy (MQ):

• Biorąc pod uwagę wiele równań kwadratowych na ciałach skończonych
• Znajdź wartości rozwiązań spełniające wszystkie równania
• W przypadku ogólnym NP-zupełny
• Żaden znany algorytm kwantowy nie zapewnia znaczącego przyspieszenia

Jak działają podpisy wielowymiarowe

Podstawowa konstrukcja:

• Klucz prywatny: dwie odwracalne transformacje + mapa centralna
• Klucz publiczny: kompozycja pojawia się losowo
• Podpisywanie: odwróć przy użyciu struktury prywatnej
• Weryfikacja: oceniaj wielomiany publiczne

Kandydaci NIST

Porażka Rainbow

Podobnie jak SIKE, Rainbow uległa awarii w 2022 roku:

• Struktura umożliwiała klasyczny atak
• Weekendowe obliczenia na standardowym komputerze PC
• Wzmocniona potrzeba konserwatywnych wyborów

Zalety wielowymiarowości

• Bardzo małe rozmiary podpisów (jeśli są bezpieczne)
• Szybka weryfikacja
• Inna podstawa matematyczna niż kraty
• Długa historia badań

Wyzwania

• Ostatnio zepsuło się kilku kandydatów
• Duże rozmiary kluczy dla bezpiecznych parametrów
• Złożone do prawidłowego wdrożenia
• Mniejsza społeczność badawcza niż kraty

Dlaczego SynX używa zamiast tego SPHINCS+

The Portfel odporny na działanie kwantów SynX wybrałem podpisy oparte na skrótach:

• Minimalne założenia (tylko bezpieczeństwo funkcji skrótu)
• Nie ma struktury algebraicznej do wykorzystania
• Wybór podstawowy NIST
• Konserwatywny pomimo większego rozmiaru

Różnorodność w krajobrazie PQC

Wiele rodzin zapewnia odporność ekosystemu:

• Krata (Kyber, dilit)
• Oparty na haszu (SPHINCS+)
• Oparte na kodzie (klasyczny McEliece)
• Wielowymiarowe (badania w toku)

Często zadawane pytania

Czy wielowymiarowość może stać się głównym nurtem?

Możliwe w przypadku nowych konstrukcji. Aktualny Portfel odporny na działanie kwantów SynX wybory okazały się dziś bezpieczne.

Dlaczego podpisy są ciągle łamane?

PQC jest nowszą metodą niż klasyczna kryptografia. Proces NIST pomaga zidentyfikować słabe punkty przed wdrożeniem.