Algoritma Kriptografi Terkenal Mendapat Peningkatan | Majalah Kuanta

Dalam kehidupan kita yang semakin digital, keamanan bergantung pada kriptografi. Kirim pesan pribadi atau bayar tagihan secara online, dan Anda mengandalkan algoritma yang dirancang untuk menjaga rahasia data Anda. Tentu saja, beberapa orang ingin mengungkap rahasia tersebut — jadi para peneliti berupaya menguji kekuatan sistem ini untuk memastikan sistem tersebut tidak hancur di tangan penyerang yang cerdik.

Salah satu alat penting dalam pekerjaan ini adalah algoritma LLL, yang dinamai sesuai nama penelitinya menerbitkannya pada tahun 1982 — Arjen Lenstra, Hendrik Lenstra Jr. dan László Lovász. LLL, bersama dengan banyak turunannya, dapat merusak skema kriptografi dalam beberapa kasus; mempelajari bagaimana mereka berperilaku membantu peneliti merancang sistem yang tidak terlalu rentan terhadap serangan. Dan bakat algoritma ini melampaui kriptografi: Ini juga merupakan alat yang berguna dalam bidang matematika tingkat lanjut seperti teori bilangan komputasi.

Selama bertahun-tahun, para peneliti telah menyempurnakan varian LLL untuk membuat pendekatan ini lebih praktis – namun hanya sampai pada titik tertentu. Kini, sepasang kriptografer telah membangun algoritma gaya LLL baru dengan peningkatan efisiensi yang signifikan. Teknik baru, yang memenangkan Penghargaan Kertas Terbaik di Konferensi Kriptologi Internasional 2023, memperluas cakupan skenario di mana ilmuwan komputer dan matematikawan dapat menggunakan pendekatan mirip LLL.

“Itu sangat menarik,” kata Chris Peikert, seorang kriptografer di Universitas Michigan yang tidak terlibat dalam makalah ini. Alat ini telah menjadi fokus penelitian selama beberapa dekade, katanya. “Selalu menyenangkan ketika sebuah target yang telah dikerjakan begitu lama… menunjukkan bahwa masih ada kejutan yang bisa ditemukan.”

Algoritme tipe LLL beroperasi di dunia kisi: kumpulan titik-titik yang berjarak teratur tak terbatas. Sebagai salah satu cara untuk memvisualisasikannya, bayangkan Anda sedang memasang ubin di lantai. Anda dapat menutupinya dengan ubin persegi, dan sudut ubin tersebut akan menjadi satu kisi. Alternatifnya, Anda dapat memilih bentuk ubin yang berbeda — misalnya, jajaran genjang panjang — untuk membuat kisi yang berbeda.

Sebuah kisi dapat dideskripsikan menggunakan “basisnya”. Ini adalah sekumpulan vektor (pada dasarnya, daftar angka) yang dapat Anda gabungkan dengan berbagai cara untuk mendapatkan setiap titik dalam kisi. Mari kita bayangkan sebuah kisi dengan basis yang terdiri dari dua vektor: [3, 2] dan [1, 4]. Kisi hanyalah semua titik yang dapat Anda capai dengan menjumlahkan dan mengurangi salinan vektor-vektor tersebut.

Pasangan vektor tersebut bukanlah satu-satunya basis kisi. Setiap kisi dengan setidaknya dua dimensi mempunyai kemungkinan basis yang tak terhingga banyaknya. Namun tidak semua pangkalan diciptakan sama. Basis yang vektor-vektornya lebih pendek dan mendekati sudut siku-siku satu sama lain biasanya lebih mudah untuk dikerjakan dan lebih berguna untuk menyelesaikan beberapa masalah komputasi, sehingga para peneliti menyebut basis tersebut “baik.” Contohnya adalah pasangan vektor berwarna biru pada gambar di bawah. Basis yang terdiri dari vektor yang lebih panjang dan kurang ortogonal — seperti vektor merah — dapat dianggap “buruk”.

Ini adalah tugas untuk LLL: Berikan (atau saudara-saudaranya) dasar kisi multidimensi, dan itu akan menghasilkan kisi yang lebih baik. Proses ini dikenal sebagai reduksi basis kisi.

Apa hubungannya semua ini dengan kriptografi? Ternyata tugas memecahkan sistem kriptografi, dalam beberapa kasus, dapat diubah menjadi masalah lain: menemukan vektor yang relatif pendek dalam sebuah kisi. Dan terkadang, vektor tersebut dapat diambil dari basis tereduksi yang dihasilkan oleh algoritma gaya LLL. Strategi ini telah membantu para peneliti menggulingkan sistem yang, pada permukaannya, tampaknya tidak ada hubungannya dengan kisi-kisi.

Secara teoritis, algoritma LLL yang asli berjalan dengan cepat: Waktu yang diperlukan untuk menjalankannya tidak berskala eksponensial dengan ukuran masukan — yaitu, dimensi kisi dan ukuran (dalam bit) angka-angka di dalam vektor dasar. Namun hal ini meningkat sebagai fungsi polinomial, dan “jika Anda benar-benar ingin melakukannya, waktu polinomial tidak selalu memungkinkan,” kata Leo Ducas, seorang kriptografer di lembaga penelitian nasional CWI di Belanda.

Dalam praktiknya, ini berarti algoritma LLL asli tidak dapat menangani input yang terlalu besar. “Matematikawan dan kriptografer menginginkan kemampuan untuk berbuat lebih banyak,” katanya Keegan Ryan, seorang mahasiswa doktoral di Universitas California, San Diego. Para peneliti bekerja untuk mengoptimalkan algoritma gaya LLL untuk mengakomodasi masukan yang lebih besar, seringkali mencapai kinerja yang baik. Namun, masih ada beberapa tugas yang masih berada di luar jangkauan.

Makalah baru, yang ditulis oleh Ryan dan penasihatnya, Nadia Heninger, menggabungkan beberapa strategi untuk meningkatkan efisiensi algoritma gaya LLL-nya. Salah satu alasannya adalah teknik ini menggunakan struktur rekursif yang memecah tugas menjadi bagian-bagian yang lebih kecil. Di sisi lain, algoritma ini secara hati-hati mengelola ketepatan angka-angka yang terlibat, menemukan keseimbangan antara kecepatan dan hasil yang benar. Pekerjaan baru ini memungkinkan para peneliti untuk mereduksi dasar kisi dengan ribuan dimensi.

Pekerjaan sebelumnya telah mengikuti pendekatan serupa: A kertas 2021 juga menggabungkan rekursi dan manajemen presisi untuk mempercepat kerja kisi-kisi besar, tetapi ini hanya berfungsi untuk jenis kisi-kisi tertentu, dan tidak semua kisi-kisi yang penting dalam kriptografi. Algoritme baru ini berperilaku baik pada rentang yang lebih luas. “Saya sangat senang seseorang melakukannya,” kata Thomas Espitau, seorang peneliti kriptografi di perusahaan PQShield dan penulis versi 2021. Kerja timnya menawarkan “bukti konsep,” katanya; hasil baru menunjukkan bahwa “Anda dapat melakukan pengurangan kisi dengan sangat cepat dengan cara yang baik.”

Teknik baru ini sudah mulai terbukti bermanfaat. Halaman Aurel, seorang ahli matematika di lembaga penelitian nasional Perancis Inria, mengatakan bahwa dia dan timnya telah menerapkan adaptasi algoritma untuk mengerjakan beberapa tugas teori bilangan komputasi.

Algoritme gaya LLL juga dapat berperan dalam penelitian terkait sistem kriptografi berbasis kisi yang dirancang untuk itu tetap aman bahkan di masa depan dengan komputer kuantum yang kuat. Mereka tidak menimbulkan ancaman bagi sistem seperti itu, karena untuk menghapusnya memerlukan penemuan vektor yang lebih pendek daripada yang dapat dicapai oleh algoritma ini. Namun serangan terbaik yang diketahui para peneliti menggunakan algoritma gaya LLL sebagai “blok penyusun dasar,” katanya Wessel van Woerden, seorang kriptografer di Universitas Bordeaux. Dalam eksperimen praktis untuk mempelajari serangan-serangan ini, elemen penyusun tersebut dapat memperlambat segalanya. Dengan menggunakan alat baru ini, para peneliti mungkin dapat memperluas jangkauan eksperimen yang dapat mereka jalankan pada algoritma serangan, sehingga menawarkan gambaran yang lebih jelas tentang bagaimana kinerja mereka.

Quanta sedang melakukan serangkaian survei untuk melayani audiens kami dengan lebih baik. Ambil milik kami survei pembaca ilmu komputer dan anda akan diikut sertakan untuk menang secara gratis Quanta dagangan.