NTRU: Sejarah, Desain, dan Keamanan

NTRU ditemukan oleh Hoffstein, Pipher, dan Silverman pada 1996, sehingga menjadi salah satu sistem kunci publik pascakuantum tertua yang masih dianggap aman. Tidak seperti RSA dan ECC yang mengandalkan kesulitan teori bilangan, keamanan NTRU didasarkan pada sulitnya menemukan vektor pendek dalam kisi tertentu yang diturunkan dari gelanggang polinomial. NTRU dikomersialkan dan diterapkan dalam beberapa produk keamanan sebelum kriptografi pascakuantum menjadi arus utama.

NTRU beroperasi dalam gelanggang polinomial terpotong Z[X]/(X^N - 1), dengan N sebagai bilangan prima. Polinomial dalam gelanggang ini memiliki derajat paling tinggi N-1, dan perkalian berputar kembali (konvolusi). Pemilihan gelanggang serta struktur polinomial berkoefisien kecil menjadi inti efisiensi dan sifat keamanan NTRU.

Pembuatan kunci memilih dua polinomial kecil f dan g dengan koefisien dalam {-1, 0, 1}. Polinomial f harus memiliki invers modulo p (bilangan prima kecil, biasanya 3) dan q (bilangan prima yang lebih besar, biasanya 2048). Kunci publiknya adalah h = f_q^{-1} * g mod q, dengan f_q sebagai invers f modulo q. Kunci privatnya adalah pasangan (f, g).

Untuk mengenkripsi polinomial pesan m dengan koefisien kecil, pengirim memilih polinomial pengacak kecil r secara acak dan menghitung c = r * h + m mod q. Teks tersandi c adalah polinomial dalam gelanggang yang sama. r acak mencegah dua enkripsi pesan yang sama tampak identik, sehingga tercapai keamanan semantik.

Dekripsi menghitung a = f * c mod q dengan memilih koefisien dalam rentang (-q/2, q/2]. Kemudian a mod p memulihkan f_p * m mod p, dan perkalian dengan fp = f^{-1} mod p menghasilkan m. Struktur galat kecil memastikan koefisien f * c cukup kecil sehingga operasi mod q dan mod p saling berinteraksi dengan benar untuk memulihkan pesan tanpa kegagalan akibat derau.

NTRU modern memiliki dua keluarga parameter yang distandarkan: NTRU-HPS (Hoffstein-Pipher-Silverman) dan NTRU-HRSS (Hulsing-Rijneveld-Schanck-Schwabe). NTRU-HPS menggunakan polinomial pesan ternari, sedangkan NTRU-HRSS menggunakan pengodean acak untuk memperoleh tingkat kegagalan dekripsi yang lebih rendah. Keduanya menjadi finalis putaran 3 PQC NIST, dengan kumpulan parameter yang menargetkan keamanan 128, 192, dan 256 bit.

Belum diketahui serangan dalam waktu polinomial terhadap NTRU yang parameternya dipilih dengan tepat. Serangan terbaik direduksi menjadi pencarian vektor pendek dalam kisi NTRU, yang merupakan contoh masalah SVP hampiran. Kisi NTRU memiliki struktur khusus, yaitu blok sirkulan, yang membuatnya sedikit lebih mudah diserang daripada kisi acak. Oleh karena itu, parameter dipilih dengan margin keamanan yang memperhitungkan struktur ini.

NTRU dilindungi secara luas oleh paten milik NTRU Cryptosystems Inc. (kemudian Security Innovation). Paten asli diajukan pada 1996 dan 1998. Perlindungan paten ini menghambat adopsi secara luas dan implementasi sumber terbuka selama dua dekade. Paten inti NTRU kedaluwarsa sekitar 2017, setelah itu implementasi terbuka berkembang pesat dan NTRU mengikuti kompetisi standardisasi PQC NIST.

NTRU menjadi finalis putaran 3 dalam kompetisi PQC NIST bersama Kyber, Classic McEliece, dan SABER. Pada akhirnya, NIST memilih Kyber (ML-KEM) sebagai standar KEM utama karena analisis keamanannya lebih sederhana dan rancangannya lebih bersih. NTRU tidak distandarkan, tetapi tetap menjadi alternatif yang layak, dan analisisnya turut memperkaya pemahaman tentang keamanan kisi.

NTRUPrime, yang dikembangkan oleh Bernstein, Chuengsatiansup, Lange, dan van Vredendaal, sengaja menghilangkan struktur gelanggang X^N - 1 dan menggantinya dengan X^N - X - 1, yaitu polinomial berderajat prima. Hal ini menghilangkan potensi kelemahan dari struktur gelanggang siklik yang menurut sebagian kriptanalis dapat dimanfaatkan. NTRUPrime juga menjadi kandidat alternatif PQC NIST.

NTRU sudah ada sebelum skema berbasis LWE dan tidak memiliki reduksi formal kesulitan kasus terburuk seperti reduksi LWE oleh Regev. Namun, NTRU lebih cepat dalam pembuatan kunci dan memiliki ukuran teks tersandi yang lebih kecil daripada banyak skema LWE dengan tingkat keamanan yang setara. Imbalannya adalah landasan keamanan yang kurang formal karena bergantung pada pengalaman analisis kriptografi selama beberapa dekade, bukan pada bukti reduksi.

NTRU adalah sistem kriptografi berbasis kisi perintis yang didasarkan pada aritmetika gelanggang polinomial. Pembuatan kunci menggunakan polinomial kecil f dan g, dengan kunci publik h = f^{-1}*g mod q. Enkripsi menggunakan pengacakan, sedangkan dekripsi memanfaatkan struktur koefisien kecil f. NTRU tidak memiliki reduksi kasus terburuk formal, tetapi telah bertahan menghadapi analisis kriptografi selama beberapa dekade. Patennya kedaluwarsa pada 2017, dan NTRU menjadi finalis putaran 3 PQC NIST.