Serangan Tebak dan Tentukan pada Masalah Logaritma Diskret Kurva Eliptik

Mereduksi ECDLP ke Penemuan Minor Nol melalui Poset Perpotongan Susunan Hiperbidang

Ayan Mahalanobis· 2026· DOI 10.48550/arXiv.2607.09814

Masalah inti

Masalah logaritma diskret kurva eliptik (ECDLP) menopang keamanan sistem kriptografi kurva eliptik yang banyak digunakan. Diberikan kurva eliptik E atas medan berhingga F_{q}, titik basis P \in E (F_{q}) berorde prima n, dan titik Q = k P, ECDLP menanyakan skalar k \in Z_{n} . Makalah ini melanjutkan karya penulis sebelumnya, yang memperkenalkan algoritma Las Vegas yang mereduksi ECDLP menjadi masalah pencarian minor nol dalam suatu matriks. Kontribusi kali ini mengembangkan algoritma untuk menemukan minor nol tersebut dalam matriks persegi panjang dengan memanfaatkan poset perpotongan suatu susunan hiperbidang. Metodenya elementer, dan makalah ini membahas kompleksitas, probabilitas keberhasilan, serta detail implementasi. Pencarian minor nol dalam matriks juga menarik secara mandiri di luar aplikasi kriptografi.

Makalah ini melaporkan hasil-hasil kunci berikut: - Algoritma Las Vegas yang mereduksi ECDLP menjadi pencarian minor nol dalam matriks persegi panjang. - Algoritma untuk menemukan minor nol menggunakan poset perpotongan suatu susunan hiperbidang. - Analisis kompleksitas yang menunjukkan bahwa waktu jalan bergantung secara polinomial pada dimensi matriks dan ukuran poset perpotongan. - Batas probabilitas keberhasilan yang dinyatakan dalam rank matriks dan jumlah hiperbidang. - Detail implementasi yang menunjukkan kelayakan pendekatan ini pada instans kecil. Penulis menekankan bahwa metodenya elementer dan tidak bergantung pada geometri aljabar tingkat lanjut atau teori bilangan yang berat. Reduksi ke penemuan minor nol menarik secara mandiri, karena menghubungkan ECDLP dengan teori matriks kombinatorial.

Masalah logaritma diskret kurva eliptik (ECDLP) menopang keamanan sistem kriptografi kurva eliptik yang banyak digunakan. Diberikan kurva eliptik E atas medan berhingga F_{q}, titik basis P \in E (F_{q}) berorde prima n, dan titik Q = k P, ECDLP menanyakan skalar k \in Z_{n} . Makalah ini melanjutkan karya penulis sebelumnya, yang memperkenalkan algoritma Las Vegas yang mereduksi ECDLP menjadi masalah pencarian minor nol dalam suatu matriks. Kontribusi kali ini mengembangkan algoritma untuk menemukan minor nol tersebut dalam matriks persegi panjang dengan memanfaatkan poset perpotongan suatu susunan hiperbidang. Metodenya elementer, dan makalah ini membahas kompleksitas, probabilitas keberhasilan, serta detail implementasi. Pencarian minor nol dalam matriks juga menarik secara mandiri di luar aplikasi kriptografi.

Metodologi inti berlangsung dalam dua tahap. Pertama, instans ECDLP ditransformasikan menjadi matriks yang entri-entrinya bergantung pada kurva, titik P dan Q, serta himpunan parameter tebakan. Solusi ECDLP bersesuaian dengan minor nol dari matriks ini. Kedua, pencarian minor nol dirumuskan ulang sebagai masalah kombinatorial atas suatu susunan hiperbidang. Setiap kondisi baris atau kolom mendefinisikan sebuah hiperbidang dalam ruang parameter, dan poset perpotongan susunan tersebut mengodekan ketergantungan antar kondisi ini.

Signifikansi karya ini terletak pada reduksi baru ECDLP menjadi masalah kombinatorial. Meskipun algoritma ini tidak diklaim berjalan dalam waktu polinomial untuk semua instans, ia menyediakan sudut serangan baru yang mungkin menginspirasi penelitian lanjutan. Penggunaan susunan hiperbidang dan poset perpotongan merupakan pendekatan segar dalam konteks ECDLP. Sifat Las Vegas menjamin kebenaran, tetapi waktu jalan yang diharapkan mungkin tinggi untuk ukuran parameter kriptografi. Penulis membahas batasan dan potensi optimasi, seperti memparalelkan pencarian pada poset perpotongan atau menggunakan pemangkasan heuristik. Dari perspektif keamanan, serangan ini saat ini tidak mengancam sistem kriptografi kurva eliptik standar, tetapi menyoroti pentingnya memahami kompleksitas ECDLP dari berbagai perspektif. Makalah ini juga berkontribusi pada masalah yang lebih luas yaitu pencarian minor nol dalam matriks, yang memiliki aplikasi dalam teori pengkodean dan kompleksitas aljabar. Karya mendatang dapat mengeksplorasi batas kompleksitas yang lebih ketat, probabilitas keberhasilan yang lebih baik, dan perluasan ke masalah logaritma diskret lainnya.

Praktisi dan peneliti ilmu komputer

Membuka konten member…