CSIDH: przemienne izogenie supersingularne

CSIDH (Commutative Supersingular Isogeny Diffie-Hellman, Castryck i in., 2018) to oparta na izogeniach wymiana kluczy, która całkowicie unika wycieku informacji z punktów torsyjnych SIDH, wykorzystując fundamentalnie inną strukturę algebraiczną. CSIDH działa na supersingularnych krzywych nad Fp (a nie nad Fp2, jak SIDH). Założeniem trudności jest przemienność działania grupy klas: każda ze stron stosuje tajny element grupy klas do wspólnej krzywej początkowej, a przemienność gwarantuje, że obie strony otrzymają tę samą krzywą wspólną. Nie publikuje się żadnych pomocniczych informacji o punktach torsyjnych — klucz publiczny jest tylko pojedynczym niezmiennikiem j. Ten projekt przetrwał atak Castrycka–Decru na SIDH.

Nad Fp, gdzie p = 3 mod 4, supersingularne krzywe E mają wyróżniony endomorfizm pi (endomorfizm Frobeniusa), a ich algebra endomorfizmów zawiera urojony rząd kwadratowy Z[pi]. Grupa klas ideałów Cl(Z[pi]) działa swobodnie i tranzytywnie na zbiorze supersingularnych krzywych nad Fp (z dokładnością do izomorfizmu). Ideał a w Cl(Z[pi]) działa na krzywą E, tworząc nową krzywą a * E, obliczaną jako krzywa E/E[a], gdzie E[a] jest podgrupą torsyjną odpowiadającą ideałowi a. Działanie to jest przemienne: a * (b * E) = b * (a * E) = [ab] * E. Jest to działanie grupy CSIDH, zapewniające przemienny analog wymiany kluczy Diffiego–Hellmana.

Wymiana kluczy CSIDH przebiega następująco. Parametry publiczne: supersingularna krzywa E0 nad Fp oraz małe nieparzyste liczby pierwsze l_1, ..., l_n. Klucze tajne: Alicja wybiera a = (a_1, ..., a_n), gdzie każde a_i należy do {-m, ..., m} (losowe małe liczby całkowite). Bob wybiera b = (b_1, ..., b_n). Klucz publiczny Alicji: E_A = [l_1^a_1 * ... * l_n^a_n] * E0. Klucz publiczny Boba: E_B = [l_1^b_1 * ... * l_n^b_n] * E0. Wspólny sekret: Alicja stosuje swoje tajne wykładniki do E_B, a Bob stosuje swoje do E_A. Przemienność gwarantuje, że oboje otrzymają E_AB = [product(l_i^(a_i + b_i))] * E0. Wspólnym sekretem jest j(E_AB). Nie publikuje się żadnych punktów pomocniczych.

Referencyjna implementacja CSIDH wykorzystuje p = 4 * l_1 * l_2 * ... * l_74 - 1, gdzie l_1 do l_74 to pierwsze 74 nieparzyste liczby pierwsze (3, 5, 7, ..., 373). Daje to p o długości około 512 bitów. Każdy składnik klucza tajnego a_i należy do {-5, ..., 5} (11 możliwości na składnik, 74 składniki). Rząd grupy klas wynosi w przybliżeniu sqrt(p), a przestrzeń kluczy ma rozmiar 11^74. Obliczanie każdego kroku izogenii: dla każdej liczby pierwszej l_i należy znaleźć podgrupę l_i-torsion i obliczyć izogenię l_i przy użyciu wzorów Velu. Dzięki sqrt-Velu każdy krok izogenii dla dużej liczby pierwszej wymaga O(sqrt(l_i)) operacji. Cała wymiana kluczy trwa około 1–5 ms na nowoczesnym sprzęcie dla CSIDH-512.

Pierwotny CSIDH nie ma stałego czasu wykonania: liczba kroków Velu zależy od wartości klucza tajnego a_i, co prowadzi do wycieku informacji przez boczne kanały czasowe. CTIDH (Constant-Time ISOGENY Diffie-Hellman, Bernstein i in., 2021) rozwiązuje ten problem, stosując format klucza o stałej wadze oraz starannie zaprojektowane obliczanie izogenii ze stałym czasem wykonania. Klucze tajne CTIDH są ograniczone do wektorów, dla których suma wartości bezwzględnych jest stała (np. sum |a_i| = 130). Obliczanie izogenii przebiega w stałej liczbie kroków, niezależnie od wartości klucza tajnego, z użyciem pozornych obliczeń izogenii do uzupełnienia kroków, w których tajny wykładnik wynosi zero. CTIDH zapewnia bezpieczeństwo podobne do CSIDH-512 oraz ścisłe gwarancje stałego czasu wykonania, odpowiednie dla wdrożeń w systemach wbudowanych.

Bezpieczeństwo kwantowe CSIDH jest bardziej złożone niż w przypadku schematów opartych na kratach. Najlepszy atak kwantowy wykorzystuje algorytm Kuperberga (2005) do rozwiązania problemu ukrytego przesunięcia, który łamie strukturę działania grupy klas w czasie podwykładniczym L(1/2) = exp(O(sqrt(log p))). Jest to znacząco lepszy wynik niż najlepszy klasyczny atak o złożoności sqrt(p), co oznacza, że komputery kwantowe znacznie osłabiają CSIDH w porównaniu z atakami klasycznymi. Aby zapewnić 128-bitowe bezpieczeństwo postkwantowe (wobec ataku L(1/2)), CSIDH wymaga liczby pierwszej p o długości około 5000 bitów (CSIDH-5000) — w porównaniu z 512 bitami dla 128-bitowego bezpieczeństwa klasycznego. Szacuje się, że CSIDH-512 zapewnia zaledwie 62–72 bity bezpieczeństwa kwantowego, czyli znacznie mniej niż wymagania poziomu 1 NIST.

Bezpieczeństwo CSIDH opiera się na problemie odwrotnym działania grupy (GAIP): mając E_A = a * E0 oraz E0, należy znaleźć a. Najlepszy znany algorytm to redukcja w stylu algorytmu Pohliga-Hellmana połączona z algorytmem baby-step-giant-step, działająca klasycznie w czasie O(sqrt(|Cl|)) ~ O(p^{1/4}). Kwantowa trudność tego problemu (Kuperberg) sprawia, że CSIDH jest mniej odporny na ataki kwantowe niż schematy oparte na LWE. Najlepszy atak kwantowy na LWE (przeszukiwanie kraty) zapewnia bardziej zachowawcze marginesy bezpieczeństwa. Zaletą CSIDH jest jego kompaktowość: CSIDH-512 ma klucze publiczne o długości 64 bajtów (zawierające jedynie niezmiennik j), podczas gdy klucze ML-KEM-512 mają 800 bajtów. W zastosowaniach wymagających możliwie najmniejszych kluczy i akceptujących mniejszy margines bezpieczeństwa kwantowego CSIDH pozostaje interesującym rozwiązaniem.

Ograniczenia bezpieczeństwa kwantowego CSIDH są przedmiotem kilku jego wariantów. BSIDH (B od „better”, czyli „lepszy”) wykorzystuje krzywe bazowe wyższego stopnia oraz produkty krzywych eliptycznych, aby zwiększyć rozmiar grupy klas przy zachowaniu wysokiej szybkości obliczeń. Csurf (CSIDH on the surface) operuje na innym zbiorze krzywych supersingularnych, co umożliwia szybsze obliczanie działania grupy. Propozycje CSIDH dla krzywych wyższego rodzaju wykorzystują jakobian krzywych rodzaju 2 nad Fp, zapewniając większą przestrzeń działania grupy i potencjalnie lepsze marginesy bezpieczeństwa kwantowego. Żaden z tych wariantów nie zyskał szerokiej popularności ani nie został uwzględniony przez NIST, częściowo dlatego, że analiza bezpieczeństwa kwantowego wariantów CSIDH wciąż się rozwija i jest mniej dojrzała niż w przypadku schematów opartych na kratach.

CSIDH i SIDH różnią się pod wieloma fundamentalnymi względami. Przemienność: CSIDH wykorzystuje przemienne działanie grupy (grupy klas), natomiast SIDH jest nieinteraktywną wymianą kluczy wykorzystującą nieprzemienne izogenie oraz pomocnicze punkty torsyjne. Ciało bazowe: CSIDH działa nad Fp, a SIDH nad Fp2 (rozszerzeniem kwadratowym). Rozmiar klucza publicznego: CSIDH zajmuje 64 bajty (pojedynczy niezmiennik j nad Fp), natomiast SIDH zajmuje co najmniej 324 bajty (krzywa oraz dwa punkty Fp2). Bezpieczeństwo: CSIDH oparł się atakowi Castrycka-Decru, podczas gdy SIDH został złamany. Bezpieczeństwo kwantowe: CSIDH wymaga liczb pierwszych o długości 5000 bitów, aby zapewnić 128-bitowe bezpieczeństwo kwantowe; przed klasycznym złamaniem SIDH zapewniał porównywalną odporność kwantową. Wydajność: CSIDH-512 działa w około 1–5 ms; SIDH osiągał podobne wyniki, ale CSIDH-5000 byłby znacznie wolniejszy.

Przemienność CSIDH umożliwia nieinteraktywną wymianę kluczy (NIKE): Alicja publikuje E_A = a * E0, a Bob publikuje E_B = b * E0. Później, bez żadnej dalszej komunikacji, każda ze stron może obliczyć wspólny sekret na podstawie klucza publicznego drugiej strony: Alicja oblicza a * E_B = a * (b * E0) = ab * E0, a Bob oblicza b * E_A = b * (a * E0) = ab * E0. Właściwość NIKE jest cenna w zastosowaniach, w których interaktywna wymiana kluczy jest niepraktyczna — na przykład przy szyfrowaniu poczty elektronicznej, gdy nadawca i odbiorca nie są jednocześnie dostępni online. NIKE w CSIDH jest analogiczne do NIKE opartego na Diffiem-Hellmanie, ale zapewnia odporność postkwantową. ML-KEM (oparty na LWE) nie obsługuje w naturalny sposób NIKE bez dodatkowego projektu protokołu.

CSIDH nie został ustandaryzowany i nie jest jeszcze wdrażany w systemach produkcyjnych. Jest aktywnym przedmiotem badań, a dostępne są jego implementacje: CTIDH (działająca w stałym czasie), csidh-reference (w Pythonie, do celów edukacyjnych) oraz supersingular-isogeny-toolbox (zoptymalizowana implementacja w C). Główną przeszkodą we wdrożeniu jest bezpieczeństwo kwantowe: szacuje się, że CSIDH-512 zapewnia 62–72 bity bezpieczeństwa kwantowego, czyli mniej niż poziom 1 NIST (128 bitów), przez co nie nadaje się do zastosowań postkwantowych wymagających zgodności z NIST. CSIDH-5000 spełniałby wymagania bezpieczeństwa, ale byłby zdecydowanie wolniejszy. Trwają badania nad dokładniejszą analizą bezpieczeństwa kwantowego oraz nad wariantami zmniejszającymi tę różnicę, jednak według stanu na 2024 rok CSIDH pozostaje prototypem badawczym, a nie prymitywem gotowym do wdrożenia.

Dlaczego przemienne działanie grupy klas w CSIDH umożliwia nieinteraktywną wymianę kluczy?

CSIDH wykorzystuje przemienne działanie grupy klas Cl(Z[pi]) na krzywych supersingularnych nad Fp, gdzie pi jest endomorfizmem Frobeniusa. Klucze publiczne są pojedynczymi niezmiennikami j (64 bajty). Nie publikuje się pomocniczych punktów torsyjnych, co pozwala uniknąć podatności SIDH. Działanie grupy klas jest przemienne, dzięki czemu możliwa jest NIKE. Najlepszy atak klasyczny ma złożoność O(p^{1/4}), a najlepszy atak kwantowy (Kuperberga) działa w podwykładniczym czasie L(1/2), co oznacza konieczność użycia liczb pierwszych o długości 5000 bitów dla uzyskania 128-bitowego bezpieczeństwa kwantowego. CTIDH zapewnia implementację działającą w stałym czasie. CSIDH-512 zapewnia tylko około 65 bitów bezpieczeństwa kwantowego. CSIDH nie został ustandaryzowany; badania koncentrują się na wariantach zwiększających odporność kwantową przy zachowaniu kompaktowych kluczy.