Trik Kriptografi Membuat Soal Sulit Menjadi Sedikit Lebih Mudah | Majalah Kuanta

Apa cara terbaik untuk memecahkan masalah sulit? Itulah pertanyaan yang mendasari subbidang ilmu komputer yang disebut teori kompleksitas komputasi. Ini pertanyaan yang sulit untuk dijawab, tetapi balikkan saja dan itu menjadi lebih mudah. Pendekatan terburuk hampir selalu berupa trial and error, yang melibatkan memasukkan solusi-solusi yang mungkin hingga berhasil. Namun untuk beberapa permasalahan, nampaknya tidak ada alternatif lain — pendekatan terburuk juga merupakan pendekatan terbaik.

Para peneliti telah lama bertanya-tanya apakah hal tersebut benar-benar terjadi, kata Rahul Ilango, seorang mahasiswa pascasarjana yang mempelajari teori kompleksitas di Massachusetts Institute of Technology. “Anda bisa bertanya, 'Apakah ada soal yang hanya bisa ditebak dan diperiksa secara optimal?'”

Para ahli teori kompleksitas telah mempelajari banyak masalah komputasi, dan bahkan masalah komputasi yang sulit sekalipun sering kali mengakui adanya semacam prosedur, atau algoritme cerdas, yang membuat pencarian solusi menjadi sedikit lebih mudah daripada sekadar coba-coba. Di antara sedikit pengecualian adalah masalah kompresi, yang tujuannya adalah menemukan deskripsi terpendek dari kumpulan data.

Namun November lalu, dua kelompok peneliti secara mandiri ditemukan algoritma lain untuk masalah kompresi - yang sedikit lebih cepat daripada memeriksa semua kemungkinan jawaban. Pendekatan baru ini bekerja dengan mengadaptasi algoritma yang ditemukan oleh kriptografer 25 tahun lalu untuk mengatasi masalah yang berbeda. Hanya ada satu batasan: Anda perlu menyesuaikan algoritme dengan ukuran kumpulan data Anda.

“Itu sungguh hasil yang indah dan penting,” kata Eric Allender, seorang ilmuwan komputer teoretis di Universitas Rutgers.

Mendefinisikan Kekerasan

Hasil baru ini adalah yang terbaru untuk menyelidiki pertanyaan yang pertama kali dipelajari di Uni Soviet, jauh sebelum munculnya teori kompleksitas. “Sebelum saya duduk di bangku sekolah dasar, orang-orang di Rusia sudah merumuskan hal ini,” kata Allender.

Masalah komputasi spesifik yang dipelajari para peneliti Soviet, yang disebut masalah ukuran sirkuit minimum, serupa dengan masalah yang selalu dihadapi oleh para perancang perangkat keras komputer. Jika Anda diberikan spesifikasi lengkap tentang bagaimana seharusnya suatu rangkaian elektronik berperilaku, dapatkah Anda menemukan rangkaian paling sederhana yang dapat melakukan pekerjaan itu? Tidak ada yang tahu bagaimana memecahkan masalah ini tanpa “perebor” – sebuah kata dalam bahasa Rusia yang kira-kira setara dengan “penelusuran menyeluruh.”

Masalah ukuran rangkaian minimum adalah contoh masalah kompresi. Anda dapat mendeskripsikan perilaku rangkaian dengan rangkaian bit yang panjang — 0 dan 1 — lalu bertanya apakah ada cara untuk mereproduksi perilaku yang sama menggunakan bit yang lebih sedikit. Memeriksa semua kemungkinan tata letak sirkuit akan membutuhkan waktu yang bertambah secara eksponensial seiring dengan jumlah bit dalam string.

Pertumbuhan eksponensial semacam ini adalah ciri khas dari masalah komputasi yang sulit. Namun tidak semua masalah sulit sama sulitnya — beberapa memiliki algoritma yang lebih cepat daripada pencarian menyeluruh, meskipun waktu prosesnya masih bertambah secara eksponensial. Dalam istilah modern, pertanyaannya adalah apakah ada algoritma seperti itu untuk masalah kompresi.

Pada tahun 1959, seorang peneliti terkemuka bernama Sergey Yablonsky mengklaim telah membuktikan bahwa pencarian menyeluruh adalah satu-satunya cara untuk memecahkan masalah ukuran sirkuit minimum. Namun pembuktiannya meninggalkan beberapa celah. Beberapa peneliti menyadari adanya kekurangan pada saat itu, namun Yablonsky cukup berpengaruh sehingga membuat sebagian besar peneliti enggan mengerjakan pertanyaan perebor.

Pada dekade-dekade berikutnya, hanya sedikit peneliti yang mempelajari masalah kompresi, dan pertanyaan perebor sebagian besar dikenal sebagai catatan kaki dalam prasejarah teori kompleksitas. Perhatian luas terhadap pertanyaan ini muncul baru-baru ini, setelah para peneliti menemukan hubungan aneh antara masalah kompresi dan dasar-dasar kriptografi.

Lalu Lintas Satu Arah

Kriptografi modern menggunakan masalah komputasi yang sulit untuk menjaga pesan rahasia. Namun kekerasan komputasi hanya berguna jika asimetris — jika sulit untuk menguraikan pesan yang dikodekan tetapi tidak sulit untuk menyandikan pesan pada awalnya.

Dalam setiap skema kriptografi, asal mula asimetri ini adalah objek matematika yang disebut fungsi satu arah, yang mengubah string bit masukan menjadi string keluaran dengan panjang yang sama. Dengan adanya masukan ke fungsi satu arah, maka mudah untuk menghitung keluarannya, namun dengan adanya keluaran maka sulit untuk membalikkan fungsi tersebut — yaitu, merekayasa balik fungsi tersebut dan memulihkan masukannya.

“Kriptografer benar-benar ingin memiliki fungsi satu arah yang dapat dihitung dengan sangat efisien dan sangat sulit untuk dibalik,” kata Allender. Banyak fungsi matematika yang tampaknya memiliki sifat ini, dan kesulitan dalam membalikkan fungsi-fungsi ini berasal dari kesulitan yang tampak dalam memecahkan berbagai masalah komputasi.

Sayangnya, para kriptografer tidak tahu pasti apakah fungsi-fungsi ini benar-benar sulit untuk dibalik — bahkan, ada kemungkinan bahwa fungsi satu arah yang sebenarnya tidak ada. Ketidakpastian ini tetap ada karena para ahli teori kompleksitas memilikinya berjuang selama 50 tahun untuk membuktikan bahwa masalah yang tampaknya sulit sebenarnya sulit. Jika tidak, dan jika para peneliti menemukan algoritma super cepat untuk masalah ini, hal ini akan menjadi bencana bagi kriptografi – seperti tiba-tiba mengarahkan mobil yang melaju ke dua arah di jalan satu arah.

Meskipun pemahaman komprehensif tentang kekerasan komputasi masih sulit dipahami, para kriptografer baru-baru ini membuat kemajuan yang menggembirakan menuju teori terpadu tentang fungsi satu arah. Satu langkah besar diambil pada tahun 2020, ketika kriptografer Universitas Tel Aviv Rafael Lulus dan mahasiswa pascasarjananya Yanyi Liu membuktikan bahwa fungsi satu arah adalah terhubung erat ke masalah kompresi tertentu yang disebut masalah kompleksitas Kolmogorov yang dibatasi waktu.

Jika satu permasalahan tersebut benar-benar sulit dipecahkan untuk sebagian besar masukan, maka hasil Pass dan Liu menghasilkan resep tentang cara membangun fungsi satu arah yang terbukti sulit - fungsi yang dijamin aman bahkan jika permasalahan komputasi lainnya ternyata jauh lebih mudah. dari perkiraan peneliti. Namun jika ada algoritma yang cepat untuk memecahkan masalah kompleksitas Kolmogorov yang terikat waktu, maka kriptografi akan hancur, dan fungsi apa pun dapat dengan mudah dibalik. Fungsi satu arah yang didasarkan pada tingkat kesulitan masalah ini adalah fungsi yang paling aman — fungsi satu arah untuk mengatur semuanya.

Membangun Struktur Data

Penemuan Pass dan Liu adalah bab terbaru dari serangkaian penelitian panjang yang menggunakan teori kompleksitas untuk lebih memahami dasar-dasar kriptografi. Namun hal ini juga menyarankan cara untuk membalikkan hubungan tersebut: Kesetaraan antara masalah kompleksitas Kolmogorov yang terikat waktu dan inversi fungsi menyiratkan bahwa wawasan tentang salah satu masalah dapat mengungkapkan lebih banyak tentang masalah lainnya. Para kriptografer telah mempelajari algoritma inversi fungsi selama beberapa dekade untuk lebih memahami titik lemah metode enkripsi mereka. Para peneliti mulai bertanya-tanya apakah algoritma tersebut dapat membantu menjawab pertanyaan kuno dalam teori kompleksitas.

Seperti banyak masalah komputasi lainnya, inversi fungsi dapat diselesaikan dengan pencarian mendalam. Dengan adanya string keluaran, cukup masukkan setiap masukan yang mungkin ke dalam fungsi hingga Anda menemukan masukan yang menghasilkan jawaban yang benar.

Pada tahun 1980, kriptografer Martin Hellman mulai mempelajari apakah mungkin untuk melakukan hal yang lebih baik – pertanyaan yang sama yang ditanyakan oleh para ahli matematika Soviet tentang masalah kompresi beberapa dekade sebelumnya. orang neraka ditemukan ya, itu mungkin - selama Anda bersedia melakukan upaya ekstra terlebih dahulu, menggunakan objek matematika yang disebut struktur data.

Struktur data pada dasarnya adalah tabel yang menyimpan informasi tentang fungsi yang akan dibalik, dan pembuatannya memerlukan penghitungan keluaran fungsi untuk masukan tertentu yang dipilih secara strategis. Semua perhitungan tersebut “bisa memakan waktu yang sangat lama,” katanya Ryan Williams, seorang ahli teori kompleksitas di MIT. “Tetapi idenya adalah hal ini dilakukan sekali, sekali dan untuk selamanya.” Jika Anda mencoba membalikkan fungsi yang sama dengan banyak keluaran berbeda — misalnya, untuk memecahkan kode banyak pesan berbeda yang dienkripsi dengan cara yang sama — melakukan pekerjaan ini terlebih dahulu mungkin bermanfaat.

Tentu saja, menyimpan informasi tambahan tersebut memerlukan ruang, jadi gunakan strategi ini secara ekstrem, dan Anda bisa mendapatkan program cepat yang tidak dapat ditampung di komputer mana pun. Hellman merancang struktur data cerdas yang memungkinkan algoritmenya membalikkan sebagian besar fungsi sedikit lebih cepat daripada penelusuran menyeluruh tanpa menghabiskan terlalu banyak ruang. Kemudian pada tahun 2000, kriptografer Amos Fiat dan Moni Naor luas Argumen Hellman untuk semua fungsi.

Setelah terobosan Pass dan Liu pada tahun 2020, hasil lama ini tiba-tiba menjadi relevan lagi. Algoritme Fiat-Naor dapat membalikkan fungsi arbitrer lebih cepat daripada pencarian menyeluruh. Bisakah ini juga berfungsi untuk masalah kompresi?

Keluar dari Seragam

Peneliti pertama yang mengajukan pertanyaan ini adalah ahli teori kompleksitas Rahul Santanam dari Universitas Oxford dan mahasiswa pascasarjananya Han Lin Ren. Mereka melakukannya di a kertas 2021 membuktikan bahwa masalah kompresi dan inversi fungsi bahkan lebih saling terkait daripada yang disadari para peneliti.

Pass dan Liu telah membuktikan bahwa jika permasalahan kompleksitas Kolmogorov yang terikat waktu sulit, maka inversi fungsi juga pasti sulit, dan sebaliknya. Namun masalahnya bisa jadi sulit dan masih ada solusi yang lebih baik daripada pencarian menyeluruh. Santhanam dan Ren menunjukkan bahwa ada hubungan erat antara apakah pencarian menyeluruh diperlukan untuk satu masalah dan apakah pencarian menyeluruh diperlukan untuk masalah lainnya.

Hasilnya mempunyai implikasi yang berbeda untuk dua kelas algoritma yang sering dipelajari para peneliti, yang disebut algoritma “seragam” dan “tidak seragam”. Algoritme seragam mengikuti prosedur yang sama untuk setiap masukan — program seragam untuk mengurutkan daftar angka, misalnya, akan bekerja dengan cara yang sama baik ada 20 entri dalam daftar atau 20,000. Algoritme yang tidak seragam malah menggunakan prosedur berbeda untuk input dengan panjang berbeda.

Struktur data yang digunakan oleh algoritma Fiat-Naor selalu disesuaikan dengan fungsi tertentu. Untuk membalikkan fungsi yang mengacak string 10-bit, Anda memerlukan struktur data yang berbeda dari struktur data yang Anda perlukan untuk membalikkan fungsi yang mengacak string 20-bit, meskipun pengacakannya dilakukan dengan cara serupa. Hal ini membuat Fiat-Naor menjadi algoritma yang tidak seragam.

Hasil Santhanam dan Ren menunjukkan bahwa algoritma Fiat-Naor dapat diubah menjadi algoritma untuk memecahkan masalah kompresi. Namun mengadaptasi algoritme dari satu masalah ke masalah lainnya tidaklah mudah, dan mereka tidak melanjutkan pertanyaan tersebut lebih lanjut.

Pass menemukan ide yang sama setahun kemudian, setelah mendengar Fiat memberikan ceramah tentang algoritma klasik di lokakarya yang merayakan kontribusi Naor pada kriptografi. “Ide penggunaan inversi fungsi telah ada di benak saya sejak saat itu,” katanya. Dia kemudian mulai mengerjakan masalah tersebut dengan sungguh-sungguh bersama peneliti Universitas Tel Aviv Noam Mazor.

Sementara itu, Ilango terinspirasi untuk mengatasi masalah tersebut setelah berdiskusi dengan peneliti lain, termasuk Santhanam, dalam kunjungan ke Institut Simons untuk Teori Komputasi di Berkeley, California. “Itu muncul dari salah satu percakapan yang sangat kebetulan di mana Anda hanya membuang-buang waktu,” kata Santhanam. Ilango kemudian bergabung dengan Williams dan Shuichi Hirahara, ahli teori kompleksitas di Institut Informatika Nasional di Tokyo.

Bagian tersulitnya adalah mencari cara untuk menanamkan struktur data di jantung algoritma Fiat-Naor ke dalam algoritma yang tidak seragam untuk memecahkan masalah kompresi. Ada prosedur standar untuk melakukan penyematan semacam itu, tetapi hal itu akan memperlambat algoritme, menghilangkan keunggulannya dibandingkan penelusuran menyeluruh. Kedua tim menemukan cara yang lebih cerdas untuk menggabungkan struktur data Fiat-Naor, dan memperoleh algoritma untuk masalah kompresi yang bekerja pada semua input dan tetap lebih cepat daripada pencarian menyeluruh.

Detail kedua algoritma ini sedikit berbeda. Yang dilakukan oleh Ilango dan rekan penulisnya lebih cepat daripada pencarian menyeluruh bahkan jika Anda membatasi pencarian pada kemungkinan yang paling sederhana, dan ini berlaku untuk semua masalah kompresi - kompleksitas Kolmogorov yang terikat waktu, masalah ukuran sirkuit minimum, dan banyak lainnya. Namun ide intinya sama untuk kedua algoritma. Teknik kriptografi telah membuktikan manfaatnya dalam domain baru ini.

Konvergensi Inversi

Bukti baru untuk algoritma yang tidak seragam menimbulkan pertanyaan alami: Bagaimana dengan algoritma yang seragam? Apakah ada cara untuk menyelesaikan masalah kompresi lebih cepat daripada pencarian menyeluruh dengan menggunakannya?

Rangkaian hasil baru-baru ini menyiratkan bahwa algoritme semacam itu akan setara dengan algoritme seragam untuk membalikkan fungsi arbitrer – sesuatu yang tidak berhasil dicari oleh para kriptografer selama beberapa dekade. Oleh karena itu, banyak peneliti menganggap kemungkinan tersebut tidak mungkin terjadi.

“Saya akan sangat terkejut,” kata Santhanam. “Ini membutuhkan ide yang benar-benar baru.”

Namun Allender mengatakan para peneliti tidak boleh mengabaikan kemungkinan tersebut. “Hipotesis yang baik bagi saya adalah jika ada cara yang tidak seragam dalam melakukan sesuatu, kemungkinan besar ada cara yang seragam,” katanya.

Bagaimanapun, pekerjaan ini telah membuat para ahli teori kompleksitas menjadi tertarik pada pertanyaan-pertanyaan lama dalam kriptografi. Yuval Ishai, seorang kriptografer di Technion di Haifa, Israel, mengatakan itulah yang membuatnya paling menarik.

“Saya sangat senang melihat konvergensi kepentingan antar komunitas yang berbeda,” katanya. “Saya pikir ini bagus untuk sains.”