Analysis of the Number-Theoretic Transform (NTT) on Module Learning With Errors (MLWE)
Bagas Adnan Rasyid, Uha Isnaini, S.Si., M.Sc., Ph.D.
2026 | Skripsi | MATEMATIKA
Skema berbasis Module Learning With Errors (MLWE), seperti standar tanda tangan digital ML-DSA, menghabiskan sebagian besar komputasinya pada perkalian polinomial, sehingga mendorong penggunaan Number-Theoretic Transform (NTT). Dengan memanfaatkan struktur ring, lapangan hingga, dan modul, skripsi ini merumuskan syarat pada modulus agar NTT menjadi isomorfisma ring pada ring polinomial yang digunakan dalam MLWE, sehingga perkalian polinomial menjadi perkalian per komponen. Dengan Theta menyatakan laju pertumbuhan asimtotik biaya komputasi, ditunjukkan bahwa, sebagai fungsi dari derajat polinomial n, biaya operasi matriks MLWE turun dari Theta(n^2) menjadi Theta(n log n) untuk ukuran matriks tetap. Implementasi dalam bahasa Python pada set parameter NIST FIPS 204 menegaskan hasil yang identik dan menunjukkan bahwa pendekatan berbasis NTT sekitar 16 hingga 29 kali lebih cepat, sejalan dengan analisis teoretis.
Schemes based on the Module Learning With Errors (MLWE) problem, such as the ML-DSA digital signature standard, devote most of their computational effort to polynomial multiplication, motivating the use of the Number-Theoretic Transform (NTT). By exploiting the structures of rings, finite fields, and modules, this thesis establishes the conditions on the modulus under which the NTT becomes a ring isomorphism on the polynomial ring employed in MLWE, allowing polynomial multiplication to be reduced to component-wise multiplication. Using Theta notation to represent the asymptotic growth rate of computational complexity, it is shown that, as a function of the polynomial degree n, the computational cost of the MLWE matrix operation decreases from Theta(n^2) to Theta(n log n) for a fixed matrix size. A Python implementation using the parameter sets specified in NIST FIPS 204 confirms the equivalence of the results and demonstrates that the NTT-based approach is approximately 16 to 29 times faster, consistent with the theoretical analysis.
Kata Kunci : Kriptografi Berbasis Latis, Module Learning With Errors, Number-Theoretic Transform, Isomorfisma Ring, Kompleksitas Asimtotik.