Komputer Quantum: Akhir Kriptografi?

Iklan

Komputasi kuantum adalah salah satu teknologi yang begitu misterius sehingga nama karakter TV menjatuhkannya ketika mereka ingin terdengar pintar.

Komputasi kuantum sebagai sebuah ide telah ada untuk sementara waktu - kemungkinan teoretis pada awalnya diperkenalkan oleh Yuri Manin dan Richard Feynman pada tahun 1982. Namun, selama beberapa tahun terakhir, bidang ini semakin mendekati kepraktisan.

Perusahaan seperti Google dan Microsoft, serta lembaga pemerintah seperti NSA semuanya telah giat mengejar komputer kuantum selama bertahun-tahun sekarang. Sebuah perusahaan bernama D-Wave telah memproduksi dan menjual perangkat yang (sementara mereka tidak layak komputer, dan bisa hanya melakukan beberapa algoritma) mengeksploitasi properti kuantum, dan merupakan langkah tambahan lainnya di jalan menuju a sepenuhnya Turing-lengkap Apa Tes Turing Dan Akankah Itu Pernah Dipukul?Tes Turing dimaksudkan untuk menentukan apakah mesin berpikir. Apakah program Eugene Goostman benar-benar lulus tes Turing, atau apakah pencipta hanya menipu? Baca lebih banyak mesin kuantum.

Tampaknya tidak masuk akal untuk mengatakan bahwa terobosan mungkin terjadi yang akan memungkinkan komputer kuantum skala besar pertama dibangun dalam satu dekade.

Lantas mengapa semua bunganya? Kenapa kamu harus peduli? Komputer menjadi lebih cepat setiap saat Apa Hukum Moore, Dan Apa Hubungannya Dengan Anda? [MakeUseOf Menjelaskan]Nasib buruk tidak ada hubungannya dengan Hukum Moore. Jika itu adalah asosiasi yang Anda miliki, Anda bingung dengan Hukum Murphy. Namun, Anda tidak jauh karena Hukum Moore dan Hukum Murphy ... Baca lebih banyak - apa yang spesial dari komputer kuantum?

Untuk menjelaskan mengapa mesin ini sangat penting, kami harus mengambil langkah mundur dan menjelajahi apa itu komputer kuantum, dan mengapa mereka bekerja. Untuk memulai, mari kita bicara tentang konsep yang disebut "kompleksitas runtime."

Apa itu Runtime Complexity?

Salah satu kejutan besar di awal-awal ilmu komputer adalah penemuan itu, jika Anda memiliki komputer yang memecahkan masalah ukuran tertentu dalam jumlah waktu tertentu, menggandakan kecepatan komputer tidak serta merta membuat masalah dua kali lipat besar.

Beberapa algoritma meningkatkan waktu eksekusi total dengan sangat, sangat cepat seiring dengan meningkatnya ukuran masalah - beberapa algoritma dapat diselesaikan dengan cepat diberikan 100 titik data, tetapi menyelesaikan algoritme yang diberikan 1000 titik data akan membutuhkan komputer seukuran Bumi yang berjalan selama satu miliar tahun. Kompleksitas runtime adalah formalisasi dari ide ini: ia melihat pada kurva seberapa cepat kompleksitas suatu masalah tumbuh, dan menggunakan bentuk kurva itu untuk mengklasifikasikan algoritma.

Secara umum, kelas-kelas kesulitan ini dinyatakan sebagai fungsi. Algoritma yang menjadi lebih sulit secara proporsional ketika data mengatur kerjanya meningkat (seperti fungsi penghitungan sederhana) dikatakan sebagai fungsi dengan kompleksitas runtime "n ” (seperti dalam, dibutuhkan n unit waktu untuk diproses n titik data).

Bergantian, itu mungkin disebut "linear", karena ketika Anda membuat grafik, Anda mendapatkan garis lurus. Fungsi lain mungkin n ^ 2 atau 2 ^ n atau n! (n faktorial). Ini polinomial dan eksponensial. Dalam dua kasus terakhir, yang eksponensial tumbuh begitu cepat sehingga dalam hampir semua kasus mereka tidak dapat diselesaikan untuk apa pun kecuali contoh yang sangat sepele.

Kompleksitas Runtime dan Kriptografi

Jika Anda mendengar hal ini untuk pertama kalinya dan kedengarannya tidak berarti dan misterius, mari kita coba untuk memulai diskusi ini. Kompleksitas runtime sangat penting untuk kriptografi, yang bergantung pada membuat dekripsi jauh lebih mudah bagi orang yang tahu kunci rahasia daripada bagi mereka yang tidak. Dalam skema kriptografi yang ideal, dekripsi harus linier jika Anda memiliki kunci, dan 2 ^ k (di mana k adalah jumlah bit dalam kunci) jika Anda tidak.

Dengan kata lain, algoritma terbaik untuk mendekripsi pesan tanpa kunci seharusnya hanya menebak kunci yang mungkin, yang tidak dapat diterapkan untuk kunci yang hanya beberapa ratus bit panjangnya.

Untuk kriptografi kunci simetris (di mana kedua pihak memiliki kesempatan untuk bertukar rahasia dengan aman sebelum mereka memulai komunikasi) ini cukup mudah. Untuk kriptografi asimetris, lebih sulit.

Kriptografi asimetris, di mana kunci enkripsi dan dekripsi berbeda dan tidak dapat dengan mudah dihitung satu sama lain, adalah matematika yang jauh lebih sulit struktur untuk diterapkan daripada kriptografi simetris, tetapi juga jauh lebih kuat: kripto asimetris memungkinkan Anda melakukan percakapan pribadi, bahkan lebih dari mengetuk garis! Ini juga memungkinkan Anda untuk membuat "tanda tangan digital" untuk memungkinkan Anda memverifikasi dari siapa pesan berasal, dan bahwa pesan itu belum dirusak.

Ini adalah alat yang kuat, dan membentuk dasar dari privasi modern: tanpa kriptografi asimetris, pengguna perangkat elektronik tidak akan memiliki perlindungan yang dapat diandalkan terhadap mata yang mengintip.

Karena kriptografi asimetris lebih sulit dibangun daripada simetris, skema enkripsi standar yang digunakan saat ini tidak sekuat karena mereka dapat: standar enkripsi yang paling umum, RSA, dapat dipecahkan jika Anda dapat secara efisien menemukan faktor-faktor utama yang sangat besar. jumlah. Berita baiknya adalah itu adalah masalah yang sangat sulit.

Algoritma yang paling dikenal untuk memfaktorkan bilangan besar ke dalam bilangan prima komponen mereka disebut saringan bidang bilangan umum, dan memiliki kompleksitas runtime yang tumbuh sedikit lebih lambat daripada 2 ^ n. Sebagai konsekuensinya, kunci harus sekitar sepuluh kali lebih lama untuk memberikan keamanan yang serupa, yang merupakan sesuatu yang biasanya ditoleransi orang sebagai biaya berbisnis. Berita buruknya adalah bahwa seluruh bidang permainan berubah ketika komputer kuantum dilemparkan ke dalam campuran.

Komputer Quantum: Mengubah Game Crypto

Komputer Quantum bekerja karena mereka dapat memiliki beberapa kondisi internal pada saat yang sama, melalui fenomena kuantum yang disebut "superposisi". Itu berarti bahwa mereka dapat menyerang bagian-bagian berbeda dari suatu masalah secara bersamaan, terbagi menjadi beberapa versi alam semesta. Mereka juga dapat dikonfigurasi sehingga cabang-cabang yang menyelesaikan masalah berakhir dengan amplitudo terbanyak, sehingga saat Anda membuka kotak pada Kucing Schrodinger, versi kondisi internal yang kemungkinan besar akan Anda suguhkan adalah kucing yang tampak sombong yang memegangi dekripsi. pesan.

Untuk informasi lebih lanjut tentang komputer kuantum, periksa artikel terbaru kami tentang masalah ini Bagaimana cara kerja Komputer Optik dan Kuantum?Zaman Exascale akan datang. Apakah Anda tahu cara kerja komputer optik dan kuantum, dan apakah teknologi baru ini akan menjadi masa depan kita? Baca lebih banyak !

Hasilnya adalah bahwa komputer kuantum tidak hanya lebih cepat secara linear, seperti komputer normal: mendapatkan dua atau sepuluh atau seratus kali lebih cepat tidak banyak membantu dalam kriptografi konvensional yang Anda proses ratusan miliar kali terlalu lambat untuk diproses. Komputer Quantum mendukung algoritma yang memiliki kompleksitas run time yang lebih kecil daripada yang mungkin terjadi. Inilah yang membuat komputer kuantum secara fundamental berbeda dari teknologi komputasi masa depan lainnya, seperti perhitungan graphene dan memrister Teknologi Komputer Terbaru yang Harus Anda Lihat untuk PercayaLihatlah beberapa teknologi komputer terbaru yang siap mengubah dunia elektronik dan PC selama beberapa tahun ke depan. Baca lebih banyak .

Sebagai contoh konkret, Algoritma Shor, yang hanya dapat dieksekusi pada komputer kuantum, dapat memasukkan faktor dalam jumlah besar ke dalam log (n) ^ 3 waktu, yang secara drastis lebih baik daripada serangan klasik terbaik. Menggunakan saringan bilangan umum untuk memfaktorkan bilangan dengan 2048 bit membutuhkan waktu 10 ^ 41 unit waktu, yang menghasilkan lebih dari satu triliun triliun triliun. Menggunakan algoritma Shor, masalah yang sama hanya membutuhkan sekitar 1000 unit waktu.

Efeknya menjadi lebih jelas semakin lama tombolnya. Itulah kekuatan komputer kuantum.

Jangan salah paham - komputer kuantum memiliki banyak potensi penggunaan non-jahat. Komputer Quantum dapat secara efisien menyelesaikan masalah salesman keliling, memungkinkan para peneliti untuk membangun jaringan pengiriman yang lebih efisien dan merancang sirkuit yang lebih baik. Komputer kuantum sudah memiliki kegunaan yang kuat dalam kecerdasan buatan.

Yang mengatakan, peran mereka dalam kriptografi akan menjadi bencana besar. Teknologi enkripsi yang memungkinkan dunia kita untuk tetap berfungsi bergantung pada masalah faktorisasi bilangan bulat yang sulit dipecahkan. RSA dan skema enkripsi terkait adalah apa yang membuat Anda memercayai Anda di situs web yang benar, yang menjadi file Anda unduh tidak diliputi malware, dan orang-orang tidak memata-matai penjelajahan internet Anda (jika Anda menggunakan Tor).

Kriptografi menjaga rekening bank Anda aman dan mengamankan infrastruktur nuklir dunia. Ketika komputer kuantum menjadi praktis, semua teknologi itu berhenti berfungsi. Organisasi pertama yang mengembangkan komputer kuantum, jika dunia masih bekerja pada teknologi yang kita gunakan saat ini, akan berada dalam posisi yang sangat kuat.

Jadi, apakah kiamat kuantum tidak terhindarkan? Adakah yang bisa kita lakukan? Ternyata... ya.

Kriptografi Pasca-Kuantum

Ada beberapa kelas algoritma enkripsi yang, sejauh yang kami tahu, tidak secara signifikan lebih cepat untuk diselesaikan pada komputer kuantum. Ini dikenal secara kolektif sebagai kriptografi post-quantum, dan memberikan beberapa harapan bahwa dunia dapat beralih ke cryptosystems yang akan tetap aman di dunia enkripsi kuantum.

Calon yang menjanjikan termasuk enkripsi berbasis kisi, seperti Ring-Learning With Error, yang mendapatkan keamanannya dari kompleks yang terbukti masalah pembelajaran mesin, dan kriptografi multivarian, yang memperoleh keamanannya dari kesulitan memecahkan sistem sederhana yang sangat besar persamaan. Anda dapat membaca lebih lanjut tentang topik ini di Artikel Wikipedia. Hati-hati: banyak dari hal-hal ini kompleks, dan Anda mungkin menemukan bahwa latar belakang matematika Anda perlu ditingkatkan sebelum Anda benar-benar dapat menggali rinciannya.

Hal yang dapat diambil dari banyak hal ini adalah bahwa cryptoschema pasca-kuantum sangat keren, tetapi juga sangat muda. Mereka membutuhkan lebih banyak pekerjaan agar efisien dan praktis, dan juga untuk menunjukkan bahwa mereka aman. Alasan mengapa kami dapat mempercayai cryptosystems adalah karena kami telah cukup banyak melempar kejeniusan paranoid secara klinis pada mereka untuk waktu yang cukup lama. bahwa setiap kekurangan yang jelas akan ditemukan sekarang, dan para peneliti telah membuktikan berbagai karakteristik yang membuatnya kuat.

Kriptografi modern bergantung pada cahaya sebagai disinfektan, dan sebagian besar skema kriptografi pasca-kuantum terlalu baru untuk mempercayai keamanan dunia. Mereka sampai di sana, dan, dengan sedikit keberuntungan dan sedikit persiapan, pakar keamanan dapat menyelesaikan peralihan sebelum komputer kuantum pertama muncul.

Namun jika mereka gagal, konsekuensinya mungkin mengerikan. Pikiran siapa pun yang memiliki kekuatan semacam itu meresahkan, bahkan jika Anda optimis dengan niat mereka. Pertanyaan tentang siapa yang pertama kali mengembangkan komputer kuantum yang berfungsi adalah pertanyaan yang harus diperhatikan setiap orang saat kita memasuki dekade berikutnya.

Apakah Anda khawatir tentang ketidakamanan kriptografi pada komputer kuantum? Apa yang Anda ambil? Bagikan pemikiran Anda dalam komentar di bawah!

Kredit Gambar: Orb biner Melalui Shutterstock