Dua jalan menuju percepatan kuantum
Ketika membahas komputer kuantum, algoritma Shor dan Grover hampir selalu muncul sebagai contoh utama. Keduanya menunjukkan bahwa komputer kuantum dapat menyelesaikan masalah tertentu lebih cepat daripada komputer klasik. Namun, menyebut keduanya sebagai cara untuk membuat semua komputasi menjadi cepat adalah kekeliruan. Shor memanfaatkan struktur matematika dalam suatu masalah, sedangkan Grover mempercepat pencarian ketika struktur yang membantu hampir tidak tersedia.
Perbedaan itu penting, terutama saat membicarakan kriptografi. Shor berkaitan dengan fondasi beberapa sistem kunci publik. Grover berkaitan dengan pencarian menyeluruh, termasuk menebak kunci dalam skenario tertentu. Untuk memahami dampaknya, kita perlu melihat masalah yang masing-masing algoritma selesaikan dan arti sebenarnya dari percepatan yang dijanjikan.
Shor: menemukan pola untuk memfaktorkan bilangan
Algoritma Shor, yang diperkenalkan Peter Shor pada 1994, terkenal karena dapat memfaktorkan bilangan bulat besar dalam waktu polinomial terhadap panjang bilangannya. Jika sebuah bilangan merupakan hasil perkalian dua faktor besar, mencari kedua faktor tersebut sulit bagi metode klasik yang dikenal saat ini. Kesulitan inilah yang membantu menjaga keamanan RSA.
Shor tidak sekadar mencoba kemungkinan faktor satu per satu. Inti pendekatannya adalah mengubah faktorisasi menjadi persoalan mencari periode: kapan suatu perhitungan modular mulai mengulang hasilnya. Komputer kuantum menyiapkan superposisi berbagai kemungkinan, lalu menggunakan rangkaian kuantum, termasuk transformasi Fourier kuantum, untuk menghasilkan informasi tentang periode tersebut. Hasil pengukuran kemudian diolah dan diperiksa dengan perhitungan klasik untuk memperoleh faktor.
Keunggulan Shor bukan berarti algoritma klasik pasti memerlukan waktu eksponensial untuk setiap bilangan. Metode faktorisasi klasik terbaik yang dikenal memiliki kompleksitas subeksponensial, sementara Shor berskala polinomial. Perbedaan itu tetap sangat besar ketika ukuran masalah meningkat.
Dampaknya pada kunci publik
Komputer kuantum yang cukup besar dan andal dapat menggunakan Shor untuk menyerang RSA. Varian algoritma ini juga dapat menyelesaikan masalah logaritma diskret, yang mendasari sejumlah sistem kunci publik, termasuk kriptografi kurva eliptik. Karena itu, ancamannya mencakup pertukaran kunci dan tanda tangan digital yang bergantung pada masalah-masalah tersebut.
Akan tetapi, kemampuan teoritis berbeda dari kemampuan perangkat saat ini. Menyerang sistem nyata membutuhkan qubit yang cukup, koreksi kesalahan, serta operasi yang sangat akurat dalam jumlah besar. Shor menunjukkan risiko jangka panjang yang serius, bukan berarti seluruh komunikasi terenkripsi dapat dibuka dengan komputer kuantum yang tersedia sekarang.
Grover: mencari dengan lebih sedikit percobaan
Algoritma Grover, yang diperkenalkan Lov Grover pada 1996, menangani persoalan berbeda: mencari jawaban dalam kumpulan kemungkinan yang tidak tersusun. Bayangkan ada satu entri yang memenuhi syarat di antara satu juta entri. Pencarian klasik tanpa petunjuk mungkin harus memeriksa ratusan ribu entri sebelum menemukannya. Dalam model ideal, Grover memerlukan sekitar akar kuadrat dari jumlah kemungkinan, yakni kira-kira seribu pemanggilan prosedur pemeriksaan.
Prosedur pemeriksaan itu disebut oracle. Ia menandai jawaban yang benar melalui perubahan fase kuantum. Grover kemudian mengulang langkah penguatan amplitudo sehingga peluang mengukur jawaban yang benar meningkat. Algoritma ini tetap bersifat probabilistik: jumlah pengulangan perlu dipilih dengan tepat, dan hasilnya dapat diverifikasi setelah pengukuran.
Percepatan Grover bersifat kuadratik, bukan polinomial seperti Shor pada masalah faktorisasi. Jika ruang pencarian berisi N kemungkinan, kebutuhan pemeriksaan ideal turun dari sekitar N menjadi sekitar akar N. Itu pencapaian besar, tetapi bukan cara instan untuk menyelesaikan pencarian berukuran berapa pun. Membuat oracle sebagai rangkaian kuantum juga memerlukan sumber daya yang harus dihitung dalam penerapan nyata.
Dampaknya pada kriptografi simetris
Dalam model pencarian kunci ideal, Grover dapat menurunkan jumlah percobaan untuk kunci 128-bit dari sekitar 2 pangkat 128 menjadi sekitar 2 pangkat 64. Kunci 256-bit, dengan asumsi serupa, memerlukan sekitar 2 pangkat 128 percobaan kuantum. Angka-angka ini menggambarkan kompleksitas pencarian, bukan biaya penuh sebuah serangan. Setiap percobaan memerlukan rangkaian kuantum, dan kebutuhan koreksi kesalahan dapat sangat besar.
Karena itu, memperpanjang kunci simetris merupakan salah satu cara menghadapi ancaman Grover. Namun, ketahanan sistem tetap bergantung pada penerapan, pengelolaan kunci, dan jenis serangan yang dihadapi. Grover tidak otomatis membobol setiap enkripsi atau fungsi hash hanya karena keduanya memakai bit.
Perbedaan utama Shor vs Grover
- Jenis masalah: Shor memanfaatkan struktur matematika, terutama pada faktorisasi dan logaritma diskret. Grover mencari jawaban dalam ruang kemungkinan yang pada dasarnya tidak terstruktur.
- Bentuk percepatan: Shor menawarkan algoritma berwaktu polinomial untuk masalah tertentu. Grover mengurangi jumlah pemeriksaan dari sekitar N menjadi akar N dalam model pencarian ideal.
- Implikasi keamanan: Shor mengancam sejumlah skema kunci publik yang banyak digunakan. Grover terutama memengaruhi perkiraan biaya pencarian menyeluruh terhadap kunci simetris.
Apa yang perlu disiapkan?
Pelajaran dari Shor vs Grover bukanlah bahwa semua sistem digital akan runtuh sekaligus. Keduanya menunjukkan bahwa keamanan bergantung pada jenis masalah komputasi yang dipakai. Organisasi dapat mulai mengidentifikasi penggunaan kriptografi kunci publik yang rentan dan merencanakan migrasi ke kriptografi pascakuantum. Untuk sistem simetris, panjang kunci yang memadai tetap menjadi pertimbangan penting.
Shor dan Grover mengubah cara kita menilai batas komputasi, tetapi keduanya tidak menghapus batas itu. Memahami masalah yang dapat mereka percepat, beserta biaya membangun komputer kuantum yang menjalankannya, jauh lebih berguna daripada menganggap komputer kuantum sebagai pemecah semua masalah.
