Learning With Errors: Masalah yang Sulit

Masalah Pembelajaran dengan Kesalahan (LWE) diperkenalkan oleh Oded Regev pada 2005 sebagai dasar kriptografi pascakuantum. Diberikan matriks acak A di atas Z_q dan vektor b = As + e, tujuannya adalah menemukan vektor rahasia s. Vektor e merupakan kesalahan kecil yang diambil dari distribusi Gaussian diskret, sehingga masalah ini sulit dipecahkan secara komputasi.

Dalam masalah LWE, A adalah matriks acak berukuran m x n yang diambil secara seragam dari Z_q, dengan q sebagai modulus prima. Rahasia s adalah vektor berdimensi n, sedangkan e adalah vektor galat kecil yang setiap entrinya diambil dari distribusi Gauss sempit. Bahkan dengan mengetahui struktur A, penyerang tetap tidak dapat membedakan b dari vektor acak yang terdistribusi seragam.

Terdapat dua formulasi baku LWE. LWE Pencarian meminta kita memulihkan rahasia s berdasarkan banyak sampel (A, b). LWE Keputusan meminta kita membedakan sampel (A, As + e) dari pasangan acak yang terdistribusi seragam (A, u). Kedua formulasi tersebut ekuivalen secara polinomial, artinya algoritme yang menyelesaikan salah satunya dapat diubah untuk menyelesaikan yang lainnya.

Suku galat dalam LWE diambil dari distribusi Gauss diskret atas bilangan bulat, yang diparameterkan oleh simpangan baku sigma. Nilai sigma yang kecil memastikan bahwa e pendek dibandingkan dengan q, sehingga b tampak hampir seperti As mod q. Jika sigma bernilai nol, tidak akan ada galat dan sistem dapat diselesaikan dengan eliminasi Gauss, sehingga galat sangat penting bagi tingkat kesulitannya.

Regev membuktikan sebuah reduksi yang luar biasa: menyelesaikan sampel LWE kasus rata-rata setidaknya sama sulitnya dengan menyelesaikan contoh kasus terburuk dari Masalah Vektor Terpendek (SVP) pada kisi. Artinya, jika Anda dapat memecahkan LWE secara efisien, Anda dapat menyelesaikan masalah kisi apa pun secara efisien. Belum diketahui algoritme klasik maupun kuantum yang dapat menyelesaikan SVP kasus terburuk dalam waktu polinomial.

Tidak seperti RSA dan kriptografi kurva eliptik, belum ada algoritme kuantum yang diketahui memberikan percepatan eksponensial terhadap LWE. Algoritme Grover menawarkan percepatan paling tinggi kuadratik, sedangkan algoritme kisi kuantum terbaik, yaitu varian BKZ, tidak dapat memecahkan LWE jika parameternya dipilih dengan tepat. Hal ini menjadikan LWE landasan yang kuat bagi keamanan pascakuantum.

Keamanan LWE ditentukan oleh tiga parameter: dimensi n (panjang rahasia), modulus q, dan simpangan baku galat sigma. Nilai n yang lebih besar serta rasio q/sigma yang lebih kecil meningkatkan keamanan. Untuk keamanan pascakuantum 128 bit, nilai yang umum digunakan adalah n = 1024, q sekitar 12289, dan sigma sekitar 3.2. Alat pengestimasi kisi karya Albrecht dkk. digunakan untuk mengevaluasi keamanan konkret.

Masalah Solusi Bilangan Bulat Pendek (SIS) adalah asumsi kesulitan kisi terkait yang digunakan untuk tanda tangan. Diberikan matriks acak A atas Z_q, carilah vektor tak nol pendek x sedemikian rupa sehingga Ax = 0 mod q. SIS menjadi dasar fungsi hash dan skema tanda tangan dalam dunia kisi, serta melengkapi LWE yang mendasari enkripsi dan enkapsulasi kunci.

Skema enkripsi LWE sederhana bekerja sebagai berikut: kunci publiknya adalah (A, b = As + e), sedangkan kunci rahasianya adalah s. Untuk mengenkripsi bit m, pengirim menghitung (u, v) = (A^T r, b^T r + m * floor(q/2)) untuk vektor biner acak r. Dekripsi menghitung v - s^T u lalu membulatkan hasilnya untuk memulihkan m. Skema ini mencapai keamanan IND-CPA berdasarkan asumsi LWE.

LWE memungkinkan berbagai konstruksi kriptografi selain enkripsi dasar. Konstruksi tersebut mencakup enkripsi homomorfik penuh (FHE), enkripsi berbasis identitas (IBE), enkripsi berbasis atribut (ABE), dan protokol pertukaran kunci. CRYSTALS-Kyber (sekarang ML-KEM, distandarkan sebagai FIPS 203) adalah skema berbasis LWE yang paling banyak diterapkan dalam praktik.

Kriptografi berbasis LWE sudah mulai digunakan dalam sistem produksi. Google dan Cloudflare melakukan eksperimen TLS menggunakan Kyber pada 2018–2020. Chrome dan Firefox menambahkan dukungan untuk ML-KEM-768 dalam jabat tangan TLS hibrida pada 2024. Signal Protocol menambahkan lapisan pascakuantum (PQXDH) menggunakan ML-KEM-1024 untuk kerahasiaan ke depan, sehingga melindungi kerahasiaan pesan jangka panjang dari komputer kuantum di masa mendatang.

Pernyataan manakah yang paling tepat menggambarkan jaminan tingkat kesulitan masalah LWE?

LWE adalah salah satu asumsi kesulitan pascakuantum yang paling banyak dipelajari, dengan dukungan reduksi kasus terburuk yang kuat dari masalah kisi. Ketiga parameternya (n, q, sigma) mengendalikan pertukaran antara keamanan dan kinerja. LWE tahan terhadap serangan kuantum dan menjadi dasar skema yang distandarkan NIST. Memahami LWE merupakan pintu masuk ke seluruh kriptografi berbasis kisi modern, termasuk ML-KEM dan ML-DSA.