Isogeni Kurva Eliptik: Dasar Matematis

Isogeni antara dua kurva eliptik E dan E' di atas medan k adalah pemetaan rasional non-konstan phi: E -> E' yang juga merupakan homomorfisme grup — pemetaan tersebut mengubah operasi grup pada E menjadi operasi grup pada E'. Setiap isogeni phi memiliki isogeni dual phi_hat: E' -> E sehingga phi_hat yang dikomposisikan dengan phi sama dengan perkalian oleh deg(phi) pada E. Derajat suatu isogeni adalah ukuran kernelnya: isogeni berderajat-l memiliki kernel berukuran l. Isogeni menggeneralisasi perkalian skalar: perkalian dengan n merupakan isogeni dari E ke dirinya sendiri dengan derajat n^2. Isogeni di atas medan hingga dihitung sebagai fungsi rasional (polinom) yang dapat dievaluasi secara efisien.

Rumus Velu (1971) menyediakan rumus eksplisit untuk menghitung isogeni phi: E -> E/G berdasarkan suatu subgrup G dari E. Kurva hasil pemetaan E/G = E' dan pemetaan rasional phi sepenuhnya ditentukan oleh G. Rumus Velu menghitung koefisien kurva hasil pemetaan dan pemetaan rasional sebagai fungsi rasional yang derajatnya sama dengan |G|. Untuk subgrup kernel G berorde prima l, isogeni tersebut berderajat l dan dapat dihitung dengan O(l) operasi. Algoritma sqrt-Velu (Bernstein dkk., 2019) menguranginya menjadi O(sqrt(l)) operasi untuk l yang besar sehingga memungkinkan isogeni prima besar CSIDH yang efisien. Rumus Velu merupakan mesin komputasi utama bagi semua kriptografi berbasis isogeni.

Kurva eliptik di atas medan hingga Fp dapat diatur dalam sebuah graf isogeni. Titik sudutnya adalah invarian-j dari kurva eliptik (invarian kanonik yang menentukan kurva hingga isomorfisme). Sisinya adalah isogeni-l: setiap kurva biasa memiliki tepat l+1 isogeni-l keluar untuk bilangan prima kecil l (berdasarkan struktur subgrup torsi-l). Graf isogeni-l di atas Fp merupakan graf reguler-(l+1). Sifat Ramanujan dari graf-graf ini (graf ekspansi) berarti jalan acak di dalamnya cepat menyebar secara merata, sehingga menyediakan asumsi kesulitan yang mendasari kriptografi berbasis isogeni: jalan acak dengan panjang O(log p) menghasilkan distribusi seragam atas invarian-j.

Kurva eliptik di atas Fp terbagi menjadi dua kategori. Kurva biasa memiliki peringkat-p non-trivial, yang berarti terdapat p^2 kelas isomorfisme dan graf isogeni kompleks dengan struktur gunung berapi (kawah dan dasar). Kurva supersingular memiliki peringkat-p 0 dan semuanya berada dalam satu graf isogeni terhubung di atas Fp2. Jumlah invarian-j supersingular di atas Fp kira-kira p/12. SIDH dan SIKE menggunakan kurva supersingular karena graf isogeninya merupakan graf Ramanujan dengan sifat ekspansi yang kuat dan tidak memiliki struktur gunung berapi yang dapat mengungkapkan arah lintasan. CSIDH juga menggunakan kurva supersingular, tetapi di atas Fp (bukan Fp2), dengan memanfaatkan struktur aljabar yang berbeda.

Kriptografi berbasis isogeni didasarkan pada dua masalah sulit yang berkaitan. Masalah Isogeni Supersingular (SSIP): jika diberikan dua kurva eliptik supersingular E dan E' di atas Fp2, temukan isogeni phi: E -> E'. Masalah Isogeni Supersingular Komputasional (CSSI): jika diberikan E, E' = phi(E), dan derajat phi, temukan phi. Algoritma klasik terbaik untuk SSIP memerlukan waktu O(p^{1/4}). Algoritma kuantum terbaik (algoritma Tani untuk mencari pasangan dengan keluaran sama) memerlukan waktu O(p^{1/6}). Untuk p = 2^{434}, ini memberikan keamanan klasik 128 bit. Percepatan kuantum ini jauh lebih kecil daripada percepatan eksponensial algoritma Shor terhadap RSA/ECC, sehingga skema berbasis isogeni aman pascakuantum.

SIDH (Diffie-Hellman Isogeni Supersingular) menggunakan bilangan prima berstruktur khusus p = 2^a * 3^b - 1 yang memastikan kurva E di atas Fp2 memiliki titik torsi-2^a (kumpulan titik P dengan 2^a * P = 0) serta titik torsi-3^b yang dapat diakses. Rahasia Alice adalah isogeni-2^a phi_A: E -> E_A dengan kernel yang dibangkitkan oleh elemen acak dari torsi-2^a. Rahasia Bob adalah isogeni-3^b phi_B: E -> E_B. Mereka bertukar citra titik torsi: Alice mempublikasikan E_A dan phi_A(P_B), phi_A(Q_B). Bob mempublikasikan E_B dan phi_B(P_A), phi_B(Q_A). Dengan demikian, masing-masing pihak dapat menghitung isogeni dari kurva pihak lain dan memperoleh invarian-j bersama yang sama.

Cincin endomorfisme End(E) dari sebuah kurva eliptik adalah cincin semua isogeni dari E ke dirinya sendiri (termasuk perkalian skalar). Untuk kurva biasa di atas Fp, End(E) merupakan suatu orde dalam medan kuadratik imajiner. Untuk kurva supersingular, End(E) merupakan orde maksimal dalam aljabar kuaternion yang bercabang di p dan tak hingga. Struktur End(E) sepenuhnya menentukan kurva hingga isomorfisme. Masalah cincin endomorfisme — menghitung End(E) jika E diberikan — diyakini sulit (setara dengan SSIP untuk kurva supersingular). Serangan Castryck-Decru terhadap SIDH/SIKE memanfaatkan informasi tambahan yang bocor dalam protokol SIDH untuk merekonstruksi sebagian cincin endomorfisme secara efisien sehingga mematahkan skema tersebut.

Isogeni berderajat-l phi: E -> E' dapat direpresentasikan sebagai polinom berderajat l (atau l/2 setelah optimasi simetri dengan memanfaatkan fakta bahwa invers titik memiliki koordinat-x yang sama). Menghitung phi(P) untuk titik P tertentu memerlukan O(l) perkalian menggunakan rumus Velu. Untuk SIDH dengan l = 2^a sekitar 2^216, hal ini tampak tidak layak, tetapi SIDH memanfaatkan fakta bahwa isogeni-2^a dapat diuraikan menjadi rantai yang terdiri atas a isogeni-2 terpisah — setiap isogeni-2 murah dihitung, dan rantai sepanjang a langkah menghasilkan isogeni-2^a. Hal yang sama berlaku untuk 3^b. sqrt-Velu memungkinkan perhitungan isogeni prima ganjil besar CSIDH berjalan dalam O(sqrt(l)), bukan O(l), sehingga CSIDH menjadi praktis.

SIKE (Enkapsulasi Kunci Isogeni Supersingular) adalah kandidat PQC NIST yang bertahan di semua putaran hingga putaran keempat, ketika berhasil dipatahkan. SIKE dikenal memiliki ukuran kunci paling kecil di antara semua kandidat NIST: 374 bita untuk SIKEp434 (Tingkat NIST 1). Sebagai perbandingan, ML-KEM-512 memiliki kunci publik berukuran 800 bita. SIKE mencapai ukuran yang ringkas ini karena rahasia bersama diturunkan dari satu invarian-j (elemen medan berukuran sekitar 430 bit). Kekompakan tersebut harus dibayar dengan kinerja: SIKE 100–1000 kali lebih lambat daripada kandidat lainnya. Ketika Castryck dan Decru mematahkan SIKE pada Juli 2022 menggunakan serangan klasik yang berjalan dalam hitungan menit pada komputer jinjing, SIKE langsung tersingkir dari kompetisi NIST.

Kriptografi berbasis isogeni menempati posisi unik di antara pendekatan pascakuantum. Ukuran kunci: jauh lebih kecil daripada kriptografi berbasis kisi (ML-KEM: 800+ bita) atau tanda tangan berbasis hash (SLH-DSA: kunci publik 32–49 bita, tetapi tanda tangan 7856–49856 bita). Kinerja: jauh lebih lambat daripada semua alternatif (SIKE 100–1000 kali lebih lambat daripada ML-KEM). Asumsi keamanan: berbeda dari LWE (yang digunakan dalam ML-KEM/ML-DSA), SIS, atau fungsi hash — sehingga menyediakan keberagaman kriptografis. Dasar keamanan pascakuantum: masalah lintasan isogeni tidak memiliki algoritma kuantum waktu polinomial yang diketahui, tidak seperti RSA/ECC yang dapat dipatahkan sepenuhnya oleh algoritma Shor. Pematahan klasik terhadap SIKE menunjukkan bahwa tingkat kesulitan isogeni masih terus dipahami, tidak seperti masalah LWE yang telah dipelajari secara mendalam.

Meskipun SIKE telah dipatahkan, kriptografi berbasis isogeni tetap menjadi bidang riset yang aktif. SQISign (Tanda Tangan Kuaternion dan Isogeni Singkat) adalah skema tanda tangan berbasis isogeni dengan tanda tangan 177 bita (dibandingkan dengan 2420 bita milik ML-DSA untuk Tingkat 2) — tanda tangan PQC terkecil yang diketahui. SQISign menggunakan masalah sulit berupa penghitungan isogeni dengan derajat yang ditentukan antara dua kurva supersingular yang diberikan, yang diformalkan sebagai masalah cincin endomorfisme. FESTA (Enkripsi Cepat dari Serangan Torsi Supersingular) adalah rancangan KEM baru yang menghindari data tambahan pendukung titik torsi yang membuat SIDH rentan. CTIDH (CSIDH Waktu-Konstan) meningkatkan kinerja CSIDH. Skema-skema ini menjaga relevansi riset isogeni bahkan setelah SIKE tersingkir.

Apa yang dimaksud dengan isogeni antara kurva eliptik?

Isogeni adalah pemetaan rasional phi: E -> E' yang merupakan homomorfisme grup, dengan derajat yang sama dengan ukuran kernelnya. Rumus Velu menghitung kurva hasil pemetaan dan pemetaan tersebut dari subgrup kernel. Graf isogeni mengatur kurva sebagai titik sudut dengan sisi isogeni-l yang membentuk graf Ramanujan reguler-(l+1). Kurva supersingular (yang digunakan dalam SIDH/SIKE/CSIDH) memiliki graf isogeni dengan ekspansi yang kuat. Masalah SSIP dan CSSI menjadi dasar keamanan isogeni. SIDH menggunakan struktur titik torsi dengan rantai isogeni-2 dan isogeni-3 yang berselang-seling. Penghitungan cincin endomorfisme setara dengan SSIP. SQISign dan FESTA mewakili arah riset pasca-SIKE yang aktif dengan memanfaatkan kesulitan masalah cincin endomorfisme.