Matematika baru kriptografi kuantum

Versi aslinya dari cerita ini muncul di Berapa banyak majalah.

Masalah sulit biasanya bukan pemandangan yang disambut baik. Tapi cryptographers mencintai mereka. Itu karena masalah matematika keras tertentu mendukung keamanan enkripsi modern. Trik pintar apa pun untuk menyelesaikannya akan menghancurkan sebagian besar bentuk kriptografi.

Beberapa tahun yang lalu, para peneliti menemukan pendekatan enkripsi baru yang radikal Itu tidak memiliki potensi titik lemah ini. Pendekatan ini mengeksploitasi fitur aneh dari fisika kuantum. Tetapi tidak seperti skema enkripsi kuantum sebelumnya, yang hanya berfungsi untuk beberapa tugas khusus, pendekatan baru ini dapat menyelesaikan berbagai tugas yang jauh lebih luas. Dan itu bisa berhasil bahkan jika semua masalah di jantung kriptografi “klasik” biasa ternyata mudah dipecahkan.

Tetapi penemuan yang mencolok ini mengandalkan asumsi yang tidak realistis. Hasilnya adalah “lebih merupakan bukti konsep,” kata Tegas tapiseorang peneliti kriptografi di Simons Institute for Theory of Computing di Berkeley, California. “Ini bukan pernyataan tentang dunia nyata.”

Sekarang, a kertas baru oleh dua cryptographers telah meletakkan jalan menuju kriptografi kuantum tanpa asumsi aneh itu. “Makalah ini mengatakan bahwa jika dugaan tertentu benar, maka kriptografi kuantum harus ada,” kata Ma.

Kastil di langit

Anda dapat menganggap kriptografi modern sebagai menara dengan tiga bagian penting. Bagian pertama adalah landasan di bawah menara, yang terbuat dari masalah matematika yang keras. Menara itu sendiri adalah bagian kedua – di sana Anda dapat menemukan protokol kriptografi spesifik yang memungkinkan Anda mengirim pesan pribadi, menandatangani dokumen digital, memberikan suara rahasia, dan banyak lagi.

Di antaranya, mengamankan aplikasi sehari-hari untuk landasan matematika, adalah fondasi yang terbuat dari blok bangunan yang disebut fungsi satu arah. Mereka bertanggung jawab atas asimetri yang melekat dalam skema enkripsi apa pun. “Ini satu arah karena Anda dapat mengenkripsi pesan, tetapi Anda tidak dapat mendekripsi,” kata Mark Zhandryseorang kriptografer di NTT Research.

Pada 1980-an, para peneliti membuktikan bahwa kriptografi yang dibangun di atas fungsi satu arah akan memastikan keamanan untuk berbagai tugas. Tetapi beberapa dekade kemudian, mereka masih tidak yakin bahwa batuan dasar itu cukup kuat untuk mendukungnya. Masalahnya adalah bahwa landasan terbuat dari masalah keras khusus – secara teknis dikenal sebagai masalah NP – yang fitur yang menentukan adalah mudah untuk memeriksa apakah ada solusi kandidat yang benar. (Misalnya, memecah angka menjadi faktor utamanya adalah masalah NP: sulit dilakukan untuk jumlah besar, tetapi mudah diperiksa.)

Banyak dari masalah ini tampaknya sulit secara intrinsik, tetapi para ilmuwan komputer belum bisa membuktikannya. Jika seseorang menemukan algoritma yang cerdik untuk menyelesaikan masalah NP yang paling sulit, batuan dasar akan hancur, dan seluruh menara akan runtuh.

Sayangnya, Anda tidak bisa begitu saja memindahkan menara Anda ke tempat lain. Yayasan menara-fungsi satu arah-hanya dapat duduk di atas landasan masalah NP.

Untuk membangun menara pada masalah yang lebih sulit, cryptographers akan membutuhkan fondasi baru yang tidak terbuat dari fungsi satu arah. Itu tampaknya mustahil sampai beberapa tahun yang lalu, ketika para peneliti menyadari bahwa fisika kuantum dapat membantu.

Itu dimulai dengan a Kertas 2021 oleh seorang mahasiswa pascasarjana bernama William Kretschmer Itu menarik perhatian pada masalah aneh tentang sifat -sifat sistem kuantum. Para peneliti segera menunjukkan bahwa masalah Kretschmer dapat menggantikan fungsi satu arah sebagai dasar untuk menara baru kriptografi protokol. Tahun berikutnya, Kretschmer dan lainnya terbukti Bahwa pendekatan alternatif ini dapat bekerja bahkan tanpa masalah NP yang sulit. Tiba -tiba, sepertinya mungkin untuk membangun benteng kriptografi yang akan jauh lebih kuat.

Tapi di mana membangunnya? Masalah kuantum yang digunakan Kretschmer sebagai fondasinya perangkat komputasi hipotetis yang disebut Oracles Itu dapat secara instan menjawab pertanyaan spesifik. Oracles bisa menjadi alat teoretis yang berguna, tetapi sebenarnya tidak ada. Bukti Kretschmer seperti cetak biru untuk membangun kastil di langit. Apakah ada cara untuk membawanya ke bumi?

Yayasan Kedua

Pada musim gugur 2022, pertanyaan itu menarik perhatian Dakshita Khuranaseorang kriptografer di University of Illinois di Urbana-Champaign dan NTT Research. Khurana dan mahasiswa pascasarjana Kabir Tomer Berangkat untuk membangun menara kriptografi baru. Langkah pertamanya adalah membangun fondasi baru menggunakan blok bangunan kuantum alih-alih fungsi satu arah klasik. Dia kemudian perlu membuktikan bahwa yayasan baru ini dapat mendukung menara protokol kriptografi lainnya. Begitu dia membuktikan bahwa yayasan dapat mendukung menara itu, dia harus menemukan tempat yang solid agar semuanya duduk-landasan masalah dunia nyata yang tampaknya lebih sulit daripada masalah NP yang digunakan dalam kriptografi klasik.

Untuk langkah pertama, Khurana dan Tomer fokus pada versi kuantum dari fungsi satu arah, yang disebut a generator negara satu arahyang memenuhi tiga properti yang membuat fungsi satu arah bermanfaat. Pertama, fungsi harus berjalan dengan cepat sehingga Anda dapat dengan mudah menghasilkan kunci kriptografi dan kunci yang sesuai untuk membukanya untuk setiap pesan yang ingin Anda kirim. Kedua, setiap kunci harus aman, membutuhkan upaya besar untuk membuka tanpa kunci yang tepat. Akhirnya, setiap kunci harus mudah dibuka dengan kunci yang tepat.

Perbedaan penting terletak pada sifat kunci. Fungsi satu arah klasik menghasilkan kunci matematika yang terbuat dari bit-0s dan 1 yang menyimpan informasi di komputer klasik. Generator negara satu arah kuantum sebaliknya akan menghasilkan kunci yang terbuat dari unit informasi kuantum yang disebut qubit. Kunci kuantum ini berpotensi tetap aman bahkan jika semua kunci klasik mudah pecah. Khurana dan Tomer berharap untuk memulai dengan fondasi kuantum baru ini dan membangun menara protokol kriptografi di atasnya. “Ini ternyata sangat sulit,” kata Khurana. “Kami terjebak selama berbulan -bulan.”

Pada Juli 2023, Khurana hampir sembilan bulan hamil dan merencanakan cuti orang tua. Tomer kehabisan ide. “Saya jauh lebih pesimis daripada Dakshita,” katanya. “Dia selalu orang yang percaya bahwa segalanya akan berhasil.”

Kemudian mereka membuat terobosan. Langkah penting adalah mendefinisikan blok bangunan matematika lain yang berfungsi sebagai sesuatu seperti lantai ruang bawah tanah: struktur yang akan menghubungkan fondasi generator negara satu arah dengan menara protokol kriptografi. Ketika Khurana dan Tomer mengerjakan properti apa yang perlu dimiliki blok bangunan, mereka menemukan bahwa itu menyerupai fungsi satu arah dengan campuran kuantum dan karakteristik klasik yang membingungkan. Seperti dalam fungsi satu arah biasa, baik kunci dan kunci terbuat dari bit klasik, tetapi prosedur untuk menghasilkan kunci dan kunci ini hanya akan berjalan pada komputer kuantum. Stranger Still Still, blok bangunan baru memenuhi dua properti pertama yang menentukan dari fungsi satu arah, tetapi bukan yang ketiga: mudah untuk menghasilkan kunci dan kunci, dan setiap kunci sulit untuk dipatahkan. Tapi kunci tidak akan dengan mudah membuka kuncinya.

Khurana dan Tomer menjuluki blok bangunan baru yang membingungkan ini. Secara intuitif, sulit membayangkan bagaimana mereka bisa berguna: apa gunanya kunci yang tidak pernah Anda gunakan? Tetapi dua cryptographers menunjukkan bahwa teka-teki satu arah yang dikombinasikan dengan tipuan kuantum lainnya sebenarnya Aktifkan banyak protokol kriptografi. Jika Anda dapat menghasilkan kunci dan kunci yang cocok bersama pada prinsipnya, tidak masalah apakah prosedur membuka kunci sangat tidak efisien.

“Hanya mengetahui bahwa ada beberapa algoritma yang bisa lambat secara sewenang -wenang sudah cukup,” kata Kretschmer, yang sekarang menjadi peneliti di Simons Institute. “Itu sangat mengejutkan.”

Dengan bagian yang hilang di tempat, mereka dengan cepat menyelesaikan bukti pada 4 Agustus. Putri Khurana lahir hanya beberapa hari kemudian.

Catatan permanen

Pada bulan November, Khurana kembali bekerja dan siap untuk mencoba fase kedua rencananya. Dia dan Tomer telah menunjukkan bahwa banyak jenis kriptografi dapat dibangun di atas teka-teki satu arah, dan bahwa teka-teki satu arah pada gilirannya dapat dibangun di atas fondasi kuantum baru yang terbuat dari generator negara satu arah. Langkah selanjutnya dalam rencana awal mereka adalah untuk menghubungkan fondasi kuantum itu ke batuan dasar baru – beberapa serangkaian masalah matematika yang relatif tidak dapat disangkal yang bahkan lebih sulit dibandingkan dengan yang ada di NP.

Tetapi ketika Khurana dan Tomer bergulat dengan tugas itu, mereka memutuskan untuk mengambil pendekatan yang lebih langsung: lupakan generator negara satu arah, dan sebaliknya jangkar teka-teki satu arah langsung ke batuan dasar matematika.

Dari satu perspektif, itu sepertinya pilihan yang aneh. Teka-teki satu arah adalah keanehan matematika yang digunakan Khurana dan Tomer dalam langkah perantara dari bukti mereka.

Namun teka-teki satu arah memiliki beberapa keuntungan. Untuk satu hal, sementara mereka kuantum, kunci dan kunci yang mereka hasilkan klasik. Khurana berpikir itu mungkin membuatnya lebih mudah untuk menghubungkan mereka ke landasan matematika klasik. Selain itu, teka-teki satu arah menghasilkan kunci yang terlalu sulit untuk benar-benar membuka kunci. Itu bisa membuatnya lebih mudah untuk menghubungkan mereka dengan masalah yang begitu rumit sehingga bahkan memeriksa solusi tampaknya sangat sulit.

Tapi masalah spesifik apa yang akan berhasil? Khurana memiliki kandidat dalam pikiran: menghitung kombinasi spesifik dari entri dalam tabel angka yang disebut matriks. Masalah ini, yang dikenal sebagai masalah permanen matriks, sangat sulit dipecahkan untuk matriks besar, dan tidak ada cara sederhana untuk memeriksa apakah suatu perhitungan benar. Masalah permanen matriks juga memiliki sifat matematika khusus lainnya yang menurut cryptographers menarik.

“Ini akan menjadi masalah yang indah untuk didasarkan pada kriptografi,” kata Khurana.

Masalah permanen matriks juga terhubung ke masalah yang berbeda itu Komputer kuantum dapat dengan mudah dipecahkan tetapi komputer klasik tampaknya tidak bisa. Para peneliti sedang berupaya membuktikan keunggulan komputasi kuantum ini dalam arti teoretis yang tepat. Khurana dan Tomer menunjukkan bahwa bukti seperti itu juga akan membiarkan mereka membangun teka-teki satu arah yang aman-dan dengan demikian seluruh menara kriptografi kuantum-di atas masalah permanen.

“Mereka dapat melakukan ini dari asumsi yang dipelajari dengan baik ini,” kata Kretschmer. “Aku sangat senang melihatnya.”

Dengan hasil baru mereka, Khurana dan Tomer telah secara efektif mengurangi dua masalah terbuka menjadi satu. Jika para peneliti melengkapi bukti bahwa komputer kuantum benar -benar melampaui yang klasik pada tugas tertentu, itu akan secara otomatis menempatkan kriptografi kuantum pada pijakan teoretis yang jauh lebih kuat daripada hampir semua jenis kriptografi klasik.

Sayangnya, Anda tidak akan dapat menggunakan pendekatan baru Khurana dan Tomer untuk mengirim pesan rahasia dalam waktu dekat. Meskipun Kemajuan TerbaruTeknologi komputasi kuantum belum cukup matang untuk mempraktikkan ide -ide mereka. Sementara itu, peneliti lain telah merancang metode kriptografi kuantum itu bisa digunakan lebih cepatmeskipun lebih banyak pekerjaan akan dibutuhkan untuk menetapkan bahwa mereka benar -benar aman.

Kriptografi kuantum telah terbukti penuh dengan kejutan, dan para peneliti baru saja mulai mengeksplorasi kemungkinan. “Kami hanya mencoba memahami lanskap baru ini yang benar -benar ada sepanjang waktu,” kata Zhandry.

Cerita asli dicetak ulang dengan izin dari Berapa banyak majalahpublikasi editorial independen dari Yayasan Simons yang misinya adalah untuk meningkatkan pemahaman publik tentang sains dengan meliput perkembangan penelitian dan tren matematika dan ilmu fisik dan kehidupan.