Brevet FR3083890A1 — publié le 20200117

PROCESSEUR NTT PAR FLOT DESCRIPTION DOMAINE TECHNIQUE La présente invention concerne le domaine des processeurs NU (Number Theoretic Transform). Elle trouve notamment application dans la cryptographie sur réseau euclidien, en particulier dans la cryptographie homomorphe. ÉTAT DE LA TECHNIQUE ANTÉRIEURE La transformée en nombres entiers ou NU (Number Theoretic Transform) est connue depuis les années 70 et a retrouvé récemment un intérêt dans les applications cryptographiques. On rappelle qu'une transformée en nombres entiers est l'équivalent d'une transformée de Fourier dans un corps de Galois de caractéristique g, G F (g) , la racine primitive d'une transformée de Fourier d'ordre N dans , à savoir e' , étant remplacée par une racine N ème de l'unité du corps G F (g) . Ainsi, N est le plus petit entier non nul tel que = 1. La transformée en nombres entiers d'une séquence a = 0,_1 de N éléments de GF(q) est définie par une séquence A = A, AN_l telle que : A, =antie (1) n=0 où les opérations d'addition et de multiplication sont celles du corps G F (g) . Il convient de noter que y/ n'est pas nécessairement une racine primitive de G r (y) , autrement dit son ordre n'est pas nécessairement égal à l'ordre -1 2 du groupe multiplicatif de GF (g) mais que l'ordre N de est nécessairement un diviseur de q-1. Si N et ci sont premiers entre eux, il existe un inverse N-1 dans le corps de Galois G r (g) et l'on peut définir la transformée en nombres entiers inverse ou 5 INTT (Inverse NTT) par : A-1 (2) les inverses w-n, existant dans la mesure où GF (g) est un corps. 10 Par analogie avec la transformée de Fourier, les éléments yi et apparaissant dans l'expression (1) ou (2) sont dénommés facteurs de rotation. De manière générale, la caractéristique q d'un corps est de la forme = p où p est un nombre premier et in est un entier non nul. Nous considérerons dans la suite les corps finis Gr(q) dont la caractéristique est un 15 nombre premier p , dont on sait qu'ils sont isomorphes à 2,, =Yi p. Une présentation générale de la NU pourra être trouvée dans l'article de J.M. Pollard « The fast Fourier transform in a finite field » publié dans Mathematics of Computation, vol. 25, N° 114, avril 1971, pp. 365-374. La transformée NU est utilisée en arithmétique RNS (Residue Number 20 System) dans le contexte de la cryptographie sur réseau euclidien où elle permet de simplifier considérablement la multiplication de polynômes de degrés élevés et de grands coefficients. En effet, on sait que la multiplication de deux polynômes nécessite de calculer la convolution de la séquence des coefficients du premier polynôme avec la séquence des coefficients du second polynôme. En se plaçant dans l'espace dual, c'est-à-dire après NU, la multiplication des polynômes ne nécessite plus qu'une simple multiplication un à un des coefficients des séquences transformées. Il suffit 3 alors d'effectuer une INTT de la séquence résultante pour obtenir les coefficients de la séquence correspondant au produit des deux polynômes. Cette accélération du calcul polynomial peut s'appliquer à une représentation RNS des polynômes. Plus précisément, si l'on considère un 5 polynôme f (x) x , on peut lui faire correspondre un ensemble L de i=0 polynômes où 4=ûç modp' et r =O. L-1 sont des i =0 entiers premiers entre eux (et généralement premiers) choisis relativement petits. L'ensemble {p',..., p} est dénommé base RNS. Cette représentation des coefficients et, par voie de conséquence, du 10 polynôme associé, est une application immédiate du Théorème des Restes Chinois ou CRT (Chinese Remainders Theorem). On notera dans la suite CRT (a,)= 1)} et CRT(f)=Lf(o) Réciproquement, à une représentation RNS )(x)=Xiii: O,.., L-1 on peut associer un polynôme f = défini N-1 15 par f (x) =>Jaxoù les coefficients ai = IC RT {a,(°) (4L-0} sont donnés par : i=0 7 (3) L \ P .64 mo pe mod P (`) d ,p,, ,1 L-1 et où P = np, est le produit des nombres premiers utilisés pour la décomposition 20 RNS des coefficients. 4 N-I Ainsi, la multiplication de deux polynômes de degré N f(x)=Icpc. et ,=0 N-1 g(x)=L6,x` peut être ramenée par représentation RNS et transformée NU à i=0 N-I N-I N.L multiplications des coefficients Ak( C) = (')4 (Vif et Bk( =113,(1 , k dans l'espace dual où vf, est une N ème racine de l'unité du corps 5 Zp et d') fi(') sont des éléments de Z obtenus par décomposition des , coefficients a, et fi, dans la base RNS Il est ensuite possible de revenir à l'espace de départ au moyen d'une transformée inverse INTT de chaque rtt) A.e) séquence de coefficients 4 =AU) d , k = 0 N -1 pour obtenir les coefficients ( en représentation RNS ,k1F) =N-11'Ce)k yej puis les coefficients du polynôme i=0 10 produit h(x)= f (x)g(x) par ICRT. Etant donné que le degré de h(x) est 2N, on peut considérer d'emblée des polynômes de degré N' =2N (et donc des racines N'ème de l'unité) en bourrant de N zéros (zero pudding) les N coefficients de plus forts degrés de f (x) et g (x) . Moyennant cette convention, on peut rester dans le même espace pour le polynôme produit et les polynômes f (x) et g (ï) à 15 multiplier. On pourra trouver une description détaillée de l'application de la transformée NTT à la multiplication de polynômes en représentation CRT dans l'article de W. Dai et al. intitulé « Accelerating NTRU based homomorphic encryption using GPUs » publié dans Proc. of IEEE High Performance Extreme 20 Computing Conference (HPEC), 2014, 9-11 Sept. 2014. Une multiplication polynomiale utilisant une transformée NU des coefficients de polynômes représentés dans une base RNS requiert de disposer des racines de l'unité des corps finis Z1,, ainsi que de leurs puissances (y)",) , 5 n= 0,...,N-1, tant pour le calcul de la transformée NU des coefficients (en représentation RNS) des polynômes à multiplier que pour le calcul de la transformée INTT des coefficients (en représentation RNS) du polynôme produit dans l'espace dual. 5 Comme pour la FFT (algorithme de Cooley-Tukey), il a été proposé d'implémenter la transformée NU au moyen d'une architecture en pipeline (traitement par flot), chaque étage effectuant une opération (radix) sur un bloc de base de taille R (traditionnellement R=2 ou R=4). L'article de D.B. Cousins et al. intitulé « Designing an FGPA-accelerated homomorphic encryption co- 10 processor » publié dans IEEE Trans. on Emerging Topics in Computing., vol. 5, N°2, avril-juin 2017, pp. 193-206 présente une architecture de processeur NU par flot reprenant une architecture classique radix-2 de FFT. Toutefois, ce processeur NU par flot nécessite de stocker en mémoire locale un nombre important d'ensembles de facteurs de rotation, correspondant 15 aux différents corps finis intervenant dans une représentation RNS. Ces corps finis pouvant différer d'une représentation RNS à une autre, des mémoires ROM de grande taille sont nécessaires. À défaut, on pourrait prévoir de ne stocker que L ensembles de facteurs de rotation correspondant à une représentation RNS spécifique mais alors le processeur NTT n'offrirait alors aucune flexibilité : une 20 reprogrammation des mémoires serait nécessaire dès lors que l'on souhaiterait changer la base de représentation RNS. La présente invention vise à proposer un processeur NU par flot qui offre une grande flexibilité vis-à-vis des bases possibles de représentation RNS sans pour autant nécessiter des ressources importantes en mémoire locale. 25 EXPOSÉ DE L'INVENTION La présente invention est définie par un processeur NU par flot comprenant une pluralité K d'étages de traitement organisés en pipeline, chaque étage comprenant un module de permutation suivi d'un module radix, chaque 6 séquence de données à transformer étant fournie au processeur sous la forme de A7 = N 1W blocs de données successifs de taille W, le résultat de la transformée NU de cette séquence de données étant également fourni sous la forme d'une séquence de Fi blocs de taille W, ledit processeur NU par flot comprenant: 5 une pluralité (G +1 ) de bancs de mémoires, chaque banc de mémoire étant associée à une transformée NU de taille N sur un corps donné ( ) et comprenant K mémoires (MEM:, k =0 K-1) respectivement associées aux K étages de traitement, chaque mémoire étant destinée à stocker un jeu de facteurs de rotation pour pa ra métrer un étage de traitement ; 10 un module de gestion d'écriture pour recevoir, sous forme d'une séquence de blocs successifs de taille W, un ensemble (p4 de facteurs de rotation constitué de K jeux de facteurs de rotation (kI, k = 0,...,K -1), et écrire ces jeux de facteurs de rotation dans les mémoires respectives d'un banc de mémoires, l'écriture étant effectuée de manière cyclique dans les bancs de mémoires, chaque 15 nouvel ensemble de facteurs de rotation étant écrit dans un nouveau banc de mémoire ; - un module de gestion de lecture pour lire les jeux de facteurs de rotation au sein des mémoires (ME/1f) d'un banc de mémoires du processeur et à paramétrer les étages de traitement au rythme de la progression des blocs de 20 données à travers les étages de traitement ; - un module de contrôle pour contrôler le module de gestion d'écriture, le module de gestion de lecture ainsi que la progression des blocs de données à travers les étages de traitement. Ledit processeur NU par flot peut comprendre G +1 bancs de mémoires 25 où G =rLat _NTT Lat NTT étant la latence de traitement du processeur NU et T=N1W est le débit de séquences de données en entrée du processeur NU, chaque banc de mémoire étant associé à la transformée d'une séquence de données et contenant les jeux de facteurs de rotation des étages successifs pour la transformée NU de cette séquence. Avantageusement, avant qu'une séquence de données ne passe d'un premier étage de traitement à un second étage de traitement, le module de 5 contrôle commande la lecture du jeu de facteurs de rotation dans la mémoire correspondante associé à ce second étage au sein du banc de mémoires associé à cette séquence, ainsi que la programmation du second étage à l'aide du jeu de facteurs de rotation ainsi lu. Le module de contrôle comporte de préférence un compteur de bancs de 10 mémoire, incrémenté à chaque fois qu'un nouvel ensemble de facteurs de rotation est fourni au module de gestion d'écriture et remis à zéro après avoir atteint la valeur G , la sortie dudit compteur étant comparée à une pluralité de comparateurs être comparée aux valeurs g G , les sorties respectives de ces comparateurs fournissant +1 signaux de sélection autorisant 15 respectivement une commande d'écriture dans chacun des bancs de mémoires. Chaque banc de mémoires associé à la transformation NU d'une séquence peut comprendre en outre un registre dans lequel est stockée la caractéristique ( p, ) du corps ( ) dans lequel est effectuée la transformée NU, la caractéristique du corps étant transmise à un étage de traitement en même 20 temps que les facteurs de rotation lus dans la mémoire associée à cet étage, au sein dudit banc de mémoires. Typiquement, les caractéristiques des corps dans lesquels sont effectuées L transformées NU de L séquences de données successives sont distincts, où LG 25 BRÈVE DESCRIPTION DES DESSINS D'autres caractéristiques et avantages de l'invention apparaîtront à la lecture d'un mode de réalisation préférentiel de l'invention, décrit en référence aux figures jointes parmi lesquelles : 5 La Fig. 1 représente de manière schématique l'architecture d'un processeur NU par flot ; La Fig. 2 représente de manière schématique l'architecture de processeur NU par flot selon un mode de réalisation de l'invention ; La Fig. 3 représente de manière schématique une opération d'écriture 10 dans un banc de mémoires de la Fig. 2; La Fig. 4 représente de manière schématique le fonctionnement de l'interface d'écriture au sein du processeur NU de la Fig. 2; La Fig. 5 représente de manière schématique une opération de lecture dans les bancs de mémoires de la Fig. 2; 15 La Fig. 6 représente de manière schématique un chronogramme des signaux de contrôle dans le processeur NU de la Fig. 2. EXPOSÉ DÉTAILLÉ DE MODES DE RÉALISATION PARTICULIERS Un processeur NU par flot comprend essentiellement une pluralité 20 d'étages de calcul, chaque étage comprenant un module de permutation adapté à effectuer une opération de permutation et un module de combinaison adapté à effectuer une opération de combinaison (radix-R butterfly) de R nombres entiers au moyen de facteurs de rotation (twiddle factors) appartenant à un corps Z = Z/ pZ de caractéristique p . 25 8 La Fig. 1 illustre de manière schématique l'architecture d'un processeur NU par flot. 9 Les données d'entrée sont des entiers relatifs (éléments de Z ) et sont fournis par blocs de taille W au processeur NU, 100. En d'autres termes, W est la largeur du chemin de données. Ainsi, si N (ou le nombre de points) est la taille de la transformée NU, et si un bloc est fourni au processeur à chaque cycle 5 d'horloge, l'intégralité d'une séquence de N éléments, encore dénommée dans la suite N-séquence, sera reçue au bout du temps T =N /W (comptabilisé en nombre de cycles), autrement dit le débit (des séquences de données) d'entrée est de NIW Le processeur NU comporte une pluralité K d'étages de traitement, 10 noo,...,nchu arrangés en pipeline, 110, chaque étage 110k comprenant un module de permutation 113k, suivi d'un module de combinaison, 115k , effectuant une opération de combinaison de R entiers fournis par le module de permutation 113k au moyen de NI RK-1`-' facteurs de rotation (dans le cas d'une implémentation par décimation temporelle) ou Ri' (dans le cas d'une 15 implémentation par décimation fréquentielle). Ainsi chaque étage est paramétré par un jeu de facteur de rotation associé. Dans la suite de la présentation, nous supposerons par souci de simplification et sans perte de généralité que R =W W. En outre, la taille (ou nombre de points) N de la transformée NU est reliée au nombre d'étages du processeur 20 par K log R(N )- Chaque module de permutation comprend des commutateurs et des retards (buffers FIFO) de manière à présenter simultanément les R entiers à combiner au module de combinaison suivant. L'architecture de ces modules de permutation a été décrite par exemple dans le brevet US-B-8321823 incorporé ici 25 par référence. Les modules de combinaison effectuent les opérations radix- R (comme pour une FFT) à raide des facteurs de rotation qui leur sont fournis, les calculs étant effectués dans le corps Zp. 10 Le débit à travers chaque étage du processeur NTT, c'est-à-dire le temps au bout duquel est traité une N-séquence de données par cet étage, est égal à T de manière à permettre une opération par flot. Les N-séquences de données étant fournies au processeur NTT avec un 5 débit T=N1W, le nombre maximum de N-séquences présentes à tout moment dans le processeur est G =r Lat _NT7' 1T1 où Lai _NTT est la latence de traitement du processeur NTT exprimé en nombre de cycles d'horloge. L'architecture du processeur NTT par flot selon la présente invention permet d'effectuer en pipeline des transformée NTT sur LG corps distincts, ce 10 qui est particulièrement avantageux lorsque l'on doit effectuer des opérations en représentation RNS. L'idée à la base de la présente invention est de permettre à chaque étage k = 0,...,K du processeur NU d'accéder au jeu de facteur de rotation kg associé à cet étage et à la N-séquence de données actuellement traitée par cet étage, 15 lesdits facteurs de rotation appartenant à Ir = {(vf,)", n = 0 N -11 où =1,. . L les transformées NTT sur les différents corps Zp, se déroulant simultanément sur des blocs de données au sein des étages successifs du processeur, l'accès des différents étages aux ensembles 3/411k étant réalisé de manière synchrone avec la progression des N-séquences de données d'un étage au 20 suivant. La Fig. 2 représente de manière schématique une architecture de processeur NTT par flot selon un mode de réalisation de l'invention. Le processeur NTT comprend un module de contrôle 250, une pluralité K 25 d'étages de traitement, 2100,...,210K 1, arrangés en pipeline, 210, ces étages de traitement ayant la structure précédemment décrite en relation avec la Fig. 1. Les N-séquences de données sur lesquelles sont effectuées les NU entrent par le 11 premier étage 2100 sous forme d'une série de blocs de taille W avec un débit T=NIW (i.e. une N-séquence par intervalle de temps T ) et le résultat de chaque NU est fourni par le dernier étage, 210k, sous forme d'un série de blocs de taille W, avec le même débit. Il est important de noter que la taille est commune à 5 toutes les NU effectuées par le processeur, quels que soient les corps dans lesquels elles sont calculées. Les différents étages sont programmés à l'aide de G+1 bancs de mémoires 2200 ..... 220G. Chaque banc de mémoires, 220 g , comprend K mémoires, MEM: , d'indice k =0,...,K -1, chaque mémoire ME14: contenant le 10 jeu de facteurs de rotation le nécessaire au paramétrage (autrement dit à la programmation) de l'étage 210k correspondant lorsque celui-ci est destiné à opérer dans le corps 'Lm.. En outre, le banc de mémoires 220g stocke dans un registre (non représenté) la caractéristique p, du corps dans lequel les opérations de combinaison seront effectuées. Cette caractéristique est également fournie à 15 l'étage 210k de manière à ce que le module de combinaison de cet étage puisse effectuer les opérations (multiplication par un facteur de rotation, addition, soustraction) modulo p, . À chaque instant, un étage d'indice k donné accède à un unique banc de mémoires. Il convient de noter que les contenus des différents bancs de mémoires 20 peuvent être différents ou identiques, selon que les transformées de NU successives sont effectuées sur des corps différents ou identiques. Il est important de comprendre que chaque banc de mémoires est associé à une séquence de V = N 11,V blocs de données (de taille W) qui chemine à travers les étages successifs du processeur NU pour fournir une transformée NU dans un corps 25 . Lorsque ces ATT blocs passent dans un étage 210k, cet étage aura précédemment accédé à la mémoire d'indice k du banc 220 contenant le jeu de g facteurs de rotation Wk, pour être paramétré par ce jeu. Les V blocs suivants 12 pourront faire l'objet d'une transformée dans le même corps ZP ou dans un corps , différent Z . Dans le premier cas, le banc de mémoires 220g (si l'on suppose que g REVENDICATIONS1. Processeur NU par flot comprenant une pluralité K d'étages de traitement (210'k 0,...,K -1) organisés en pipeline (210), chaque étage comprenant un module de permutation suivi d'un module radix, chaque séquence de données à transformer étant fournie au processeur sous la forme de ITV blocs de données successifs de taille W, le résultat de la transformée NU de cette séquence de données étant également fourni sous la forme d'une séquence de I7 blocs de taille W, caractérisé en ce qu'il comprend : une pluralité ( G +1) de bancs de mémoires ( 220g , g = G ) , chaque banc de mémoire (220g ) étant associée à une transformée WU de taille N sur un corps donné ( v- ) et comprenant K mémoires ( MEM , k = 0 K-1 ) , respectivement associées aux K étages de traitement (210, ,k =0,...,K-1) chaque mémoire étant destinée à stocker un jeu de facteurs de rotation pour para métrer un étage de traitement ; un module de gestion d'écriture (270) pour recevoir, sous forme d'une séquence de blocs successifs de taille W, un ensemble (y.) de facteurs de rotation constitué de K jeux de facteurs de rotation ('Iik, K -1), et écrire ces jeux de facteurs de rotation dans les mémoires respectives d'un banc de mémoires, l'écriture étant effectuée de manière cyclique dans les bancs de mémoires, chaque nouvel ensemble de facteurs de rotation étant écrit dans un nouveau banc de mémoire ; un module de gestion de lecture (260) pour lire les jeux de facteurs de rotation au sein des mémoires (M047, ) d'un banc de mémoires (22O ) du processeur et à paramétrer les étages de traitement (210, ) au rythme de la progression des blocs de données à travers les étages de traitement ; 20 un module de contrôle (250) pour contrôler le module de gestion d'écriture (270), le module de gestion de lecture (260) ainsi que la progression des blocs de données à travers les étages de traitement. 5 2. Processeur NU par flot selon la revendication 1, caractérisé en ce qu'il comprend G +1 bancs de mémoires où G Lat _NTT / Tl, Lat _ NTT étant la latence de traitement du processeur NU et T = ATIV17 est le débit de séquences de données en entrée du processeur NU, chaque banc de mémoire étant associé à la transformée d'une séquence de données et contenant les jeux 10 de facteurs de rotation des étages successifs pour la transformée NU de cette séquence. 3. Processeur NU par flot selon la revendication 2, caractérisé en ce qu'avant qu'une séquence de données ne passe d'un premier étage de traitement 15 à un second étage de traitement, le module de contrôle (250) commande la lecture du jeu de facteurs de rotation dans la mémoire correspondante associé à ce second étage au sein du banc de mémoires associé à cette séquence, ainsi que la programmation du second étage à l'aide du jeu de facteurs de rotation ainsi lu. 20 4. Processeur NU par flot selon la revendication 2 ou 3, caractérisé en ce que le module de contrôle (250) comporte un compteur de bancs de mémoire (430), incrémenté à chaque fois qu'un nouvel ensemble de facteurs de rotation est fourni au module de gestion d'écriture (270) et remis à zéro après avoir atteint la valeur G , la sortie dudit compteur étant comparée à une pluralité de 25 comparateurs être comparée aux valeurs g = 0,G , les sorties respectives de ces comparateurs fournissant G+1 signaux de sélection autorisant respectivement une commande d'écriture dans chacun des bancs de mémoires. 21 5. Processeur NU par flot selon la revendication 4, caractérisé en ce que chaque banc de mémoires associé à la transformation NU d'une séquence comprend en outre un registre dans lequel est stockée la caractéristique ( p, ) du corps (Zet ) dans lequel est effectuée la transformée NU, la caractéristique du 5 corps étant transmise à un étage de traitement en même temps que les facteurs de rotation lus dans la mémoire associée à cet étage, au sein dudit banc de mémoires. 6. Processeur NU par flot selon la revendication 5, caractérisé en ce 10 que les caractéristiques des corps dans lesquels sont effectuées L transformées NU de L séquences de données successives sont distincts, où