Pengantar
Pada tahun 1994, ilmuwan komputer Peter Shoro ditemukan bahwa jika komputer kuantum pernah ditemukan, mereka akan menghancurkan banyak infrastruktur yang digunakan untuk melindungi informasi yang dibagikan secara online. Kemungkinan menakutkan itu telah membuat para peneliti berebut untuk menghasilkan skema enkripsi "pasca-kuantum" baru, untuk menyimpan informasi sebanyak mungkin agar tidak jatuh ke tangan peretas kuantum.
Awal tahun ini, Institut Nasional Standar dan Teknologi mengungkapkan empat finalis dalam pencariannya untuk standar kriptografi pasca-kuantum. Tiga dari mereka menggunakan "kriptografi kisi" — skema yang terinspirasi oleh kisi, pengaturan titik-titik yang teratur di ruang angkasa.
Kriptografi kisi dan kemungkinan pasca-kuantum lainnya berbeda dari standar saat ini dalam cara yang penting. Tapi mereka semua mengandalkan asimetri matematika. Keamanan dari banyak sistem kriptografi saat ini didasarkan pada perkalian dan pemfaktoran: Setiap komputer dapat dengan cepat mengalikan dua angka, tetapi butuh waktu berabad-abad untuk memfaktorkan angka besar secara kriptografis ke dalam konstituen utamanya. Asimetri itu membuat rahasia mudah dikodekan tetapi sulit didekodekan.
Apa yang diungkapkan Shor dalam algoritme 1994-nya adalah bahwa kekhasan pemfaktoran membuatnya rentan terhadap serangan komputer kuantum. “Ini adalah hal yang sangat spesifik dan khusus yang dapat dilakukan oleh komputer kuantum,” kata Katherine Stange, seorang matematikawan di University of Colorado, Boulder. Jadi setelah Shor, kriptografer memiliki pekerjaan baru: Temukan serangkaian operasi matematika baru yang mudah dilakukan tetapi hampir tidak mungkin dibatalkan.
Kriptografi kisi adalah salah satu upaya paling sukses sejauh ini. Awalnya dikembangkan pada 1990-an, itu bergantung pada kesulitan jumlah poin rekayasa balik.
Berikut ini salah satu cara untuk mendeskripsikan kriptografi kisi: Bayangkan teman Anda memiliki kisi, yang hanya berupa sekumpulan titik dalam pola yang berulang dan teratur di seluruh bidang. Teman Anda ingin Anda menyebutkan 10 poin ini. Tapi dia sulit, dan dia tidak akan menggambar seluruh kisi. Sebaliknya, dia hanya mencantumkan dua poin — yang pertama dengan x-nilai 101 dan y-nilai 19, yang lain dengan koordinat [235, 44].
Untungnya, mudah untuk menemukan titik baru pada kisi, karena saat Anda menambah dan mengurangi dua titik pada kisi, Anda mendapatkan titik ketiga dalam kisi yang sama. Jadi yang harus Anda lakukan adalah menjumlahkan poin yang diberikan teman Anda, atau mengalikannya dengan bilangan bulat lalu menjumlahkannya, atau kombinasi keduanya. Lakukan delapan cara berbeda ini, dan Anda akan dapat menjawab pertanyaan teman Anda.
Tapi temanmu masih belum puas. Dia memberi Anda dua titik awal yang sama, dan kemudian menanyakan apakah titik [2, 1] berada pada kisi yang sama. Untuk menjawab pertanyaan ini dengan benar, Anda harus mencari kombinasi [101, 19] dan [235, 44] yang menghasilkan [2, 1]. Soal ini jauh lebih sulit daripada soal pertama, dan Anda mungkin hanya akan menebak-nebak dan mengecek untuk mendapatkan jawabannya.* Asimetri itulah yang mendasari kriptografi kisi.
Jika Anda benar-benar ingin menggunakan kriptografi kisi untuk berbagi informasi, Anda harus melakukan hal berikut. Bayangkan seorang teman (yang lebih baik!) ingin mengirimi Anda pesan yang aman. Anda mulai dengan kotak angka persegi. Katakanlah ia memiliki dua baris dan dua kolom, dan terlihat seperti ini:
Sekarang Anda menemukan "kunci" pribadi yang hanya Anda yang tahu. Dalam contoh ini, katakanlah kunci pribadi Anda hanya terdiri dari dua angka rahasia: 3 dan 2. Anda mengalikan angka di kolom pertama dengan 3, dan angka di kolom kedua dengan 2. Jumlahkan hasil di setiap baris untuk mendapatkan kolom ketiga dengan dua entri.
Tempelkan kolom baru ke ujung kisi Anda. Kisi tiga kolom baru ini adalah kunci publik Anda. Bagikan dengan bebas!
(Skenario dunia nyata akan sedikit lebih rumit. Untuk mencegah peretas mendekode kunci pribadi Anda, Anda harus menambahkan sedikit noise acak ke kolom terakhir Anda. Tapi di sini kita akan mengabaikan langkah itu demi kesederhanaan. )
Sekarang teman Anda akan menggunakan kunci publik untuk mengirimi Anda pesan. Dia memikirkan dua angka rahasianya sendiri: 2 dan 0. Dia mengalikan angka di baris pertama dengan 2, dan angka di baris kedua dengan 0. Dia kemudian menjumlahkan hasilnya di setiap kolom untuk mendapatkan baris ketiga.
Dia sekarang menempelkan baris baru ke bagian bawah kisi dan mengirimkannya kembali kepada Anda. (Sekali lagi, dalam sistem nyata, dia perlu menambahkan beberapa suara ke barisnya.)
Sekarang Anda akan membaca pesannya. Untuk melakukan ini, periksa untuk melihat apakah baris terakhir teman Anda benar. Terapkan kunci pribadi Anda sendiri ke dua entri pertama dari barisnya. Hasilnya harus sesuai dengan entri terakhir.
Teman Anda juga dapat memilih untuk mengirimi Anda baris dengan nomor yang salah di kolom terakhir. Dia tahu bahwa angka ini tidak akan cocok dengan perhitungan Anda.
Jika teman Anda mengirimkan baris dengan nomor terakhir yang benar, Anda akan menafsirkannya sebagai 0. Jika dia mengirim baris dengan nomor yang salah, Anda akan menafsirkannya sebagai 1. Oleh karena itu, baris tersebut mengkodekan satu bit: 0 atau 1.
Perhatikan bahwa penyerang luar tidak akan memiliki akses ke kunci pribadi Anda atau kunci teman Anda. Tanpa itu, penyerang tidak akan tahu apakah angka terakhir benar atau tidak.
Dalam praktiknya, Anda ingin mengirim pesan yang lebih panjang dari satu bit. Jadi orang yang ingin menerima, katakanlah, pesan 100-bit akan menghasilkan 100 kolom baru, bukan hanya satu. Kemudian pengirim pesan akan membuat satu baris baru, memodifikasi 100 entri terakhir untuk mengkodekan 0 atau 1 untuk setiap entri.
Jika kriptografi kisi benar-benar diterapkan, itu akan memiliki banyak nuansa yang tidak tercakup dalam skenario ini. Misalnya, jika Anda ingin pesan benar-benar aman dari mata-mata, matriks harus memiliki jumlah entri yang tidak terpikirkan, membuat semuanya begitu berat sehingga tidak layak digunakan. Untuk menyiasatinya, peneliti menggunakan matriks dengan simetri yang berguna yang dapat mengurangi jumlah parameter. Di luar itu, ada seluruh rangkaian tweak yang dapat diterapkan pada masalah itu sendiri, dengan cara memasukkan kesalahan, dan banyak lagi.
Tentu saja, selalu ada kemungkinan bahwa seseorang akan menemukan kesalahan fatal dalam kriptografi kisi, seperti yang dilakukan Shor untuk pemfaktoran. Tidak ada jaminan bahwa skema kriptografi tertentu akan bekerja dalam menghadapi kemungkinan serangan. Kriptografi bekerja sampai retak. Memang, awal musim panas ini satu skema kriptografi pasca-kuantum yang menjanjikan telah dipecahkan menggunakan bukan komputer kuantum, melainkan laptop biasa. Bagi Stange, seluruh proyek menciptakan paradoks yang tidak menyenangkan: “Apa yang menurut saya sangat menakjubkan tentang kriptografi adalah bahwa kami telah membangun infrastruktur ini untuk umat manusia dengan keyakinan kuat bahwa kemampuan kita sebagai manusia terbatas,” katanya. "Ini sangat terbelakang."
*: Jawabannya kalau penasaran adalah 7 × [101, 19] – 3 × [235, 44] = [2, 1]. [kembali ke artikel]
