Ring-LWE dan Kekisi Modul

LWE standard memerlukan hasil darab matriks-vektor yang besar, lalu menghasilkan saiz kunci yang besar. Ring-LWE, yang diperkenalkan oleh Lyubashevsky, Peikert dan Regev pada tahun 2010, menggantikan vektor dan matriks dengan polinomial dalam gelanggang R_q = Z_q[X]/(f(X)). Tetapan berstruktur ini membolehkan kunci yang jauh lebih padat serta aritmetik yang lebih pantas, menjadikan Ring-LWE asas praktikal bagi kriptografi kekisi dunia sebenar.

Polinomial f(X) yang digunakan dalam Ring-LWE biasanya ialah f(X) = X^n + 1, dengan n sebagai kuasa 2. Ini ialah polinomial siklotomi ke-2n. Polinomial ini dipilih kerana tidak boleh diuraikan atas Z, memastikan gelanggang R_q mempunyai sifat algebra yang baik dan membolehkan Transformasi Teori Nombor (NTT) untuk pendaraban yang cekap. Gelanggang siklotomi telah dikaji secara mendalam dan dipercayai selamat.

Dalam Ring-LWE, rahsia s ialah polinomial dalam R_q, dan sampel berbentuk (a, b = a*s + e), dengan a sebagai unsur gelanggang rawak seragam dan e sebagai polinomial ralat kecil. Penyerang melihat banyak sampel sedemikian dan mesti mendapatkan semula s atau membezakannya daripada taburan seragam. Kesukaran masalah ini bergantung pada andaian Ring-LWE, yang mempunyai pengurangan daripada masalah kes terburuk pada kekisi ideal.

Ring-LWE lebih sukar bagi penyerang tetapi juga mempunyai pengurangan keselamatan yang sedikit berbeza daripada LWE biasa. Pengurangan ini datang daripada masalah kes terburuk pada kekisi ideal (ideal-SVP), bukannya kekisi sewenang-wenangnya. Struktur tambahan kekisi ideal pada prinsipnya boleh menjadikannya lebih mudah daripada kekisi umum, dan perkara ini merupakan bidang penyelidikan yang aktif. Tiada serangan praktikal yang mengeksploitasi struktur ini diketahui.

Module-LWE (M-LWE) menggeneralisasikan LWE dan Ring-LWE dengan menggunakan matriks berukuran k x k yang terdiri daripada unsur gelanggang, bukannya satu unsur gelanggang atau matriks integer yang besar. Apabila k = 1, ia menjadi Ring-LWE; apabila k bertambah, ia menghampiri LWE standard. Parameter k yang boleh dilaras ini membolehkan keseimbangan antara keyakinan terhadap keselamatan dan prestasi.

CRYSTALS-Kyber, yang kini dikenali sebagai ML-KEM (FIPS 203), berdasarkan Module-LWE dengan matriks berpangkat k atas R_q. Parameter k mengawal tahap keselamatan secara langsung: k=2 menyasarkan keselamatan 128 bit (ML-KEM-512), k=3 menyasarkan 192 bit (ML-KEM-768) dan k=4 menyasarkan 256 bit (ML-KEM-1024). Struktur modul membolehkan satu pangkalan kod dengan keselamatan yang diskalakan melalui perubahan k.

Pendaraban polinomial dalam R_q = Z_q[X]/(X^n + 1) merupakan halangan prestasi utama. Transformasi Teori Nombor (NTT) ialah transformasi Fourier diskret atas Z_q yang menukar polinomial kepada bentuk penilaian, yang menjadikan pendaraban berlaku mengikut titik. Dengan q dipilih supaya NTT boleh digunakan, pendaraban polinomial mengambil masa O(n log n), bukannya O(n^2), iaitu pengoptimuman penting dalam ML-KEM dan ML-DSA.

NTT memerlukan q merupakan nombor perdana yang memenuhi q = 1 mod 2n, sekali gus memastikan bahawa Z_q mengandungi punca primitif kesatuan peringkat ke-2n. Bagi ML-KEM dengan n = 256, q = 3329 memenuhi keperluan ini. NTT atas Z_3329 sangat pantas pada perkakasan moden dengan arahan SIMD, membolehkan ribuan operasi ML-KEM sesaat pada CPU biasa.

LWE gelang dan LWE modul mengurangkan saiz kunci dengan ketara berbanding LWE piawai. Kunci awam LWE piawai untuk keselamatan 128 bit mungkin berukuran 1 MB; LWE gelang mengurangkannya kepada kira-kira 800 bait, manakala LWE modul (ML-KEM-768) mencapai kunci awam berukuran 1184 bait dengan keselamatan pascakuantum 192 bit. Saiz yang kecil ini menjadikan skema kekisi praktikal untuk TLS dan sistem terbenam.

Sesetengah ahli kriptografi bimbang bahawa struktur algebra tambahan gelang siklotomik mungkin membolehkan serangan yang tidak terpakai pada LWE biasa. Pada tahun 2024, Elias Rokicki dan rakan-rakannya menerbitkan analisis polinomial siklotomik ke-2n, dan tidak menemui eksploitasi praktikal, tetapi menekankan pentingnya penelitian berterusan. Proses PQC NIST mempertimbangkan risiko ini dan memilih LWE modul sebahagiannya untuk mengurangkan kebergantungan pada mana-mana satu struktur gelang.

Selain Kyber, LWE gelang menjadi asas kepada CRYSTALS-Dilithium (ML-DSA), iaitu skema tandatangan yang dipiawaikan oleh NIST. Pustaka SEAL daripada Microsoft membolehkan penyulitan homomorfik melalui LWE gelang. Pustaka kriptografi Tink daripada Google menyertakan sokongan untuk ML-KEM. LWE gelang telah beralih daripada pembinaan teori kepada penggunaan dalam sistem sebenar dalam tempoh yang amat singkat, didorong oleh proses penyeragaman NIST.

LWE gelang memindahkan LWE ke dalam gelang polinomial R_q = Z_q[X]/(X^n+1), sekali gus mengurangkan saiz kunci dengan ketara dan membolehkan aritmetik pantas berasaskan NTT. LWE modul menggeneralisasikan pendekatan ini dengan struktur berperingkat k, dan menjadi asas kepada ML-KEM (FIPS 203) serta ML-DSA (FIPS 204). Nombor perdana q = 3329 yang serasi dengan NTT membolehkan pelaksanaan yang cekap. Keselamatan bergantung pada kesukaran masalah pada kekisi ideal dan kekisi modul.