NTRU: Tarihçe, Tasarım ve Güvenlik

NTRU, 1996 yılında Hoffstein, Pipher ve Silverman tarafından icat edilmiştir; bu nedenle günümüzde hâlâ güvenli kabul edilen en eski kuantum sonrası açık anahtarlı sistemlerden biridir. Sayı kuramına dayalı zorluk varsayımına dayanan RSA ve ECC'nin aksine NTRU'nun güvenliği, polinom halkalarından türetilen belirli bir kafeste kısa vektörleri bulmanın zorluğuna dayanır. NTRU, kuantum sonrası kriptografi yaygınlaşmadan önce ticarileştirilmiş ve çeşitli güvenlik ürünlerinde kullanılmıştır.

NTRU, Z[X]/(X^N - 1) kesilmiş polinom halkasında çalışır; burada N bir asaldır. Bu halkadaki polinomların derecesi en fazla N-1'dir ve çarpım döngüsel olarak sarar (konvolüsyon). Halka seçimi ve küçük katsayılı polinomların yapısı, hem NTRU'nun verimliliği hem de güvenlik özellikleri açısından merkezi öneme sahiptir.

Anahtar üretiminde, katsayıları {-1, 0, 1} kümesinde bulunan iki küçük f ve g polinomu seçilir. f polinomu hem p'ye (küçük asal, genellikle 3) hem de q'ya (daha büyük asal, genellikle 2048) göre terslenebilir olmalıdır. Açık anahtar h = f_q^{-1} * g mod q değeridir; burada f_q, f'nin q'ya göre tersidir. Özel anahtar (f, g) çiftidir.

Küçük katsayılara sahip bir m mesaj polinomunu şifrelemek için gönderici, rastgele küçük bir maskeleme polinomu r seçer ve c = r * h + m mod q değerini hesaplar. Şifreli metin c, aynı halkada bulunan bir polinomdur. Rastgele r, aynı mesajın iki şifreleme işleminin birbirinin aynısı görünmesini engelleyerek anlamsal güvenlik sağlar.

Şifre çözme işlemi, katsayıları (-q/2, q/2] aralığında seçerek a = f * c mod q değerini hesaplar. Ardından a mod p, f_p * m mod p değerini verir ve fp = f^{-1} mod p ile çarpılması m'yi geri kazandırır. Küçük hata yapısı, f * c katsayılarının yeterince küçük olmasını sağlar; böylece mod q ve mod p işlemleri, gürültü nedeniyle başarısızlık yaşanmadan mesajı geri kazanacak şekilde etkileşir.

Modern NTRU'nun iki standartlaştırılmış parametre ailesi vardır: NTRU-HPS (Hoffstein-Pipher-Silverman) ve NTRU-HRSS (Hulsing-Rijneveld-Schanck-Schwabe). NTRU-HPS üç değerli mesaj polinomları kullanırken NTRU-HRSS, daha iyi şifre çözme başarısızlığı oranları için rastgeleleştirilmiş bir kodlama kullanır. Her ikisi de NIST PQC üçüncü tur finalistleri arasında yer almış ve 128, 192 ve 256 bitlik güvenliği hedefleyen parametre kümelerine sahip olmuştur.

Doğru parametrelerle yapılandırılmış NTRU'ya karşı polinom zamanda çalışan bilinen bir saldırı yoktur. En iyi saldırılar, bir NTRU kafesinde kısa bir vektör bulma problemine indirgenir; bu da yaklaşık SVP probleminin bir örneğidir. NTRU kafesi, rastgele bir kafese kıyasla saldırılması biraz daha kolay olan belirli bir yapıya (döngüsel bloklara) sahiptir; bu nedenle parametreler, bu yapıyı hesaba katan bir güvenlik payıyla seçilir.

NTRU, NTRU Cryptosystems Inc. (daha sonra Security Innovation) tarafından çok sayıda patentle korunuyordu. İlk patent başvuruları 1996 ve 1998 yıllarında yapıldı. Bu patent koruması, yirmi yıl boyunca yaygın kullanımı ve açık kaynaklı uygulamaları engelledi. NTRU'nun temel patentlerinin süresi yaklaşık 2017 yılında doldu; bunun ardından açık uygulamalar hızla çoğaldı ve NTRU, NIST PQC standardizasyon yarışmasına katıldı.

NTRU, NIST PQC yarışmasının üçüncü turunda Kyber, Classic McEliece ve SABER ile birlikte finalist oldu. NIST, daha basit güvenlik analizi ve daha yalın tasarım gerekçeleriyle Kyber'i (ML-KEM) birincil KEM standardı olarak seçti. NTRU standarda alınmadı, ancak uygulanabilir bir alternatif olmayı sürdürmektedir; NTRU'nun analizi kafes güvenliğinin anlaşılmasına katkıda bulunmuştur.

Bernstein, Chuengsatiansup, Lange ve van Vredendaal tarafından geliştirilen NTRUPrime, X^N - 1 halka yapısını bilinçli olarak kaldırır ve yerine asal dereceli bir polinom olan X^N - X - 1'i koyar. Böylece bazı kriptanalistlerin istismar edilebileceğine inandığı döngüsel halka yapısından kaynaklanabilecek olası zayıflıklar ortadan kaldırılır. NTRUPrime ayrıca NIST PQC için alternatif aday olmuştur.

NTRU, LWE tabanlı şemalardan daha eskidir ve Regev'in LWE indirgemesi gibi biçimsel bir en kötü durum zorluk indirgemesine sahip değildir. Bununla birlikte NTRU, eşdeğer güvenlik düzeylerinde birçok LWE şemasına kıyasla anahtar üretiminde daha hızlıdır ve daha küçük şifreli metin boyutlarına sahiptir. Bunun karşılığında güvenlik temeli daha az biçimseldir; NTRU, bir indirgeme kanıtı yerine onlarca yıllık kriptanaliz deneyimine dayanır.

NTRU, polinom halkası aritmetiğine dayanan öncü bir kafes tabanlı kriptosistemdir. Anahtar üretiminde küçük f ve g polinomları kullanılır; açık anahtar h = f^{-1}*g mod q değeridir. Şifrelemede rastgele maskeleme kullanılır; şifre çözme ise f'nin küçük katsayılı yapısından yararlanır. NTRU'nun biçimsel bir en kötü durum indirgemesi yoktur, ancak onlarca yıllık kriptanalize dayanmıştır. Patentlerinin süresi 2017 yılında dolmuş ve NIST PQC üçüncü turunda finalist olmuştur.