Explicit cost analysis of Toom-4 multiplication for incomplete NTT in lattice-based cryptography

Technische Zusammenfassung: Explizite Kostenanalyse der Toom-4-Multiplikation für unvollständige NTT in gitterbasierter Kryptographie

Problemstellung
Die Polynommultiplikation ist eine fundamentale Operation in gitterbasierten Kryptosystemen wie Kyber (ML-KEM) und Dilithium (ML-DSA), die typischerweise über Restklassenringen $R_q = \mathbb{F}_q[x]/\langle x^n + 1 \rangle$ durchgeführt wird. Obwohl die Zahlentheoretische Transformation (NTT) eine Multiplikationsgeschwindigkeit von $O(n \log n)$ bietet, erfordert sie strikt die Bedingung $2n \mid (q-1)$. Diese Einschränkung begrenzt die Parametersélection und kann Sicherheits- oder Effizienzziele beeinträchtigen.

Um dies zu adressieren, führten Hafiz et al. (2025) die „unvollständige NTT" ein, die die Modulbedingung lockert, indem sie eine abgeschnittene NTT der Tiefe $\ell$ (wobei $2^{\ell+1} \mid (q-1)$) durchführt und diese mit einer konventionellen Polynommultiplikation für die verbleibenden Teilprobleme kombiniert. Während die Karatsuba-Multiplikation innerhalb dieses Rahmens gut verstanden ist, wurden die genauen Kosten der Toom-4-Multiplikation – insbesondere ihre konstanten Faktoren bezüglich Additionen und Multiplikationen – nicht in einer Form ausgedrückt, die mit dem Kostenmodell der unvollständigen NTT kompatibel ist. Bestehende Analysen von Toom-Cook (z. B. Bodrato und Zanoni) konzentrieren sich auf allgemeine Optimierungen, sind jedoch nicht direkt in das spezifische hybride Framework integriert, das für die unvollständige NTT erforderlich ist.

Methodik
Die Autoren präsentieren eine konkrete Implementierung der Toom-4-Multiplikation, die auf das Framework der unvollständigen NTT zugeschnitten ist, und leiten ein explizites Operationszählmodell ab.

1. Implementierungsstrategie: Die Autoren verwenden ganzzahlige Auswertungsstellen $\{0, \pm 1, \pm 2, 3, \infty\}$, um gebrochene Konstanten zu vermeiden. Alle Divisionen werden auf einen abschließenden Skalierungsschritt verschoben.
2. Optimierung der Additionsketten: Ein kritischer Bestandteil der Methodik ist die Verwendung von Additionsketten zur Berechnung der notwendigen skalaren Vielfachen während der Interpolationsphase. Anstatt einzelne skalare Multiplikationen durchzuführen, konstruieren die Autoren minimale Additionsketten für die Zielkoeffizienten, die von der inversen Vandermonde-Matrix gefordert werden. Dies ermöglicht eine systematische Bestimmung der exakten Anzahl erforderlicher Additionen und Subtraktionen.
3. Kostenableitung: Die Autoren trennen die Operationszahlen in Additionen/Subtraktionen ($A$) und Multiplikationen ($M$) über dem Koeffizientenkörper $\mathbb{F}_q$. Sie leiten rekursive Formeln für die Toom-4-Schritte (Aufspaltung, Auswertung, rekursive Multiplikation, Interpolation und Re-Komposition) ab und integrieren diese in das gewichtete Kostenmodell der unvollständigen NTT, das von Hafiz et al. etabliert wurde.
4. Hybride Analyse: Die Studie analysiert hybride Strategien, die Toom-4, Karatsuba und unvollständige NTT kombinieren. Durch Minimierung der gewichteten Kostenfunktion $C_w(n; \ell, L)$ (wobei $w$ die relativen Kosten von Addition zu Multiplikation sind), bestimmen die Autoren die optimale Rekursionstiefe $L$ für verschiedene Teilproblemgrößen.

Hauptbeiträge

• Explizites Toom-4-Kostenmodell: Die Arbeit liefert das erste explizite Toom-4-Kostenmodell, das mit dem Framework der unvollständigen NTT kompatibel ist. Sie detailliert die exakten Anzahlen von Additionen und Multiplikationen, einschließlich konstanter Faktoren, die aus optimierten Additionsketten abgeleitet wurden.
• Verifikation von Additionsketten: Die Autoren stellen Verifikationsskripte (in ihrem Repository verfügbar) bereit, die die Optimalität der für die Interpolationsskalare verwendeten Additionsketten bestätigen und sicherstellen, dass die abgeleiteten Zahlen für die gewählten Auswertungsstellen minimal sind.
• Optimierung hybrider Strategien: Die Studie identifiziert spezifische Parameterbereiche, in denen eine Toom-4/Karatsuba-Hybridlösung reine Karatsuba- oder reine Toom-4-Ansätze im Kontext der unvollständigen NTT übertrifft.
• Experimentelle Validierung: Die Autoren implementierten die vorgeschlagene hybride Methode in Python und validierten die theoretischen Vorhersagen gegen experimentelle Laufzeiten unter Verwendung von Primzahlmoduln, die für NTT ungünstig sind (ähnlich groß wie der Modul von Dilithium, jedoch mit eingeschränkten 2-adischen Bewertungen).

Ergebnisse
Die Analyse zeigt, dass die Wirksamkeit von Toom-4 in diesem Kontext stark von der zulässigen NTT-Tiefe ($\ell$) und der resultierenden Teilproblemgröße ($d = n/2^\ell$) abhängt:

• Regime begrenzter Tiefe: Wenn die zulässige NTT-Tiefe gering ist (z. B. $\ell=0$ oder $\ell=1$), sind die Teilprobleme groß genug, sodass Toom-4 signifikante Gewinne bietet. Beispielsweise reduzierte die hybride Methode bei $n=256$ und $\ell=0$ die gewichteten Kosten um etwa 5 % im Vergleich zu reiner Karatsuba und übertraf reine Toom-4 deutlich.
• Optimale Rekursion: Die optimale Rekursionstiefe $L$ variiert mit $d$. Für $d \le 128$ ist die optimale Strategie $L=0$ (reine Karatsuba). Für $d=256$ ist $L=1$ optimal, und für $d \ge 512$ ist $L=2$ optimal.
• Experimentelle Bestätigung: Experimente mit Primzahlen mit eingeschränkten 2-adischen Bewertungen bestätigten das theoretische Modell. Wenn die maximal zulässige Tiefe minimal war ($\ell_{max}=0$), übertraf die hybride Methode Karatsuba deutlich (z. B. 14,182 ms vs. 16,722 ms für $n=256$). Mit zunehmender zulässiger Tiefe nahm der Leistungsüberschuss der hybriden Methode ab und konvergierte schließlich mit Karatsuba, wenn die Teilprobleme zu klein wurden.

Bedeutung und Behauptungen
Die Autoren bescheiden behaupten, dass ihr Hauptbeitrag kein neuer Multiplikationsalgorithmus ist, sondern eine präzise Analyse auf Konstantenebene von Toom-4, die auf das Framework der unvollständigen NTT zugeschnitten ist. Sie betonen, dass dieses explizite Kostenmodell eine Lücke in der Literatur schließt und eine systematische Bewertung hybrider Strategien in Szenarien ermöglicht, in denen eine vollständige NTT nicht verfügbar ist.

Die Arbeit kommt zu dem Schluss, dass Toom-4 im „Regime begrenzter Tiefe" der unvollständigen NTT am vorteilhaftesten ist, insbesondere wenn die 2-adische Bewertung von $q-1$ die Transformtiefe einschränkt. In solchen Fällen bietet die vorgeschlagene hybride Strategie eine messbare Leistungsverbesserung gegenüber Standardansätzen auf Karatsuba-Basis. Die Autoren weisen darauf hin, dass ihre aktuelle Implementierung in Python erfolgt ist und zukünftige Arbeiten die Optimierung von Low-Level-Implementierungen (z. B. in C/C++) sowie eine weitere Evaluierung in konkreten gitterbasierten Schemata umfassen werden.