Izogenie krzywych eliptycznych: podstawy matematyczne

Izogenia między dwiema krzywymi eliptycznymi E i E' nad ciałem k to niestałe odwzorowanie wymierne phi: E -> E', które jest również homomorfizmem grup — odwzorowuje działanie grupowe E na działanie grupowe E'. Każda izogenia phi ma izogenię dualną phi_hat: E' -> E taką, że phi_hat złożone z phi jest równe mnożeniu przez deg(phi) na E. Stopień izogenii jest równy rozmiarowi jej jądra: izogenia stopnia l ma jądro o rozmiarze l. Izogenie uogólniają mnożenie skalarne: mnożenie przez n jest izogenią z E do E o stopniu n^2. Izogenie nad ciałami skończonymi oblicza się jako funkcje wymierne (wielomiany), które można efektywnie ewaluować.

Wzory Velu (1971) dostarczają jawnych wzorów do obliczania izogenii phi: E -> E/G dla danego podgrupowego G grupy E. Krzywa wynikowa E/G = E' oraz odwzorowanie wymierne phi są całkowicie wyznaczone przez G. Wzory Velu obliczają współczynniki krzywej wynikowej i odwzorowanie wymierne jako funkcje wymierne stopnia równego |G|. Dla podgrupy jądra G rzędu pierwszego l izogenia ma stopień l i można ją obliczyć w O(l) operacjach. Algorytmy sqrt-Velu (Bernstein i in., 2019) zmniejszają tę złożoność do O(sqrt(l)) operacji dla dużych l, umożliwiając wydajne izogenie o dużym pierwszym stopniu stosowane w CSIDH. Wzory Velu stanowią podstawowe narzędzie obliczeniowe całej kryptografii opartej na izogeniach.

Krzywe eliptyczne nad ciałem skończonym Fp można uporządkować w graf izogenii. Wierzchołkami są niezmienniki j krzywych eliptycznych (kanoniczny niezmiennik, który wyznacza krzywą z dokładnością do izomorfizmu). Krawędzie to izogenie l: każda krzywa zwyczajna ma dokładnie l+1 wychodzących izogenii l dla małej liczby pierwszej l (ze względu na strukturę podgrup l-torsyjnych). Graf izogenii l nad Fp jest grafem regularnym stopnia (l+1). Własność Ramanujana tych grafów (grafów ekspanderowych) oznacza, że losowe spacery mieszają się szybko, zapewniając założenie trudności leżące u podstaw kryptografii opartej na izogeniach: losowe spacery długości O(log p) dają jednostajne rozkłady niezmienników j.

Krzywe eliptyczne nad Fp dzielą się na dwie kategorie. Krzywe zwyczajne mają nietrywialny p-rank, co oznacza, że istnieje p^2 klas izomorfizmu, a ich graf izogenii ma złożoną strukturę wulkaniczną (kratery i poziomy). Krzywe supersingularne mają p-rank równy 0 i wszystkie należą do jednego spójnego grafu izogenii nad Fp2. Liczba supersingularnych niezmienników j nad Fp wynosi w przybliżeniu p/12. SIDH i SIKE używają krzywych supersingularnych, ponieważ ich graf izogenii jest grafem Ramanujana o silnych właściwościach ekspansji i nie ma struktury wulkanicznej, która mogłaby ujawnić kierunek spaceru. CSIDH również używa krzywych supersingularnych, ale nad Fp (nie Fp2), wykorzystując inną strukturę algebraiczną.

Kryptografia oparta na izogeniach opiera się na dwóch powiązanych trudnych problemach. Problem izogenii supersingularnych (SSIP): mając dane dwie supersingularne krzywe eliptyczne E i E' nad Fp2, należy znaleźć izogenię phi: E -> E'. Problem obliczeniowej izogenii supersingularnej (CSSI): mając dane E, E' = phi(E) oraz stopień phi, należy znaleźć phi. Najlepszy klasyczny algorytm dla SSIP działa w czasie O(p^{1/4}). Najlepszy algorytm kwantowy (wyszukiwanie kolizji Taniego) działa w czasie O(p^{1/6}). Dla p = 2^{434} daje to 128-bitowy poziom bezpieczeństwa klasycznego. Są to znacznie mniejsze przyspieszenia kwantowe niż wykładnicze przyspieszenie algorytmu Shora przeciwko RSA/ECC, dzięki czemu schematy oparte na izogeniach są odporne na ataki postkwantowe.

SIDH (Supersingular Isogeny Diffie-Hellman) używa specjalnie skonstruowanej liczby pierwszej p = 2^a * 3^b - 1, która zapewnia, że krzywa E nad Fp2 ma dostępne punkty 2^a-torsyjne (zbiór punktów P, dla których 2^a * P = 0) oraz punkty 3^b-torsyjne. Sekretem Alicji jest izogenia 2^a phi_A: E -> E_A, której jądro jest generowane przez losowy element grupy 2^a-torsyjnej. Sekretem Boba jest izogenia 3^b phi_B: E -> E_B. Wymieniają obrazy punktów torsyjnych: Alicja publikuje E_A i phi_A(P_B), phi_A(Q_B). Bob publikuje E_B i phi_B(P_A), phi_B(Q_A). Dzięki temu każda ze stron może obliczyć izogenie z krzywej drugiej strony i uzyskać ten sam współdzielony niezmiennik j.

Pierścień endomorfizmów End(E) krzywej eliptycznej to pierścień wszystkich izogenii z E do E (w tym mnożenia skalarne). Dla krzywych zwyczajnych nad Fp End(E) jest rzędem w urojonym ciele kwadratowym. Dla krzywych supersingularnych End(E) jest maksymalnym rzędem w algebrze kwaternionowej rozgałęzionej w p i nieskończoności. Struktura End(E) całkowicie wyznacza krzywą z dokładnością do izomorfizmu. Problem pierścienia endomorfizmów — obliczenie End(E) przy danym E — uważa się za trudny (dla krzywych supersingularnych jest równoważny SSIP). Atak Castrycka-Decru na SIDH/SIKE wykorzystał dodatkowe informacje ujawnione w protokole SIDH do wydajnej rekonstrukcji części pierścienia endomorfizmów, łamiąc ten schemat.

Izogenię stopnia l phi: E -> E' można reprezentować jako wielomian stopnia l (lub l/2 po optymalizacji z wykorzystaniem symetrii, ponieważ odwrotności punktów mają tę samą współrzędną x). Obliczenie phi(P) dla danego punktu P wymaga O(l) mnożeń przy użyciu wzorów Velu. W przypadku SIDH, dla l = 2^a około 2^216, wydaje się to niewykonalne, ale SIDH wykorzystuje fakt, że izogenie 2^a można rozłożyć na łańcuch a pojedynczych izogenii 2 — każda izogenia 2 jest tania, a łańcuch a kroków tworzy izogenię 2^a. Analogicznie postępuje się dla 3^b. sqrt-Velu pozwala obliczać izogenie dla dużych nieparzystych liczb pierwszych w CSIDH w czasie O(sqrt(l)), a nie O(l), dzięki czemu CSIDH staje się praktyczny.

SIKE (Supersingular Isogeny Key Encapsulation) był kandydatem w konkursie NIST PQC, który przetrwał wszystkie rundy aż do czwartej, gdy został złamany. SIKE wyróżniał się najmniejszymi rozmiarami kluczy spośród wszystkich kandydatów NIST: 374 bajty dla SIKEp434 (poziom 1 NIST). Dla porównania klucze publiczne ML-KEM-512 mają 800 bajtów. SIKE osiągał tę kompaktowość, ponieważ współdzielony sekret wynika z pojedynczego niezmiennika j (elementu ciała o długości około 430 bitów). Kompaktowość miała jednak swoją cenę: SIKE był od 100 do 1000 razy wolniejszy od innych kandydatów. Gdy Castryck i Decru złamali SIKE w lipcu 2022 roku za pomocą klasycznego ataku działającego w kilka minut na laptopie, SIKE natychmiast wyeliminowano z konkursu NIST.

Kryptografia oparta na izogeniach zajmuje wyjątkową pozycję wśród podejść postkwantowych. Rozmiary kluczy: znacznie mniejsze niż w kryptografii kratowej (ML-KEM: ponad 800 bajtów) lub podpisach opartych na funkcjach skrótu (SLH-DSA: klucz publiczny 32–49 bajtów, ale podpisy 7856–49856 bajtów). Wydajność: znacznie niższa niż wszystkich alternatyw (SIKE był od 100 do 1000 razy wolniejszy od ML-KEM). Założenie bezpieczeństwa: odmienne od LWE (używanego w ML-KEM/ML-DSA), SIS i funkcji skrótu — zapewnia różnorodność kryptograficzną. Podstawa bezpieczeństwa postkwantowego: problem ścieżki izogenii nie ma znanego algorytmu kwantowego działającego w czasie wielomianowym, w przeciwieństwie do RSA/ECC, które algorytm Shora całkowicie łamie. Klasyczne złamanie SIKE pokazuje, że trudność problemów izogenii wciąż jest badana, w przeciwieństwie do dobrze poznanego problemu LWE.

Pomimo złamania SIKE kryptografia oparta na izogeniach pozostaje aktywnym obszarem badań. SQISign (Short Quaternion and Isogeny Signature) to oparty na izogeniach schemat podpisu z podpisami o rozmiarze 177 bajtów (w porównaniu z 2420 bajtami dla ML-DSA na poziomie 2) — najmniejszymi znanymi podpisami PQC. SQISign wykorzystuje trudny problem obliczenia izogenii o zadanym stopniu między dwiema danymi krzywymi supersingularnymi, sformalizowany jako problem pierścienia endomorfizmów. FESTA (Fast Encryption from Supersingular Torsion Attacks) to nowy projekt KEM, który nie wykorzystuje dodatkowych pomocniczych danych o punktach torsyjnych, przez które SIDH był podatny na ataki. CTIDH (Constant-Time CSIDH) poprawia wydajność CSIDH. Schematy te sprawiają, że badania nad izogeniami pozostają istotne nawet po wyeliminowaniu SIKE.

Czym jest izogenia między krzywymi eliptycznymi?

Izogenia to odwzorowanie wymierne phi: E -> E', które jest homomorfizmem grup, a jej stopień jest równy rozmiarowi jądra. Wzory Velu obliczają krzywą wynikową i odwzorowanie na podstawie podgrupy jądra. Grafy izogenii przedstawiają krzywe jako wierzchołki, a krawędzie izogenii l tworzą regularne grafy Ramanujana stopnia (l+1). Krzywe supersingularne (używane w SIDH/SIKE/CSIDH) mają grafy izogenii o silnych właściwościach ekspansji. Problemy SSIP i CSSI stanowią podstawę bezpieczeństwa izogenii. SIDH wykorzystuje strukturę punktów torsyjnych z naprzemiennymi łańcuchami izogenii 2 i 3. Obliczanie pierścienia endomorfizmów jest równoważne SSIP. SQISign i FESTA reprezentują aktywne kierunki badań po SIKE, wykorzystujące trudność problemu pierścienia endomorfizmów.