Przyszłość kryptografii opartej na izogeniach

Złamanie SIKE przez Castrycka i Decru w lipcu 2022 roku radykalnie zmieniło sytuację w dziedzinie kryptografii opartej na izogeniach. Przed tym złamaniem kryptografia oparta na izogeniach była obiecującym kierunkiem postkwantowym, charakteryzującym się małymi rozmiarami kluczy, aktywnymi pracami standaryzacyjnymi i rosnącą społecznością. Po upadku SIKE dziedzina musiała ponownie przeanalizować swoje podstawy. Kluczowe pytanie brzmi: które aspekty kryptografii opartej na izogeniach pozostają trudne po opracowaniu nowych technik izogenii Richelota? Obecna odpowiedź wskazuje, że trudność problemów opartych na pierścieniu endomorfizmów (wykorzystywana w SQISign) oraz przemienne działania grup klas (CSIDH) pozostają nienaruszone. Złamanym elementem nie są izogenie jako takie, lecz wyciek informacji z pomocniczych punktów torsyjnych charakterystyczny dla SIDH.

SQISign (Short Quaternion and Isogeny Signature, De Feo i in., 2020) jest najbardziej kompaktowym znanym schematem podpisu postkwantowego. Klucz publiczny ma 64 bajty (zawiera niezmiennik j krzywej supersingularnej). Podpis ma 177 bajtów na poziomie 1. Dla porównania klucze publiczne ML-DSA (Dilithium) mają 1312 bajtów, a podpisy 2420 bajtów na poziomie 2. Bezpieczeństwo SQISign opiera się na korespondencji Deuringa: problem obliczenia izogenii o zadanym stopniu między dwiema danymi krzywymi supersingularnymi jest równoważny znalezieniu ideału w algebrze kwaternionowej pierścienia endomorfizmów. SQISign wykorzystuje schemat identyfikacji Fiat-Shamira oparty na tym trudnym problemie i tworzy podpis jako skompresowaną reprezentację izogenii odpowiedzi.

Kompaktowość SQISign wiąże się z bardzo wysokim kosztem wydajności. Podpisywanie wymaga obliczenia izogenii dużego stopnia (około p^{1/4}) z użyciem tłumaczenia ideał–izogenia w algebrze kwaternionowej — jest to intensywna obliczeniowo operacja, której wykonanie na procesorze CPU komputera stacjonarnego zajmuje około 60–600 sekund, zależnie od zestawu parametrów. Weryfikacja jest szybsza (około 200 ms), ale nadal znacznie wolniejsza niż weryfikacja ML-DSA (trwająca mikrosekundy). SQISign 2.0 (2023) zwiększył wydajność stukrotnie dzięki udoskonaleniom algorytmów, skracając podpisywanie do 1–10 sekund. SQISign HD (high degree) i inne warianty są nadal optymalizowane. Docelowe zastosowania obejmują przypadki, w których przepustowość jest silnie ograniczona (certyfikaty IoT, dane blockchainów, komunikacja kosmiczna), a szybkość obliczeń ma drugorzędne znaczenie.

FESTA (Fast Encryption from Supersingular Torsion Attacks, 2023) to KEM zaprojektowany specjalnie w celu uniknięcia wycieku punktów torsyjnych charakterystycznego dla SIDH. Kluczowa idea projektu polega na tym, że zamiast publikować phi_A(P_B) i phi_A(Q_B), jak w SIDH, FESTA wykorzystuje inną strukturę izogenii, w której klucz publiczny szyfrującego zawiera wyłącznie krzywą obrazu (bez obrazów punktów torsyjnych). FESTA wykorzystuje izogenie 2^n w zmodyfikowany sposób, umożliwiając deszyfrowanie bez obrazów bazy torsyjnej drugiej strony. Wstępne analizy sugerują, że FESTA jest odporny na atak Castrycka-Decru ze względu na inną strukturę informacji pomocniczych. FESTA jest obiecującym kierunkiem, ale wymaga dokładniejszej analizy kryptograficznej — społeczność zajmująca się izogeniami zachowuje ostrożność po niespodziewanym złamaniu SIKE.

SCALLOP (Scalable Commutative Actions with Large Oriented Primes, 2023) odpowiada na problem słabego bezpieczeństwa kwantowego CSIDH. Mała, 512-bitowa liczba pierwsza p w CSIDH zapewnia zaledwie około 65 bitów bezpieczeństwa kwantowego (wobec podwykładniczego algorytmu Kuperberga). SCALLOP wykorzystuje inną strukturę algebraiczną: krzywe z mnożeniem zespolonym przez duże urojone porządki kwadratowe, w których grupa klas została specjalnie zaprojektowana tak, aby była odporna na ataki kwantowe w stylu Kuperberga. SCALLOP zapewnia większą efektywną grupę klas, a jego parametry pozwalają uzyskać 128-bitowe bezpieczeństwo kwantowe przy mniejszych rozmiarach parametrów niż w CSIDH-5000. Kompromisem jest bardziej złożona konfiguracja algebraiczna SCALLOP oraz mniejsza liczba niezależnych analiz niż w przypadku CSIDH.

Biorąc pod uwagę wyjątkową kompaktowość schematów opartych na izogeniach (podpisy SQISign o długości 177 bajtów, klucze CSIDH o długości 64 bajtów) oraz ich odmienne założenia dotyczące trudności w porównaniu ze schematami kratowymi, konstrukcje hybrydowe łączą komponenty izogeniczne i kratowe, zapewniając ochronę warstwową. W hybrydowym KEM można przeprowadzić enkapsulację zarówno za pomocą ML-KEM-512, jak i CSIDH-512, a następnie połączyć oba sekrety za pomocą funkcji skrótu. Aby złamać połączony klucz, konieczne byłoby jednoczesne złamanie ML-KEM (trudność LWE) i CSIDH (trudność działania grupy klas). Jeśli którykolwiek z tych schematów pozostanie niezłamany, hybryda będzie bezpieczna. Takie podejście, nazywane elastycznością kryptograficzną, jest zalecane przez NIST i NSA organizacjom, które chcą uzyskać dodatkową pewność wykraczającą poza pojedynczy prymityw postkwantowy, zwłaszcza gdy nie ma pewności co do terminu powstania komputera kwantowego.

Oparte na izogeniach dowody z wiedzą zerową są rozwijającym się kierunkiem badań. Problem ścieżki izogenii (znalezienie phi: E -> E' przy danych obu krzywych) może służyć jako trudny problem w schematach dowodu znajomości. Protokoły Sigma dla stwierdzenia „znam izogenię z E do E'” umożliwiają uwierzytelnianie bez ujawniania izogenii. Vero (2022) demonstruje praktyczny system dowodów ZK oparty na izogeniach. Dowody te są naturalnie kompaktowe (stwierdzenie obejmuje jedynie dwa niezmienniki j), ale obecnie zbyt wolne do praktycznego wdrożenia. W miarę usprawniania obliczeń izogenii oparte na nich dowody ZK mogą stanowić alternatywę dla dowodów kratowych lub haszowych tam, gdzie ceniona jest różnorodność założeń bezpieczeństwa.

Techniki izogeniczne mają znaczenie nie tylko dla kryptografii postkwantowej — znajdują również zastosowania w klasycznej kryptografii krzywych eliptycznych. Algorytm Schoofa-Elkiesa-Atkina (SEA) zliczający punkty na krzywych eliptycznych wykorzystuje izogenie do obliczania śladu Frobeniusa, umożliwiając wydajne generowanie bezpiecznych parametrów krzywych eliptycznych. Izogenie pojawiają się w udoskonaleniach algorytmu rho Pollarda do obliczania ECDLP. Metoda CM (Complex Multiplication) konstruowania krzywych o zadanym rzędzie wykorzystuje wielomiany klas, które są z natury obiektami izogenicznymi. Narzędzia kryptoanalizy opartej na izogeniach (znajdowanie ścieżek izogenii o gładkim stopniu) służą do oceny proponowanych parametrów krzywych eliptycznych pod kątem ukrytych tylnych furtek — co ma bezpośredni związek z problemem Dual EC DRBG.

Według stanu na 2024 rok żaden schemat oparty na izogeniach nie został ustandaryzowany przez NIST ani inne główne organizacje. W ramach procesu PQC NIST ustandaryzował ML-KEM, ML-DSA, SLH-DSA i FN-DSA — wszystkie oparte na kratach lub funkcjach skrótu. NIST prowadzi drugą rundę oceny podpisów PQC; zgłoszono SQISign, ale budzi on obawy dotyczące wydajności. Społeczność zajmująca się izogeniami pracuje nad bardziej dojrzałą wersją SQISign 3.0, której celem jest osiągnięcie praktycznego czasu podpisywania poniżej jednej sekundy. ISO i ETSI nie ustandaryzowały żadnego schematu izogenicznego. Najbardziej prawdopodobna ścieżka standaryzacji w najbliższym czasie prowadzi przez SQISign przeznaczony do niszowych zastosowań wymagających minimalnych rozmiarów podpisów, być może jako standard informacyjny, a nie obowiązkowy prymityw. Szerokie wdrożenie wymaga poprawy wydajności o kilka rzędów wielkości.

Aktywne kierunki badań w kryptografii opartej na izogeniach według stanu na 2024 rok: (1) warianty SQISign (SQISign 2.0, HD, Fast SQISign) poprawiające wydajność podpisywania i zmierzające do czasu działania poniżej jednej sekundy; (2) analiza bezpieczeństwa kwantowego CSIDH i jego wariantów — uściślanie szacunków dotyczących ataku Kuperberga oraz badanie struktur algebraicznych odpornych na ten atak; (3) nowe założenia dotyczące trudności — obliczanie pierścienia endomorfizmów krzywych supersingularnych oraz problemy modułowe nad urojonymi pierścieniami kwadratowymi; (4) niejawne PRF-y oparte na izogeniach i ich zastosowania w protokołach chroniących prywatność; (5) implementacje arytmetyki izogenicznej w sprzęcie — wykorzystanie równoległości FPGA do działania grupy klas CSIDH; (6) integracja działań grup opartych na izogeniach z ogólnymi strukturami kryptografii opartej na działaniu grupy w celu tworzenia nowych schematów szyfrowania funkcyjnego i szyfrowania opartego na atrybutach.

Złamanie SIKE mogłoby sugerować całkowite porzucenie kryptografii opartej na izogeniach. Społeczność kryptograficzna przyjmuje odwrotne stanowisko: złamanie było cenne właśnie dlatego, że wskazało, które struktury są niebezpieczne (wyciek informacji z punktów torsyjnych SIDH), a które nadal pozostają trudne do obliczenia (pierścienie endomorfizmów, działania grup klas). Badanie izogenii pozostaje ważne z czterech powodów: (1) różnorodność kryptografii postkwantowej — posiadanie założeń bezpieczeństwa innych niż oparte na kratach zmniejsza ryzyko systemowe na wypadek złamania LWE; (2) SQISign zapewnia wyjątkowo krótkie podpisy, które obecnie nie mają konkurencji; (3) techniki izogeniczne pomagają w kryptoanalizie krzywych eliptycznych i walidacji parametrów; (4) matematyka jest piękna i owocna — narzędzia opracowane podczas łamania SIKE bezpośrednio pogłębiły wiedzę o pierścieniach endomorfizmów krzywych eliptycznych, wykorzystywanych także w innych kontekstach.

Jakie założenie dotyczące trudności obliczeniowej leży u podstaw podpisów SQISign?

Po złamaniu SIKE w 2022 roku kryptografia izogeniczna rozwija się dalej, opierając się na innych założeniach dotyczących trudności obliczeniowej. SQISign zapewnia 177-bajtowe podpisy postkwantowe — najmniejsze obecnie znane — oparte na trudności problemu pierścienia endomorfizmów; wydajność się poprawia, a celem jest zejście poniżej jednej sekundy. FESTA omija problem wycieku informacji z punktów torsyjnych SIDH, projektując mechanizmy KEM. SCALLOP dąży do 128-bitowego bezpieczeństwa w modelu kwantowym za pomocą krzywych z orientacją. Hybrydowe schematy izogeniczno-kratowe zapewniają różnorodność założeń bezpieczeństwa. Żaden schemat izogeniczny nie został obecnie ustandaryzowany. Najbardziej prawdopodobną ścieżką w najbliższym czasie jest standaryzacja SQISign. Złamanie SIKE pogłębiło wiedzę o tym, co należy ukrywać w protokołach izogenicznych, i doprowadziło do powstania nowych narzędzi matematycznych wykorzystywanych w całej kryptografii krzywych eliptycznych.