CSIDH: Değişmeli Süpersingular İzogeni̇ler

CSIDH (Commutative Supersingular Isogeny Diffie-Hellman, Castryck ve diğerleri, 2018), SIDH'in torsiyon noktası sızıntısından tamamen kaçınan ve temelden farklı bir cebirsel yapı kullanan, izojeni tabanlı bir anahtar değişimidir. CSIDH, SIDH'deki gibi Fp2 üzerinde değil, Fp üzerindeki süpersingüler eğrilerle çalışır. Zorluk varsayımı, sınıf grubu etkisinin değişmeli olmasıdır: iki taraf da ortak bir başlangıç eğrisine gizli bir sınıf grubu elemanı uygular ve değişmelilik, her ikisinin de aynı ortak eğriye ulaşmasını sağlar. Hiçbir yardımcı torsiyon noktası bilgisi yayımlanmaz; açık anahtar yalnızca tek bir j-değişmezidir. Bu tasarım, Castryck-Decru'nun SIDH saldırısından etkilenmeden çıktı.

p = 3 mod 4 koşulunu sağlayan Fp üzerinde, süpersingüler E eğrileri ayırt edici bir endomorfizmaya, yani Frobenius olan pi'ye sahiptir ve endomorfizma cebirleri sanal kuadratik düzen Z[pi]'yi içerir. İdeal sınıf grubu Cl(Z[pi]), Fp üzerindeki süpersingüler eğriler kümesi üzerinde (izomorfizmaya kadar) serbest ve geçişli olarak etki eder. Cl(Z[pi]) içindeki bir a ideali, E eğrisine etki ederek a * E adlı yeni bir eğri üretir; bu eğri, E[a]'nın a idealine karşılık gelen torsiyon alt grubu olduğu E/E[a] eğrisi olarak hesaplanır. Bu etki değişmelidir: a * (b * E) = b * (a * E) = [ab] * E. Bu, Diffie-Hellman'ın değişmeli bir benzerini sağlayan CSIDH grup etkisidir.

CSIDH anahtar değişimi şu şekilde gerçekleşir. Açık parametreler: Fp üzerinde bir süpersingüler E0 eğrisi ve küçük tek asallar l_1, ..., l_n. Gizli anahtarlar: Alice, her a_i'nin {-m, ..., m} kümesinde yer aldığı a = (a_1, ..., a_n) değerini seçer; bunlar rastgele küçük tam sayılardır. Bob da b = (b_1, ..., b_n) değerini seçer. Alice'in açık anahtarı: E_A = [l_1^a_1 * ... * l_n^a_n] * E0. Bob'un açık anahtarı: E_B = [l_1^b_1 * ... * l_n^b_n] * E0. Ortak sır: Alice gizli üslerini E_B'ye, Bob ise kendi gizli üslerini E_A'ya uygular. Değişmelilik, her ikisinin de E_AB = [product(l_i^(a_i + b_i))] * E0 değerini elde etmesini sağlar. Ortak sır j(E_AB) değeridir. Hiçbir yardımcı nokta yayımlanmaz.

Referans CSIDH uygulaması, l_1'den l_74'e kadar olan sayıların ilk 74 tek asal (3, 5, 7, ..., 373) olduğu p = 4 * l_1 * l_2 * ... * l_74 - 1 değerini kullanır. Böylece p yaklaşık 512 bit olur. Her gizli anahtar bileşeni a_i, {-5, ..., 5} kümesindedir (bileşen başına 11 seçenek ve toplam 74 bileşen). Sınıf grubunun mertebesi yaklaşık sqrt(p) değerindedir ve anahtar uzayının boyutu 11^74'tür. Her izojeni adımının hesaplanması: her l_i asalı için l_i-torsiyon alt grubunu bulmak ve Velu formüllerini kullanarak l_i-izojenisini hesaplamak gerekir. sqrt-Velu ile her büyük asal izojeni adımı O(sqrt(l_i)) işlem sürer. Toplam anahtar değişimi, modern donanımda CSIDH-512 için yaklaşık 1-5 milisaniye sürer.

Özgün CSIDH sabit süreli değildir: Velu adımlarının sayısı gizli anahtar değerlerine bağlıdır ve zamanlama yan kanalları üzerinden bilgi sızdırır. CTIDH (Constant-Time ISOGENY Diffie-Hellman, Bernstein ve diğerleri, 2021), sabit ağırlıklı bir anahtar biçimi ve özenle tasarlanmış sabit süreli izojeni hesaplaması kullanarak bu sorunu giderir. CTIDH gizli anahtarları, mutlak değerlerin toplamının sabit olduğu vektörlerle sınırlandırılmıştır (örneğin, sum |a_i| = 130). İzojeni hesaplaması, gizli anahtar değerlerinden bağımsız olarak sabit sayıda adımda ilerler; gizli üslerin sıfır olduğu adımları doldurmak için sahte izojeni hesaplamaları kullanılır. CTIDH, gömülü sistemlerde kullanıma uygun katı sabit süre garantileriyle CSIDH-512'ye benzer güvenlik sağlar.

CSIDH'nin kuantum güvenliği, kafes tabanlı şemalara kıyasla daha inceliklidir. Bilinen en iyi kuantum saldırısı, gizli kaydırma problemi için Kuperberg'in 2005 tarihli algoritmasını kullanır; bu algoritma, sınıf grubu etkisi yapısını L(1/2) = exp(O(sqrt(log p))) alt üstel zamanda kırar. Bu, klasik en iyi saldırı olan sqrt(p) saldırısından önemli ölçüde daha iyidir; yani kuantum bilgisayarlar, klasik saldırganlara kıyasla CSIDH'nin güvenliğini ciddi biçimde zayıflatır. Kuantum sonrası 128 bitlik güvenlik için (L(1/2) saldırısına karşı) CSIDH, yaklaşık 5000 bitlik bir p asalı (CSIDH-5000) gerektirir; klasik 128 bitlik güvenlik için ise 512 bit yeterlidir. CSIDH-512'nin kuantum güvenliğinin yalnızca 62-72 bit olduğu tahmin edilmektedir; bu değer, NIST 1. Seviye gereksinimlerinin oldukça altındadır.

CSIDH'nin güvenliği, Grup Etkisi Ters Problemine (GAIP) dayanır: E_A = a * E0 ve E0 verildiğinde a'yı bulun. Bilinen en iyi algoritma, Pohlig-Hellman benzeri indirgemeyi bebek-adım-dev-adım yöntemiyle birleştirir ve klasik olarak O(sqrt(|Cl|)) ~ O(p^{1/4}) zamanda çalışır. Kuantum zorluğu, Kuperberg algoritması nedeniyle CSIDH'yi LWE tabanlı şemalara göre kuantuma daha az dayanıklı kılar. LWE'nin bilinen en iyi kuantum saldırısı olan kafes eleme yöntemi daha ihtiyatlı güvenlik payları sağlar. CSIDH'nin avantajı kompakt olmasıdır: CSIDH-512, 64 baytlık açık anahtarlara (yalnızca j-değişmezi) sahipken ML-KEM-512'nin açık anahtarı 800 bayttır. Mümkün olan en küçük anahtarları gerektiren ve daha düşük kuantum güvenliği paylarını kabul eden uygulamalar için CSIDH ilgi çekici olmaya devam etmektedir.

Çeşitli CSIDH varyantları, CSIDH'nin kuantum güvenliğiyle ilgili sınırlamalarını ele alır. BSIDH ("daha iyi" anlamındaki B), sınıf grubunun boyutunu artırırken hesaplamayı hızlı tutmak için daha yüksek dereceli taban eğrileri ve eliptik eğrilerin çarpımlarını kullanır. Csurf (yüzey üzerindeki CSIDH), grup etkisinin daha hızlı hesaplanmasını sağlamak için farklı bir süpersingüler eğri kümesiyle çalışır. Daha yüksek cinsli CSIDH önerileri, Fp üzerinde cins-2 eğrilerinin Jakobenlerini kullanır; böylece daha iyi kuantum güvenliği payları sağlayabilecek daha geniş bir grup etkisi alanı sunar. Bu varyantların hiçbiri yaygın biçimde benimsenmemiş veya NIST tarafından değerlendirmeye alınmamıştır; bunun nedenlerinden biri, CSIDH varyantlarının kuantum güvenlik analizinin hâlâ gelişmekte olması ve kafes tabanlı şemalara kıyasla daha az olgunlaşmış olmasıdır.

CSIDH ve SIDH, temel yönlerden birbirinden ayrılır. Değişmelilik: CSIDH, değişmeli bir grup etkisi (sınıf grubu) kullanır; SIDH ise yardımcı torsiyon noktalarıyla birlikte değişmeli olmayan izojenileri kullanan etkileşimsiz bir anahtar değişimidir. Taban cismi: CSIDH, Fp üzerinde; SIDH ise Fp2 (ikinci dereceden genişletme) üzerinde çalışır. Açık anahtar boyutu: CSIDH 64 bayttır (Fp üzerinde tek bir j-değişmezi); SIDH ise 324+ bayttır (bir eğri ve iki Fp2 noktası). Güvenlik: CSIDH, Castryck-Decru saldırısından kurtulmuştur; SIDH kırılmıştır. Kuantum güvenliği: CSIDH, 128 bitlik kuantum güvenliği için 5000 bitlik asallar gerektirir; klasik kırılmadan önce SIDH'nin kuantum direnci benzer düzeydeydi. Performans: CSIDH-512 yaklaşık 1-5 ms sürer; SIDH de benzerdi, ancak CSIDH-5000 çok daha yavaş olacaktır.

CSIDH'nin değişmeliliği, etkileşimsiz anahtar değişimini (NIKE) mümkün kılar: Alice, E_A = a * E0 değerini; Bob ise E_B = b * E0 değerini yayımlar. Daha sonra, başka hiçbir iletişim kurmadan herkes paylaşılan sırrı açık anahtarlardan herhangi birini kullanarak hesaplayabilir: Alice, a * E_B = a * (b * E0) = ab * E0 değerini; Bob ise b * E_A = b * (a * E0) = ab * E0 değerini hesaplar. Bu NIKE özelliği, etkileşimli anahtar değişiminin pratik olmadığı uygulamalar için değerlidir; örneğin gönderici ile alıcının aynı anda çevrimiçi olmadığı e-posta şifrelemesi için. CSIDH'den elde edilen NIKE, kuantum sonrası bir Diffie-Hellman NIKE'ına benzer. LWE tabanlı ML-KEM, ek protokol tasarımı olmadan doğal olarak NIKE'ı desteklemez.

CSIDH standardize edilmemiştir ve henüz üretim sistemlerinde kullanılmamaktadır. Aktif bir araştırma konusudur ve çeşitli uygulamaları mevcuttur: CTIDH (sabit zamanlı), csidh-reference (eğitim amacıyla Python) ve supersingular-isogeny-toolbox (optimize edilmiş C). Kullanıma almanın önündeki temel engel kuantum güvenliğidir: CSIDH-512'nin tahmini 62-72 bitlik kuantum güvenliği, NIST 1. Seviyesinin (128 bit) altında kalır; bu nedenle NIST uyumluluğu gerektiren kuantum sonrası uygulamalar için uygun değildir. CSIDH-5000 güvenlik eşiğini karşılayabilir, ancak çok daha yavaş olacaktır. Kuantum güvenlik analizini iyileştirme ve aradaki farkı kapatan varyantlar üzerine araştırmalar sürmektedir; ancak 2024 itibarıyla CSIDH, kullanıma hazır bir temel yapıdan çok bir araştırma prototipi olmayı sürdürmektedir.

CSIDH, pi'nin Frobenius endomorfizması olduğu durumda, Cl(Z[pi]) değişmeli sınıf grubunun Fp üzerindeki süpersingüler eğriler üzerindeki etkisini kullanır. Açık anahtarlar tek bir j-değişmezinden oluşur (64 bayt). Yardımcı torsiyon noktaları yayımlanmadığından SIDH'deki güvenlik açığı önlenir. Sınıf grubu etkisi değişmelidir ve NIKE'ı mümkün kılar. Bilinen en iyi klasik saldırı O(p^{1/4}) zamanda çalışır; bilinen en iyi kuantum saldırısı olan Kuperberg saldırısı L(1/2) alt üstel zamanda çalışır ve 128 bitlik kuantum güvenliği için 5000 bitlik asallar gerektirir. CTIDH, sabit zamanlı bir uygulama sunar. CSIDH-512'nin kuantum güvenliği yalnızca yaklaşık 65 bittir. CSIDH standardize edilmemiştir; araştırmalar, kompakt anahtarları korurken kuantum direncini artıran varyantlara odaklanmaktadır.