NTRU: Geschichte, Design und Sicherheit

NTRU wurde 1996 von Hoffstein, Pipher und Silverman erfunden und ist damit eines der ältesten noch als sicher geltenden Public-Key-Systeme für die Post-Quanten-Kryptografie. Im Gegensatz zu RSA und ECC, deren Sicherheit auf zahlentheoretischen Problemen beruht, basiert die Sicherheit von NTRU auf der Schwierigkeit, kurze Vektoren in einem bestimmten, aus Polynomringen abgeleiteten Gitter zu finden. NTRU wurde kommerzialisiert und in mehreren Sicherheitsprodukten eingesetzt, bevor sich die Post-Quanten-Kryptografie allgemein durchsetzte.

NTRU arbeitet im gekürzten Polynomring Z[X]/(X^N - 1), wobei N eine Primzahl ist. Polynome in diesem Ring haben höchstens den Grad N-1, und bei der Multiplikation wird zyklisch gewickelt (Faltung). Die Wahl des Rings und die Struktur von Polynomen mit kleinen Koeffizienten sind entscheidend für die Effizienz und die Sicherheitseigenschaften von NTRU.

Bei der Schlüsselerzeugung werden zwei kleine Polynome f und g mit Koeffizienten aus {-1, 0, 1} ausgewählt. Das Polynom f muss sowohl modulo p, einer kleinen Primzahl, typischerweise 3, als auch modulo q, einer größeren Primzahl, typischerweise 2048, invertierbar sein. Der öffentliche Schlüssel ist h = f_q^{-1} * g mod q, wobei f_q die Inverse von f modulo q ist. Der geheime Schlüssel ist das Paar (f, g).

Um ein Nachrichtenpolynom m mit kleinen Koeffizienten zu verschlüsseln, wählt der Sender ein zufälliges kleines Maskierungspolynom r und berechnet c = r * h + m mod q. Der Chiffretext c ist ein Polynom im selben Ring. Das zufällige r verhindert, dass zwei Verschlüsselungen derselben Nachricht identisch aussehen, und gewährleistet so semantische Sicherheit.

Bei der Entschlüsselung wird a = f * c mod q berechnet, wobei die Koeffizienten in den Bereich (-q/2, q/2] gebracht werden. Dann ergibt a mod p den Wert f_p * m mod p, und die Multiplikation mit fp = f^{-1} mod p liefert m. Die Struktur des kleinen Fehlers stellt sicher, dass die Koeffizienten von f * c klein genug bleiben, damit die Operationen modulo q und modulo p korrekt zusammenwirken und die Nachricht ohne einen Rauschfehler wiederhergestellt werden kann.

Das moderne NTRU hat zwei standardisierte Parameterfamilien: NTRU-HPS (Hoffstein-Pipher-Silverman) und NTRU-HRSS (Hulsing-Rijneveld-Schanck-Schwabe). NTRU-HPS verwendet Nachrichtenpolynome mit ternären Koeffizienten, während NTRU-HRSS eine randomisierte Kodierung nutzt, um die Rate von Entschlüsselungsfehlern zu verbessern. Beide waren Finalisten der dritten Runde der NIST-PQC-Auswahl und bieten Parametersätze für eine Sicherheit von 128, 192 und 256 Bit.

Gegen korrekt parametriertes NTRU ist kein Angriff in polynomieller Zeit bekannt. Die besten Angriffe laufen darauf hinaus, einen kurzen Vektor in einem NTRU-Gitter zu finden, was eine Instanz des Problems des approximativen SVP ist. Das NTRU-Gitter besitzt eine besondere Struktur mit zirkulären Blöcken, die einen Angriff etwas leichter macht als bei einem zufälligen Gitter. Daher werden die Parameter mit einer Sicherheitsmarge gewählt, die diese Struktur berücksichtigt.

NTRU war durch NTRU Cryptosystems Inc., später Security Innovation, umfassend patentiert. Die ursprünglichen Patente wurden 1996 und 1998 eingereicht. Dieser Patentschutz behinderte zwei Jahrzehnte lang die breite Einführung und die Entwicklung von Open-Source-Implementierungen. Die Kernpatente von NTRU liefen ungefähr 2017 aus. Danach verbreiteten sich offene Implementierungen, und NTRU nahm am Standardisierungswettbewerb für NIST-PQC teil.

NTRU war neben Kyber, Classic McEliece und SABER ein Finalist der dritten Runde des NIST-PQC-Wettbewerbs. NIST wählte letztlich Kyber (ML-KEM) als primären KEM-Standard und verwies dabei auf die einfachere Sicherheitsanalyse und das klarere Design. NTRU wurde nicht standardisiert, bleibt aber eine tragfähige Alternative, und seine Analyse trug zum Verständnis der Gittersicherheit bei.

NTRUPrime, entwickelt von Bernstein, Chuengsatiansup, Lange und van Vredendaal, entfernt absichtlich die Ringstruktur X^N - 1 und ersetzt sie durch X^N - X - 1, ein Polynom vom Primgrad. Dadurch werden potenzielle Schwachstellen der zyklischen Ringstruktur beseitigt, die nach Ansicht einiger Kryptoanalytiker ausgenutzt werden könnten. NTRUPrime war ebenfalls ein alternativer Kandidat für NIST-PQC.

NTRU ist älter als LWE-basierte Verfahren und verfügt nicht über eine formale Worst-Case-Härtereduktion wie die LWE-Reduktion von Regev. Bei gleichwertigen Sicherheitsniveaus ist NTRU jedoch bei der Schlüsselerzeugung schneller und hat kleinere Chiffretexte als viele LWE-Verfahren. Der Kompromiss besteht in einer weniger formalen Sicherheitsgrundlage: Sie beruht eher auf jahrzehntelanger kryptoanalytischer Erfahrung als auf einem Reduktionsbeweis.

Woraus wird der öffentliche Schlüssel bei NTRU abgeleitet?

NTRU ist ein wegweisendes gitterbasiertes Kryptosystem, das auf der Arithmetik von Polynomringen beruht. Bei der Schlüsselerzeugung werden die kleinen Polynome f und g verwendet, wobei der öffentliche Schlüssel h = f^{-1}*g mod q ist. Die Verschlüsselung verwendet eine zufällige Maskierung, und die Entschlüsselung nutzt die Struktur der kleinen Koeffizienten von f. NTRU verfügt über keine formale Worst-Case-Reduktion, hat aber jahrzehntelanger Kryptoanalyse standgehalten. Seine Patente liefen 2017 aus, und NTRU war ein Finalist der dritten Runde von NIST-PQC.