Ini adalah pekerjaan untuk LLL: Berikan basis kisi multidimensional pada LLL, dan ia akan menghasilkan yang lebih baik. Proses ini dikenal sebagai reduksi basis kisi.
Apa hubungannya semua ini dengan kriptografi? Ternyata, tugas untuk merusak sistem kriptografi dapat, dalam beberapa kasus, diubah sebagai masalah lain: menemukan vektor yang relatif pendek dalam kisi. Dan kadang-kadang, vektor itu dapat diambil dari basis yang direduksi yang dihasilkan oleh algoritma gaya LLL. Strategi ini telah membantu para peneliti menggulingkan sistem yang, pada permukaannya, tampaknya memiliki sedikit hubungan dengan kisi.
Secara teoritis, algoritma LLL asli berjalan dengan cepat: Waktu yang dibutuhkan untuk menjalankannya tidak meningkat secara eksponensial dengan ukuran masukan—yaitu, dimensi kisi dan ukuran (dalam bit) dari angka dalam vektor basis. Tetapi waktu yang dibutuhkan meningkat sebagai fungsi polinomial, dan “jika Anda benar-benar ingin melakukannya, waktu polinomial tidak selalu mudah,” kata Léo Ducas, seorang ahli kriptografi di institut penelitian nasional CWI di Belanda.
Dalam praktiknya, ini berarti bahwa algoritma LLL asli tidak dapat menangani masukan yang terlalu besar. “Matematikawan dan kriptografer ingin memiliki kemampuan untuk melakukan lebih banyak hal,” kata Keegan Ryan, seorang mahasiswa doktoral di Universitas California, San Diego. Para peneliti bekerja untuk mengoptimalkan algoritma gaya LLL agar dapat menampung masukan yang lebih besar, seringkali mencapai kinerja yang baik. Namun, beberapa tugas tetap sulit dijangkau.
Makalah baru ini, yang ditulis oleh Ryan dan pembimbingnya, Nadia Heninger, menggabungkan beberapa strategi untuk meningkatkan efisiensi algoritma gaya LLL-nya. Salah satunya, teknik ini menggunakan struktur rekursif yang memecah tugas menjadi bagian-bagian yang lebih kecil. Selain itu, algoritma ini mengelola presisi angka yang terlibat dengan hati-hati, menemukan keseimbangan antara kecepatan dan hasil yang benar. Karya baru ini memungkinkan para peneliti untuk mengurangi basis-basis kisi dengan ribuan dimensi.
Karya sebelumnya telah mengikuti pendekatan serupa: Sebuah makalah tahun 2021 juga menggabungkan rekursi dan pengelolaan presisi untuk menyelesaikan dengan cepat kisi-kisi besar, tetapi hanya berhasil untuk jenis kisi tertentu, dan bukan semua yang penting dalam kriptografi. Algoritma baru ini berperilaku dengan baik pada rentang yang jauh lebih luas. “Saya sangat senang seseorang melakukannya,” kata Thomas Espitau, seorang peneliti kriptografi di perusahaan PQShield dan salah satu penulis versi 2021. Karya timnya menawarkan “bukti konsep,” katanya; hasil baru ini menunjukkan bahwa “Anda dapat melakukan reduksi kisi dengan cepat secara akurat.”
Teknik baru ini sudah mulai terbukti berguna. Aurel Page, seorang ahli matematika dari institut penelitian nasional Prancis Inria, mengatakan bahwa dia dan timnya telah menggunakan adaptasi algoritma ini untuk menyelesaikan beberapa tugas teori bilangan komputasi.
Algoritma gaya LLL juga dapat berperan dalam penelitian terkait sistem kriptografi berbasis kisi yang dirancang untuk tetap aman bahkan di masa depan dengan komputer kuantum yang kuat. Mereka tidak mengancam sistem seperti itu, karena menghancurkannya membutuhkan menemukan vektor yang lebih pendek daripada yang dapat dicapai oleh algoritma-algoritma ini. Tetapi serangan terbaik yang diketahui peneliti menggunakan algoritma gaya LLL sebagai “blok dasar,” kata Wessel van Woerden, seorang kriptografer di Universitas Bordeaux. Dalam eksperimen praktis untuk mempelajari serangan-serangan ini, blok dasar tersebut dapat melambatkan segalanya. Dengan menggunakan alat baru ini, para peneliti mungkin dapat memperluas rentang eksperimen yang dapat mereka jalankan pada algoritma serangan tersebut, menawarkan gambaran yang lebih jelas tentang kinerjanya.
Cerita asli dicetak ulang dengan izin dari Quanta Magazine, sebuah publikasi independen secara editorial dari Simons Foundation yang misinya adalah meningkatkan pemahaman publik tentang ilmu pengetahuan dengan meliput perkembangan penelitian dan tren dalam matematika serta ilmu pengetahuan fisik dan hayati.