Lance Fortnow sudah menulis blog tentang kompleksitas komputasi selama lebih dari dua dekade, dan ia bukan tipe yang mudah heboh. Tulisannya soal klaim baru ini ditutup dengan kalimat yang hati-hati: "I have not verified the proof myself, but it is safe to assume now that the exponential-time hypothesis is toast" (Computational Complexity).
Klaim ini datang dari dua lab. OpenAI, perusahaan di balik ChatGPT, mengatakan modelnya telah membantah Exponential Time Hypothesis, yang biasa disingkat ETH. Beberapa jam kemudian Anthropic, pembuat Claude (kedua asisten ini dibandingkan di sini), menerbitkan bantahannya sendiri. Judul-judul berita lalu mengaitkan kabar ini dengan perseteruan di antara matematikawan dan kekhawatiran soal enkripsi global. Kami membaca tulisan resmi kedua lab, komentar para pakar, dan liputan media, dan pendapat kami jelas: hasil ini kemungkinan besar nyata dan penting bagi para teoretikus, tetapi bukan alasan untuk mengubah cara Anda melindungi data. Dua dari tiga isu di judul berita menyangkut perselisihan yang berbeda, dan yang ketiga soal tren.
Apa itu Exponential Time Hypothesis, dalam bahasa sederhana?
Mulailah dari teka-teki bernama 3-SAT. Anda diberi daftar panjang kondisi atas n saklar benar-atau-salah, masing-masing berbentuk "A, atau bukan B, atau C", dan Anda harus menemukan pengaturan saklar yang memenuhi semuanya. Memeriksa satu pengaturan itu cepat. Menemukannya yang sulit, mirip Sudoku: kotak yang sudah terisi mudah diverifikasi, sedangkan kotak kosong tidak.
ETH, yang diajukan pada 1999 oleh Russell Impagliazzo dan Ramamohan Paturi (bersama Francis Zane), menyatakan bahwa setiap algoritma untuk 3-SAT membutuhkan waktu yang tumbuh seperti 2 pangkat c kali n, untuk suatu c tetap yang lebih besar dari nol (Fortnow). Bayangkan gembok kombinasi yang setiap penambahan satu putarannya melipatgandakan pekerjaan dengan faktor tetap, misalnya 1,3. ETH mengatakan faktor itu bisa dikecilkan, tetapi tidak pernah sampai 1.
Bantahan ini mengatakan faktor tersebut memang mengecil mendekati 1 seiring formula membesar. Makalah OpenAI memberikan, menurut Fortnow, waktu eksekusi sekitar 2 pangkat n kali log log n per akar kuadrat log n. Itu masih jauh dari cepat. Pertumbuhannya hanya lebih lambat daripada pengali tetap mana pun. Tulisan Anthropic sendiri menyatakannya terus terang: "The result is purely asymptotic and says nothing about solving formulas in practice" (Anthropic).
Mengapa para teoretikus begitu peduli? ETH telah dipakai di ratusan makalah sebagai pengganti pernyataan "masalah ini tidak bisa diselesaikan jauh lebih cepat" (OpenAI). Jika hipotesis ini salah, argumen-argumen kesulitan tersebut perlu diperiksa ulang, meski Fortnow mencatat bahwa "the fact that ETH and SETH fail doesn't mean their implications are false."
Lebih banyak yang sudah diperiksa dari biasanya, tetapi belum tuntas
Pemeriksaan sejauh ini lebih banyak daripada yang didapat kebanyakan terobosan di minggu pertamanya. OpenAI mengatakan modelnya menemukan sanggahan itu sepuluh hari sebelum pengumuman dan telah diformalkan di Lean, pemeriksa bukti yang hanya menerima langkah yang bisa diverifikasinya (OpenAI). Anthropic mengatakan model Claude internal menemukan versinya, dan file Lean-nya ditulis oleh model AI (Anthropic).
Sejak itu manusia ikut turun tangan. Ryan O'Donnell dari Carnegie Mellon memublikasikan uraian ulang bukti tersebut, dan menurut Fortnow, Shiva Kintali memublikasikan uraian lain, keduanya mengutamakan kesederhanaan ketimbang batas terbaik. Timothy Gowers menyebutnya "Very surprising and consequential that it is false" (Business Insider).
Pihak yang secara resmi ditugaskan memeriksanya adalah Impagliazzo, Paturi, dan Ryan Williams dari MIT. Kepada TechCrunch, Williams mengatakan sebagian bukti itu rutin, tetapi "there are two or three alien-looking parts". Business Insider melaporkan Williams belum mengesahkan hasil ini dan kelompok itu menyatakan keterlibatan mereka bukan berarti dukungan. Satu peringatan lagi dari repositori Anthropic sendiri: Lean memeriksa bukti, tetapi "no machine checks that this file says what the paper says", jadi seseorang harus membaca file pernyataan yang pendek itu. Mereka sengaja membuatnya pendek karena alasan tersebut.
Menurut kami: klaim dari dua lab, bukti yang diperiksa mesin, dan uraian ulang oleh manusia dalam hitungan hari adalah sinyal yang luar biasa kuat. Tetapi ini tetap sebatas klaim sampai kelompok pakar dan jurnal menyatakan sebaliknya.
Apakah perseteruan matematikawan menyangkut hasil ini?
Sebagian besar tidak. "Perselisihan antarmatematikawan" ala BBC adalah soal masalah lain. Beritanya membahas sengketa Navier-Stokes, ketika Tristan Buckmaster dari NYU mempertanyakan apakah draf miliknya, yang tersimpan di alat Codex milik OpenAI, bisa saja ikut memengaruhi pekerjaan OpenAI sendiri. OpenAI menyatakan tidak ada orang di sana yang melihat pekerjaan tim lain itu, dan bahwa prompt-nya "could not have influenced the system in any way".
Judul "scooped" di Scientific American menyangkut Yang-Mills, masalah fisika. Majalah itu menyebut OpenAI tampaknya mendahului Ethan Sussman, yang bekerja bersama Levent Alpöge dari Anthropic, dalam menghasilkan bukti. Alpöge menyampaikan keberatan di X. Semua itu tidak berkaitan dengan apakah algoritma 3-SAT tersebut berfungsi.
Pertikaian soal ETH adalah soal proses. Williams menyebut rilis OpenAI sebelumnya "a DDOS attack on mathematicians" (X), lalu setuju membantu dalam kasus ini. Scientific American menyebut pendekatan OpenAI pada dua dari tiga hasil melanggar pernyataan klarifikasi dari kelompok penasihat pakar AI dan matematika mereka sendiri, dan prompt serta chain-of-thought di baliknya masih dirahasiakan. Untuk ETH, OpenAI memang setuju menerbitkan buktinya dan mendanai sebuah konferensi.
Apakah ini menjebol RSA atau enkripsi di ponsel saya?
Tidak, dan bukan lewat jalur ini. Kami menyatakannya setegas itu karena alasannya spesifik. Pertama, algoritma ini menyelesaikan k-SAT. Fortnow menekankan bahwa algoritma ini "gives nothing new for Subset Sum or Traveling Salesman", karena mengubah masalah-masalah itu menjadi 3-SAT akan menggelembungkan jumlah variabel terlalu besar. Kedua, RSA bertumpu pada sulitnya memecah bilangan raksasa menjadi dua bilangan prima (Financial Times menggambarkan metodenya tanpa menyebut namanya), yang merupakan masalah berbeda dari memenuhi formula logika, dan tak satu pun sumber yang kami baca mengatakan algoritma baru ini menjangkaunya. Ketiga, batasnya bersifat asimtotik: tidak ada yang berubah untuk kunci 2.048-bit pada mesin mana pun yang ada saat ini.
Williams menyampaikan kekhawatiran yang paling jelas kepada kepala sains OpenAI, Dan Roberts. Menurut TechCrunch, ia bertanya apakah ada yang kini tidak aman, dan menyampaikan bahwa, rupanya, OpenAI sudah memeriksa dan "reasonably confident" hasil ini tidak berimplikasi pada pembobolan apa pun. Itu informasi tangan kedua dan belum dipublikasikan, jadi timbanglah dengan semestinya. Williams juga mengatakan bahwa algoritma yang lebih baik bisa berarti sebagian ukuran kunci dianggap sudah jebol.
Ada pertanyaan terbuka yang nyata di baliknya. Williams mengatakan "every computer scientist should probably put a little more weight on the plausibility of P = NP", tetapi John D. Cook menunjukkan bahwa "the status of P = NP is still unknown" (Business Insider). Williams juga tidak menganggap algoritma baru ini yang terbaik. Jika muncul yang lebih tajam, argumennya akan berubah.
Artikel Financial Times membahas tren, bukan bukti ini
Artikel FT membahas kemampuan matematika AI yang kian berkembang dan enkripsi secara umum, dan dalam teks yang bisa kami baca, ETH tidak disebut sama sekali. Narasumbernya berimbang. Matematikawan Australia Geordie Williamson mengatakan kepada audiens Imperial College bahwa AI menyebabkan "a complete kind of restructuring of what difficulty is", dan bahwa kita sebaiknya siap menghadapi kejutan. Daniel Shiu dari University of Manchester menyebut AI yang membobol enkripsi sebagai "significant risk" bagi "more mathematical forms of cryptography", dengan menyebut beberapa algoritma tahan kuantum yang "less mature". FT sendiri menyatakan AI "has yet to break a core cryptography method".
Scott Aaronson menambahkan satu petunjuk yang masih menggantung: kriptografi tampak absen dari daftar 376 makalah OpenAI sebelumnya, dan dalam pembaruan tulisannya ia menulis bahwa sumber-sumbernya mengatakan perusahaan AI mulai menyelidiki apakah model mereka bisa membobol protokol. Ia tidak menyebut nama, dan kami pun tidak bisa.
Menurut kami: kekhawatiran yang masuk akal tertuju pada skema yang lebih baru, bukan yang ada di browser Anda. Standar NIST 2024 mencakup dua skema berbasis lattice dan standar tanda tangan ketiga yang dibangun di atas jenis matematika berbeda, disiapkan sebagai cadangan kalau yang pertama terbukti rentan.
Apa yang sebaiknya dilakukan bisnis kecil
Nyaris tidak ada, dan tidak ada yang mendesak. Pohon keputusan di bawah ini memilah tiga situasi yang menurut kami penting.
Ada satu kebiasaan yang layak dimiliki terlepas dari kabar ini. Regulator Inggris mengatakan kepada FT bahwa "firms shouldn't wait to act" dalam bersiap menghadapi risiko AI dan kuantum terhadap kriptografi, dan BT mengatakan ingin kriptografinya "changed more readily as standards, technologies and threats evolve". Bagi toko kecil, artinya menjaga perangkat lunak tetap diperbarui dan bertanya kepada vendor bagaimana mereka akan mengganti algoritma. Kerangka kerja kami untuk memercayakan data kepada alat AI membahas pertanyaan untuk vendor, dan papan Security & Privacy di ToolRank mendaftar alat per kategori.
Tiga hal yang perlu dipantau sebelum ada yang menyatakan tuntas
Pantau tiga hal. Pertama, tulisan kelompok pakar dari Impagliazzo, Paturi, dan Williams, serta konferensi yang disanggupi OpenAI untuk didanai. Kedua, pembacaan independen atas file pernyataan Lean, karena di sanalah kesalahan halus bisa bersembunyi. Ketiga, tinjauan sejawat jurnal, yang belum kami temukan tanda-tandanya. Sebelum yang pertama muncul, kami akan menyebutnya "sangat mungkin sudah terbantahkan".