Die zahlentheoretische Transformation (NTT) wird aufgrund ihrer quasilinearen Komplexität allgemein als die effizienteste Methode zur Berechnung von Polynommultiplikationen mit hohen Dimensionen und ganzzahligen Koeffizienten angesehen.
Welche Beziehung besteht zwischen den NTT-Varianten, die durch Aufspalten der ursprünglichen Polynome in Gruppen von Unterpolynomen niedrigeren Grades wie K-NTT, H-NTT und G3-NTT erstellt werden? Können sie als Sonderfälle eines bestimmten Algorithmus unter unterschiedlichen Parametrisierungen betrachtet werden?
Um die Probleme zu lösen, veröffentlichte ein Forschungsteam unter der Leitung von Yunlei Zhao neue Forschung am 15. August 2024 in Grenzen der Informatik.
Das Team schlug die erste verallgemeinerte Splitting-Ring-Zahlentheorie-Transformation vor, die als GSR-NTT bezeichnet wird. Anschließend untersuchten sie die Beziehung zwischen K-NTT, H-NTT und G3-NTT.
In ihrer Forschung untersuchen sie die verallgemeinerte Splitting-Ring-Polynommultiplikation auf der Grundlage der monischen inkrementellen Polynomvarietät und schlagen die erste verallgemeinerte Splitting-Ring-Zahlentheorie-Transformation vor, die als GSR-NTT bezeichnet wird. Sie zeigen, dass K-NTT, H-NTT und G3-NTT unter verschiedenen Parametrisierungen als Sonderfälle von GSR-NTT angesehen werden können.
Sie führen eine prägnante Methodik zur Komplexitätsanalyse ein, auf deren Grundlage GSR-NTT seine optimalen Parametereinstellungen ableiten kann. Sie bieten GSR-NTT weitere Instanziierungen auf der Grundlage zyklischer Faltungspolynome und Dreierpotenz-Zyklotompolynome.
Sie wenden GSR-NTT an, um die Polynommultiplikation im gitterbasierten Schema NTTRU und die einfache Polynommultiplikation über Dreierpotenz-Zyklotom-Polynomringe zu beschleunigen. Die experimentellen Ergebnisse zeigen, dass GSR-NTT für NTTRU Beschleunigungen von 24,7 %, 37,6 % und 28,9 % für die Algorithmen zur Schlüsselgenerierung, Kapselung und Entkapselung erreicht, was zu einer Gesamtbeschleunigung von 29,4 % führt.
Zukünftige Arbeiten können sich auf die Implementierung von GSR-NTT auf weiteren Plattformen konzentrieren.
Weitere Informationen:
Zhichuang Liang et al., Verallgemeinerte Splitting-Ring-Zahlentheorie-Transformation, Grenzen der Informatik (2024). DOI: 10.1007/s11704-024-3288-9
Zur Verfügung gestellt von Frontiers Journals