La transformée théorique des nombres (NTT) est largement reconnue comme la méthode la plus efficace pour calculer la multiplication polynomiale avec des coefficients de dimension et d’intégrale élevés, en raison de sa complexité quasi-linéaire.
Quelle est la relation entre les variantes NTT construites en divisant les polynômes d’origine en groupes de sous-polynômes de degré inférieur, tels que K-NTT, H-NTT et G3-NTT ? Peuvent-ils être considérés comme des cas particuliers d’un certain algorithme sous différentes paramétrisations ?
Pour résoudre les problèmes, une équipe de recherche dirigée par Yunlei Zhao a publié Nouvelle recherche le 15 août 2024 à Les frontières de l’informatique.
L’équipe a proposé la première transformation théorique généralisée des nombres en anneau fractionné, appelée GSR-NTT. Ils ont ensuite étudié la relation entre K-NTT, H-NTT et G3-NTT.
Dans cette recherche, ils étudient la multiplication polynomiale en anneau fractionné généralisée basée sur la variété polynomiale incrémentale monique, et ils proposent la première transformation théorique en anneau fractionné généralisée, appelée GSR-NTT. Ils démontrent que K-NTT, H-NTT et G3-NTT peuvent être considérés comme des cas particuliers de GSR-NTT sous différentes paramétrisations.
Ils introduisent une méthodologie succincte pour l’analyse de la complexité, sur la base de laquelle GSR-NTT peut dériver ses paramètres optimaux. Ils fournissent à GSR-NTT d’autres instanciations basées sur des polynômes basés sur la convolution cyclique et des polynômes cyclotomiques à puissance de trois.
Ils appliquent GSR-NTT pour accélérer la multiplication polynomiale dans le schéma basé sur un réseau appelé NTTRU et la multiplication polynomiale simple sur des anneaux polynomiaux cyclotomiques à puissance de trois. Les résultats expérimentaux montrent que, pour NTTRU, GSR-NTT atteint des accélérations de 24,7 %, 37,6 % et 28,9 % pour les algorithmes de génération de clés, d’encapsulation et de décapsulation, respectivement, conduisant à une accélération totale de 29,4 %.
Les travaux futurs peuvent se concentrer sur la mise en œuvre de GSR-NTT sur davantage de plateformes.
Plus d’informations :
Zhichuang Liang et al., Transformée théorique généralisée des nombres en anneau fractionné, Les frontières de l’informatique (2024). DOI : 10.1007/s11704-024-3288-9
Fourni par Frontiers Journals