Ring-LWE dan Kisi Modul

LWE standar memerlukan perkalian matriks-vektor berukuran besar, yang menghasilkan ukuran kunci besar. Ring-LWE, yang diperkenalkan oleh Lyubashevsky, Peikert, dan Regev pada 2010, mengganti vektor dan matriks dengan polinomial dalam gelanggang R_q = Z_q[X]/(f(X)). Lingkungan yang terstruktur ini memungkinkan kunci yang jauh lebih ringkas dan aritmetika yang lebih cepat, sehingga Ring-LWE menjadi landasan praktis bagi kriptografi kisi di dunia nyata.

Polinomial f(X) yang digunakan dalam Ring-LWE biasanya berupa f(X) = X^n + 1, dengan n sebagai pangkat 2. Polinomial ini adalah polinomial siklotomik ke-2n. Polinomial tersebut dipilih karena tak tereduksi atas Z, memastikan gelanggang R_q memiliki sifat aljabar yang baik, dan memungkinkan Transformasi Teoretis Bilangan (NTT) untuk perkalian yang efisien. Gelanggang siklotomik telah dipelajari secara mendalam dan diyakini aman.

Dalam Ring-LWE, rahasia s adalah polinomial dalam R_q, dan sampelnya berbentuk (a, b = a*s + e), dengan a sebagai elemen gelanggang acak yang terdistribusi seragam dan e sebagai polinomial galat kecil. Penyerang melihat banyak sampel semacam itu dan harus memulihkan s atau membedakannya dari sampel yang terdistribusi seragam. Tingkat kesulitannya bergantung pada asumsi Ring-LWE, yang memiliki reduksi dari masalah kasus terburuk pada kisi ideal.

Ring-LWE lebih sulit bagi penyerang, tetapi juga memiliki reduksi keamanan yang sedikit berbeda dari LWE biasa. Reduksinya berasal dari masalah kasus terburuk pada kisi ideal (ideal-SVP), bukan dari kisi sembarang. Struktur tambahan pada kisi ideal secara prinsip dapat membuatnya lebih mudah daripada kisi umum, dan hal ini masih menjadi bidang penelitian aktif. Belum diketahui serangan praktis yang memanfaatkan struktur tersebut.

Module-LWE (M-LWE) menggeneralisasi LWE dan Ring-LWE dengan menggunakan matriks berukuran k x k yang elemen-elemennya berupa elemen gelanggang, bukan satu elemen gelanggang atau matriks bilangan bulat berukuran besar. Saat k = 1, masalah ini menjadi Ring-LWE; ketika k bertambah besar, masalah ini mendekati LWE standar. Parameter k yang dapat disetel ini memungkinkan penyeimbangan antara keyakinan terhadap keamanan dan kinerja.

CRYSTALS-Kyber (sekarang ML-KEM, FIPS 203) didasarkan pada Module-LWE dengan matriks berperingkat k atas R_q. Parameter k secara langsung mengendalikan tingkat keamanan: k=2 menargetkan keamanan 128 bit (ML-KEM-512), k=3 menargetkan 192 bit (ML-KEM-768), dan k=4 menargetkan 256 bit (ML-KEM-1024). Struktur modul memungkinkan satu basis kode dengan tingkat keamanan yang diskalakan melalui perubahan nilai k.

Perkalian polinomial dalam R_q = Z_q[X]/(X^n + 1) merupakan hambatan kinerja utama. Transformasi Teoretis Bilangan (NTT) adalah transformasi Fourier diskret atas Z_q yang mengubah polinomial ke bentuk evaluasi, sehingga perkalian menjadi operasi per titik. Dengan memilih q agar NTT dapat diterapkan, perkalian polinomial memerlukan waktu O(n log n), bukan O(n^2), sehingga menjadi pengoptimalan penting dalam ML-KEM dan ML-DSA.

NTT mengharuskan q berupa bilangan prima dengan q = 1 mod 2n, sehingga Z_q memuat akar kesatuan primitif ke-2n. Untuk ML-KEM dengan n = 256, q = 3329 memenuhi persyaratan ini. NTT atas Z_3329 sangat cepat pada perangkat keras modern dengan instruksi SIMD, sehingga memungkinkan ribuan operasi ML-KEM per detik pada CPU umum.

Ring-LWE dan Module-LWE secara drastis mengurangi ukuran kunci dibandingkan LWE standar. Kunci publik LWE standar untuk keamanan 128 bit mungkin berukuran 1 MB; Ring-LWE menguranginya menjadi sekitar 800 bita, sedangkan Module-LWE (ML-KEM-768) menghasilkan kunci publik berukuran 1184 bita dengan keamanan pascakuantum 192 bit. Ukuran yang ringkas ini membuat skema kisi praktis untuk TLS dan sistem tertanam.

Sejumlah kriptografer khawatir bahwa struktur aljabar tambahan pada gelanggang siklotomik dapat memungkinkan serangan yang tidak berlaku pada LWE biasa. Pada 2024, Elias Rokicki dan para kolaboratornya menerbitkan analisis terhadap polinomial siklotomik ke-2n, yang tidak menemukan eksploitasi praktis, tetapi menekankan pentingnya penelaahan berkelanjutan. Proses PQC NIST mempertimbangkan risiko ini dan memilih Module-LWE, salah satunya untuk mengurangi ketergantungan pada satu struktur gelanggang tertentu.

Selain Kyber, Ring-LWE menjadi dasar CRYSTALS-Dilithium (ML-DSA), skema tanda tangan yang distandardisasi NIST. Pustaka SEAL dari Microsoft memungkinkan enkripsi homomorfik melalui Ring-LWE. Pustaka kriptografi Tink dari Google menyertakan dukungan untuk ML-KEM. Ring-LWE telah berpindah dari konstruksi teoretis ke penerapan produksi dalam waktu yang sangat singkat, didorong oleh proses standardisasi NIST.

Apa keunggulan utama Ring-LWE dibandingkan LWE standar?

Ring-LWE memindahkan LWE ke dalam gelanggang polinomial R_q = Z_q[X]/(X^n+1), sehingga secara drastis mengurangi ukuran kunci dan memungkinkan aritmetika cepat berbasis NTT. Module-LWE menggeneralisasikannya dengan struktur berperingkat-k, yang menjadi dasar ML-KEM (FIPS 203) dan ML-DSA (FIPS 204). Bilangan prima q = 3329 yang ramah terhadap NTT memungkinkan implementasi yang efisien. Keamanan bertumpu pada kesulitan masalah pada kisi ideal dan kisi modul.