CSIDH: Isogeni Supersingular Komutatif

CSIDH (Commutative Supersingular Isogeny Diffie-Hellman, Castryck dkk., 2018) adalah pertukaran kunci berbasis isogeni yang sepenuhnya menghindari kebocoran titik torsi SIDH dengan menggunakan struktur aljabar yang berbeda secara mendasar. CSIDH bekerja dengan kurva supersingular di atas Fp (bukan Fp2 seperti pada SIDH). Asumsi kesulitannya adalah komutativitas aksi grup kelas: masing-masing pihak menerapkan elemen grup kelas rahasia pada kurva awal bersama, dan komutativitas memastikan keduanya tiba pada kurva bersama yang sama. Tidak ada informasi titik torsi tambahan yang dipublikasikan—kunci publik hanya berupa satu invarian-j. Rancangan ini bertahan dari serangan Castryck-Decru terhadap SIDH.

Di atas Fp dengan p = 3 mod 4, kurva supersingular E memiliki endomorfisme khusus pi (Frobenius), dan aljabar endomorfismenya memuat orde kuadratik imajiner Z[pi]. Grup kelas ideal Cl(Z[pi]) bertindak secara bebas dan transitif pada himpunan kurva supersingular di atas Fp (hingga isomorfisme). Suatu ideal a dalam Cl(Z[pi]) bertindak pada kurva E untuk menghasilkan kurva baru a * E, yang dihitung sebagai kurva E/E[a], dengan E[a] sebagai subgrup torsi yang bersesuaian dengan ideal a. Aksi ini bersifat komutatif: a * (b * E) = b * (a * E) = [ab] * E. Inilah aksi grup CSIDH yang menyediakan analog komutatif dari Diffie-Hellman.

Pertukaran kunci CSIDH berlangsung sebagai berikut. Parameter publik: kurva supersingular E0 di atas Fp dan bilangan prima ganjil kecil l_1, ..., l_n. Kunci rahasia: Alice memilih a = (a_1, ..., a_n), dengan setiap a_i berada dalam {-m, ..., m} (bilangan bulat kecil acak). Bob memilih b = (b_1, ..., b_n). Kunci publik Alice: E_A = [l_1^a_1 * ... * l_n^a_n] * E0. Kunci publik Bob: E_B = [l_1^b_1 * ... * l_n^b_n] * E0. Rahasia bersama: Alice menerapkan eksponen rahasianya pada E_B; Bob menerapkannya pada E_A. Komutativitas memastikan keduanya memperoleh E_AB = [product(l_i^(a_i + b_i))] * E0. Rahasia bersama adalah j(E_AB). Tidak ada titik tambahan yang dipublikasikan.

Implementasi rujukan CSIDH menggunakan p = 4 * l_1 * l_2 * ... * l_74 - 1, dengan l_1 hingga l_74 adalah 74 bilangan prima ganjil pertama (3, 5, 7, ..., 373). Ini menghasilkan p yang berukuran sekitar 512 bit. Setiap komponen kunci rahasia a_i berada dalam {-5, ..., 5} (11 pilihan per komponen, 74 komponen). Orde grup kelas kira-kira sebesar sqrt(p), dan ruang kuncinya berukuran 11^74. Penghitungan setiap langkah isogeni: untuk setiap bilangan prima l_i, temukan subgrup torsi-l_i dan hitung isogeni-l_i menggunakan rumus Velu. Dengan sqrt-Velu, setiap langkah isogeni untuk bilangan prima besar memerlukan O(sqrt(l_i)) operasi. Total pertukaran kunci: sekitar 1–5 ms pada perangkat keras modern untuk CSIDH-512.

CSIDH asli tidak memiliki waktu konstan: jumlah langkah Velu bergantung pada nilai kunci rahasia a_i, sehingga membocorkan informasi melalui saluran samping waktu. CTIDH (Constant-Time ISOGENY Diffie-Hellman, Bernstein dkk., 2021) memperbaiki hal ini dengan menggunakan format kunci berbobot tetap dan penghitungan isogeni waktu-konstan yang dirancang secara cermat. Kunci rahasia CTIDH dibatasi pada vektor yang jumlah nilai absolutnya tetap (misalnya, jumlah |a_i| = 130). Penghitungan isogeni berlangsung dalam jumlah langkah tetap tanpa memedulikan nilai kunci rahasia, menggunakan penghitungan isogeni tiruan untuk mengisi langkah ketika eksponen rahasia bernilai nol. CTIDH mencapai keamanan yang serupa dengan CSIDH-512, disertai jaminan waktu-konstan yang ketat dan sesuai untuk penerapan pada perangkat tertanam.

Keamanan kuantum CSIDH lebih bernuansa dibandingkan skema berbasis kisi. Serangan kuantum terbaik menggunakan algoritme Kuperberg (2005) untuk masalah pergeseran tersembunyi, yang mematahkan struktur aksi grup kelas dalam waktu subeksponensial L(1/2) = exp(O(sqrt(log p))). Ini jauh lebih baik daripada serangan klasik terbaik sqrt(p), yang berarti komputer kuantum secara signifikan melemahkan CSIDH dibandingkan penyerang klasik. Untuk keamanan pascakuantum 128 bit (terhadap serangan L(1/2)), CSIDH memerlukan bilangan prima p berukuran sekitar 5000 bit (CSIDH-5000), dibandingkan 512 bit untuk keamanan klasik 128 bit. CSIDH-512 diperkirakan hanya memiliki keamanan kuantum 62–72 bit, jauh di bawah persyaratan Tingkat 1 NIST.

Keamanan CSIDH bergantung pada Masalah Invers Aksi Grup (GAIP): jika diberikan E_A = a * E0 dan E0, carilah a. Algoritme terbaik yang diketahui adalah reduksi mirip Pohlig-Hellman yang digabungkan dengan langkah-kecil-langkah-besar, yang secara klasik berjalan dalam O(sqrt(|Cl|)) ~ O(p^{1/4}). Kesulitan kuantum (Kuperberg) membuat CSIDH kurang aman terhadap kuantum dibandingkan skema berbasis LWE. Serangan kuantum terbaik pada LWE (penyaringan kisi) memberikan margin keamanan yang lebih konservatif. Keunggulan CSIDH adalah kekompakannya: CSIDH-512 memiliki kunci publik 64 byte (hanya invarian-j), sedangkan ML-KEM-512 memiliki 800 byte. Untuk aplikasi yang memerlukan kunci sekecil mungkin dan menerima margin keamanan kuantum yang lebih rendah, CSIDH tetap menarik.

Beberapa varian CSIDH mengatasi keterbatasan keamanan kuantumnya. BSIDH (B untuk "lebih baik") menggunakan kurva dasar berderajat lebih tinggi dan hasil kali kurva eliptik untuk memperbesar ukuran grup kelas sambil mempertahankan komputasi yang cepat. Csurf (CSIDH pada permukaan) bekerja dengan sekumpulan kurva supersingular yang berbeda untuk memungkinkan penghitungan aksi grup yang lebih cepat. Usulan CSIDH bergenus lebih tinggi menggunakan Jacobian kurva bergenus-2 di atas Fp, sehingga menyediakan ruang aksi grup yang lebih besar dengan margin keamanan kuantum yang berpotensi lebih baik. Belum ada satu pun varian ini yang diadopsi secara luas atau dipertimbangkan oleh NIST, sebagian karena analisis keamanan kuantum varian CSIDH masih berkembang dan belum sematang analisis untuk skema berbasis kisi.

CSIDH dan SIDH berbeda dalam hal-hal mendasar. Komutativitas: CSIDH menggunakan aksi grup komutatif (grup kelas); SIDH adalah pertukaran kunci non-interaktif yang menggunakan isogeni nonkomutatif dengan titik torsi tambahan. Medan dasar: CSIDH bekerja di atas Fp; SIDH di atas Fp2 (perluasan kuadratik). Ukuran kunci publik: CSIDH berukuran 64 byte (satu invarian-j di atas Fp); SIDH berukuran 324+ byte (kurva + dua titik Fp2). Keamanan: CSIDH bertahan dari serangan Castryck-Decru; SIDH berhasil dipatahkan. Keamanan kuantum: CSIDH memerlukan bilangan prima 5000 bit untuk keamanan kuantum 128 bit; SIDH memiliki ketahanan kuantum yang sebanding sebelum pematahan klasik. Kinerja: CSIDH-512 memerlukan sekitar 1–5 ms; SIDH serupa, tetapi CSIDH-5000 akan jauh lebih lambat.

Komutativitas CSIDH memungkinkan pertukaran kunci non-interaktif (NIKE): Alice menerbitkan E_A = a * E0; Bob menerbitkan E_B = b * E0. Kemudian, tanpa komunikasi lebih lanjut, siapa pun dapat menghitung rahasia bersama dari salah satu kunci publik: Alice menghitung a * E_B = a * (b * E0) = ab * E0; Bob menghitung b * E_A = b * (a * E0) = ab * E0. Sifat NIKE ini berharga untuk aplikasi yang membuat pertukaran kunci interaktif tidak praktis — misalnya, enkripsi email ketika pengirim dan penerima tidak sedang daring secara bersamaan. NIKE dari CSIDH serupa dengan NIKE Diffie-Hellman, tetapi bersifat pascakuantum. ML-KEM (berbasis LWE) tidak secara alami mendukung NIKE tanpa rancangan protokol tambahan.

CSIDH belum distandardisasi dan belum diterapkan dalam sistem produksi. CSIDH merupakan topik riset aktif dengan beberapa implementasi yang tersedia: CTIDH (waktu-konstan), csidh-reference (Python, untuk pedagogi), dan supersingular-isogeny-toolbox (C yang dioptimalkan). Hambatan utama penerapan adalah keamanan kuantum: keamanan kuantum CSIDH-512 yang diperkirakan sebesar 62–72 bit berada di bawah Tingkat 1 NIST (128 bit), sehingga tidak cocok untuk aplikasi pascakuantum yang memerlukan kepatuhan terhadap NIST. CSIDH-5000 akan memenuhi ambang keamanan tersebut, tetapi akan jauh lebih lambat. Riset terus berlanjut untuk meningkatkan analisis keamanan kuantum dan mengembangkan varian yang menutup kesenjangan ini, tetapi hingga 2024 CSIDH tetap merupakan purwarupa riset, bukan primitif yang siap diterapkan.

CSIDH menggunakan aksi grup kelas komutatif dari Cl(Z[pi]) pada kurva supersingular di atas Fp, dengan pi sebagai endomorfisme Frobenius. Kunci publiknya berupa satu invarian-j (64 byte). Tidak ada titik torsi tambahan yang diterbitkan, sehingga kerentanan SIDH dapat dihindari. Aksi grup kelas bersifat komutatif, sehingga memungkinkan NIKE. Serangan klasik terbaik adalah O(p^{1/4}); serangan kuantum terbaik (Kuperberg) berjalan dalam waktu subeksponensial L(1/2), sehingga diperlukan bilangan prima 5000 bit untuk keamanan kuantum 128 bit. CTIDH menyediakan implementasi waktu-konstan. CSIDH-512 hanya memiliki sekitar 65 bit keamanan kuantum. CSIDH belum distandardisasi; riset berfokus pada varian yang meningkatkan ketahanan kuantum sambil mempertahankan kunci yang ringkas.