Dasar Learning With Errors (LWE)

Learning With Errors (LWE) oleh Regev (2005): diberikan banyak persamaan linear berderau atas Z_q, temukan vektor rahasia s. Derau e berukuran kecil, tetapi mencegah eliminasi Gauss. Tanpa derau, sistem ini mudah; dengan derau sekecil apa pun, sistem ini menjadi sulit secara komputasional.

Rahasia s ∈ Z_q^n. Penyerang menerima sampel (a_i, b_i), dengan a_i ∈ Z_q^n acak, b_i = + e_i mod q, dan e_i adalah derau kecil dari distribusi χ (misalnya, Gaussian dengan σ = √n). Tugasnya adalah menemukan s berdasarkan sejumlah sampel polinomial.

Tanpa derau: b_i = mod q. Eliminasi Gauss memulihkan s dalam O(n^3). Dengan derau: bahkan satu persamaan yang keliru dapat merusak eliminasi. Derau cukup kecil sehingga dekripsi tetap berhasil (menggunakan kunci), tetapi cukup besar untuk mencegah kriptoanalisis.

Regev membuktikan bahwa LWE dapat direduksi menjadi masalah kisi kasus terburuk (SIVP, GapSVP) melalui reduksi kuantum. Artinya, jika LWE berhasil dipecahkan, banyak masalah kisi yang sulit juga terselesaikan—tetapi belum ada algoritma kuantum yang diketahui untuk masalah kisi. LWE aman pascakuantum.

RLWE mengganti Z_q^n dengan cincin Z_q[x]/(f(x)) untuk polinom siklotomik f. Satu sampel RLWE mengodekan n persamaan sehingga jauh lebih efisien. RLWE menjadi dasar bagi Kyber (KEM), Dilithium (tanda tangan), serta skema HE BFV/BGV/CKKS.

Keamanan bergantung pada: n (dimensi, biasanya 512-2048), q (modulus, 1024-2^60), dan σ (simpangan baku derau). n yang lebih besar serta rasio σ/q yang lebih kecil berarti masalahnya lebih sulit. Standar Pascakuantum NIST menggunakan n=256 (dimensi modul) dengan k modul (k=2,3,4).

Kunci publik: (A, b=As+e). Enkripsi bit m: pilih r acak, lalu hitung teks sandi (u=A^T r, v = b^T r + m*q/2). Dekripsi: v - s^T u = e^T r + m*q/2 ≈ m*q/2. Bulatkan ke m terdekat. Derau e membuat m tetap tersembunyi dalam teks sandi selama enkripsi.

LWE Keputusan: bedakan (a, As+e) dari (a, u), dengan u acak seragam. Keduanya tidak dapat dibedakan secara komputasional jika LWE sulit dipecahkan. Inilah dasar keamanan semantik—teks sandi tampak seperti derau acak bagi penyerang yang tidak memiliki kunci rahasia.

Serangan terbaik yang diketahui: reduksi kisi BKZ (Blok Korkine-Zolotarev). Kompleksitasnya subeksponensial, tetapi bukan polinomial. BKZ-β memerlukan 2^{0.292β} operasi. Untuk LWE-512: keamanannya sekitar 128 bit terhadap BKZ. Belum ada percepatan kuantum yang diketahui untuk BKZ.

Module-LWE (digunakan dalam Kyber) adalah RLWE pada modul dengan peringkat k. Ini memberikan fleksibilitas: k=2 untuk keamanan 512 bit, k=3 untuk 768 bit, dan k=4 untuk 1024 bit. Keamanan dan performa meningkat seiring k. NIST memilih Kyber (berganti nama menjadi ML-KEM) sebagai standar PQC.

Keamanan RSA/ECC didasarkan pada faktorisasi bilangan bulat dan logaritma diskret (rentan terhadap kuantum melalui algoritma Shor). Keamanan LWE didasarkan pada masalah kisi kasus terburuk (belum ada percepatan kuantum yang diketahui). Ukuran kunci: kunci LWE sekitar 1 KB, sedangkan RSA-2048 berukuran 256 bita. LWE lebih besar, tetapi aman terhadap kuantum.

Apa yang membuat LWE sulit dipecahkan meskipun tersedia banyak sampel?

LWE: menemukan rahasia s dari persamaan linear berderau—sulit bagi komputer kuantum. RLWE menggunakan cincin polinom untuk efisiensi. Menjadi dasar bagi Kyber, Dilithium, dan skema HE. Berikutnya: skema HE BGV dan BFV untuk operasi bilangan bulat.