La cryptographie à clé publique est réputée pour le surcoût important engendré tant au niveau de l'implémentation (calculs sur les grands nombres, manipulation de points dans une courbe elliptique, etc.) qu'au niveau calculatoire. Un des principaux usages de la cryptographie à clé publique est l'échange de clés lors de la mise en place d'une communication sécurisée (par exemple pour une connexion TLS). Cette opération, gourmande en temps de calcul, permet au mieux (en utilisant ECDH avec un Core i7-4770) de gérer de l'ordre de vingt mille connexions entrantes par seconde à 128 bits de sécurité ou six mille connexions à 256 bits de sécurité.
La cryptographie basée sur les réseaux est entrée en scène en force depuis quelques années, en particulier grâce aux fonctionnalités avancées, de type chi rement complètement homomorphe, qu'elle permet d'atteindre. Notre bibliothèque, NFLlib, permet d'implémenter simplement des algorithmes cryptographiques basés sur les réseaux euclidiens, le tout avec des performances supérieures à l'état de l'art connu. Pour illustrer cela, nous implémentons, en une dizaine de lignes de code, un système de chi rement standard avec une estimation conservatrice du niveau de sécurité. Cette implémentation permet de gérer quatre millions d'échanges de clés de type TLS par seconde à 128 bits de sécurité et deux millions à 256 bits de sécurité.
Si nous partons sur un proxy web utilisé pour du partage de charge et pouvant gérer les connexions TLS, il est possible de traiter jusqu'à 70 000 requêtes par seconde 1 sur un unique serveur. L'utilisation de ECDH demandera trois Core i7-4770 à 100% rien que pour les échanges de clés, alors que notre bibliothèque permet d'utiliser uniquement 2% d'un unique CPU libérant ainsi les processeurs pour traiter les requêtes.
Depuis le début des années 90, une branche de la complexité est entrée avec force dans le monde de la cryptographie : la complexité des problèmes algorithmiques dans les réseaux euclidiens. Cette branche a donné naissance à ce qu'on appelle de nos jours la cryptographie basée sur les réseaux (lattice-based cryptography en anglais).
Ce domaine est de plus en plus présent dans les conférences en cryptographie pour plusieurs raisons :
Dans cet article nous nous intéressons aux performances pratiques de la cryptographie basée sur les réseaux.
Un comportement asymptotique, aussi excellent soit-il, n'est pas garant d'une supériorité lors d'une utilisation pratique. Un bon exemple est la multiplication basée sur la transformée de Fourrier qui a un coût quasi linéaire en la taille n d'un nombre (proportionnel à nlog n) mais dont le coût de base est important de telle façon que cet algorithme n'est intéressant que quand les nombres sont très grands (milliers ou dizaines de milliers de bits).
Dans cet article nous présentons NFLlib, une bibliothèque permettant de développer facilement des algorithmes de cryptographie basée sur les réseaux euclidiens, le tout avec d'excellents résultats au niveau des performances. Cette bibliothèque permet de faire abstraction des objets sous-jacents dans les réseaux (des polynômes) et de juste décrire les opérations à réaliser (par exemple générer un élément aléatoire, multiplier celui-ci par un autre élément, etc.). Nous présentons également une étude de performances comparative dans le cadre des échanges de clés.
Une version primitive de NFLlib est présente dans le projet XPIRe [1] (comme un sous-module). XPIRe est une bibliothèque C++ disponible 2 sur GitHub, permettant de réaliser du téléchargement privé (i.e. de télécharger un élément d'une base de données sans que le serveur contenant la base sache quel élément a été téléchargé) à haute vitesse. La comparaison à ce module initial est donnée en section 1.2.
Il existe di érentes bibliothèques génériques permettant de dé nir les polynômes utilisés dans les réseaux et de réaliser les opérations de base nécessaires aux algorithmes cryptographiques. Parmi ces bibliothèques, celles permettant d'obtenir les plus hautes performances sont NTL [18] et FLINT [12]. Nous comparons dans cet article certaines fonctions de base pour montrer que les performances obtenues dans NFLlib sont très supérieures. Ceci est relativement normal puisque NTL et FLINT sont des bibliothèques génériques permettant de réaliser des calculs dans des contextes variés alors que notre bibliothèque est fortement optimisée pour un type de polynômes précis et uniquement pour une utilisation en cryptographie.
Dans le domaine de la cryptographie basée sur les réseaux, la bibliothèque HElib [11] propose une implémentation d'un système du chi rement complètement homomorphe décrit dans [4]. Le pari de cette bibliothèque est de partir de NTL, de l'utiliser de manière optimisée et en pro tant des nombreux algorithmes implémentés. La sélection des paramètres étant automatisée par HElib, et le schéma utilisé beaucoup plus compliqué qu'un simple schéma de chi rement classique (ce dernier étant complètement homomorphe, il rend possible d'opérer publiquement sur des données chi rées), la comparaison avec cette bibliothèque n'est pas signi catif. Nous nous comparerons néanmoins, en section 3.2, avec une implémentation basée sur NTL qui permet d'obtenir une estimation du gain en performances que pourrait apporter la bibliothèque NFLlib pour HElib.
En n, un article, disponible dans les archives de l'IACR [3], présente un protocole permettant de faire un échange de clés basé sur les réseaux euclidiens, avec des propriétés de sécurité telles que la perfect forward secrecy ou la résistance aux analyses temporelles. Les auteurs développent un module intégré dans OpenSSL qui leur permet de réaliser des échanges de clés de type TLS en atteignant le nombre de requêtes par seconde similaire aux protocoles classiques. Dans cet article nous présentons une preuve de concept et non un module complètement intégré dans OpenSSL, et nous n'étudions pas la sécurité de l'implémentation elle-même. En revanche, nous pouvons réaliser environ mille fois plus d'opérations par seconde que dans cet article. Au vu de cet écart, il nous semble raisonnable de penser que les performances qu'ils présentent pourraient signi cativement s'améliorer par l'utilisation de NFLlib.
La version de NFLlib que nous présentons dans cet article est beaucoup plus évoluée que celle incluse dans XPIRe. Les principales modi cations que nous introduisons dans cette bibliothèque par rapport au sous-module d'XPIRe sont :
Ces modi cations permettent d'augmenter grandement la polyvalence de la bibliothèque (en permettant de traiter e cacement les tout petits et les très grands polynômes). Nous comparons dans cet article les performances avec et sans plusieurs des modi cations introduites pour montrer l'évolution positive que ces modi cations apportent.
La deuxième contribution de cette bibliothèque est sa facilité d'utilisation à travers la surcharge d'opérateurs, sans que cela n'ait d'impact signi catif sur les performances, grâce à plusieurs techniques de méta-programmation.
La troisième contribution est propre à l'article en soit. Nous montrons que la cryptographie basée sur les réseaux permet d'atteindre des performances très supérieures à la cryptographie classique pour l'échange de clés. Ceci est déjà vrai pour un niveau de sécurité basique (128 bits de sécurité) et la di érence de performance explose pour les niveaux de sécurité les plus élevés. Nous montrons ainsi qu'il est possible de passer d'une gestion de quelques milliers de connexions de type TLS par seconde dans un serveur classique à des millions.
La suite de l'article est structurée de la façon suivante : la section 2 introduit les bases théoriques sur lesquelles repose notre approche et décrit l'algorithme de chi rement que nous utiliserons pour faire les échanges de clés ; la section 3 décrit les performances atteintes et les compare avec l'existant ; en n, la section 4 détaille les choix de conceptions et les optimisations qui ont permis d'atteindre des performances élevées en conservant une API simple.
D'un point de vue purement mathématique, les réseaux euclidiens sont les sous-groupes discrets de Rn . Ici, nous nous intéressons à une famille importante des réseaux, appelée les réseaux d'idéaux. À nouveau, d'un point de vue purement mathématique, il s'agit des réseaux en bijection avec les anneaux d'entiers du corps des nombres . En pratique, quand nous implémentons les algorithmes de la cryptographie basée sur les réseaux, nous n'avons pas du tout besoin d'appréhender ces concepts mathématiques et nous manipulons tout simplement des polynômes sur les entiers.
Ainsi, les objets que nous manipulons sont des polynômes du type :
a Xi. Typiquement, n est une puissance de deux supérieure ou
égale à 256 et le module utilisé pour les coe cients est un nombre
allant d'une dizaine de bits (pour les échanges de clés ou les signatures
numériques [6]) à plusieurs milliers de bits (pour le chi rement complètement
homomorphe [4]).
Algorithmiquement, un polynôme est stocké comme un tableau P de taille n où P[i] contient le coe cient de Xi dans le polynôme.
L'addition de polynômes se fait en additionnant les coe cients modulo
q. La multiplication de deux polynômes est un peu plus compliquée
puisqu'il faut multiplier tous les termes deux à deux, ce qui a un coût
quadratique en n, puis réduire les coe cients avec un degré supérieur
ou égal à n en les translatant et inversant le signe (avec l'opération
a Xn+i
a Xi).
Dans NFLlib deux techniques, changeant la représentation, permettent de réduire les coûts calculatoires : la représentation des polynômes par NTT (Number-Theoretic Transform, un cas particulier de FFT) et la représentation des coe cients par CRT (Chinese Remainder Theorem, Théorème des restes chinois). Une troisième technique permet d'accélérer les réductions modulaires, dans le cas où on travaille avec des entiers de 64 bits, en précalculant des quotients de certaines valeurs par les modules (pour 32 et 16 bits GCC le fait automatiquement). Cette technique est décrite dans [1], et le lecteur est renvoyé sur ce papier pour les détails. Quand une multiplication modulaire fait appel à de tels précalculs on parlera de multiplication modulaire de Shoup, ou de multiplication faisant appel à une représentation de Shoup.
Comme la FFT, la NTT transforme un vecteur de coe cients représentant un polynôme en un autre vecteur qui représente l'évaluation du polynôme en des points particuliers. Nous appelons ce vecteur de valeurs la représentation NTT du polynôme. La principale di érence entre la FFT et la NTT est la façon dont les points d'évaluation sont choisis, mais nous n'entrerons pas dans ces détails.
Quand les polynômes sont représentés par de tels vecteurs de valeurs, la multiplication des polynômes se fait coordonnée par coordonnée, et donc en une complexité linéaire en n. En e et, si à un des points d'évaluation, un polynôme f vaut a et un polynôme g vaut b, alors le produit des deux polynômes vaudra a b (modulo q) et ceci est vrai pour chaque coordonnée des vecteurs décrivant les évaluations.
Transformer un polynôme en forme NTT ou faire la transformation inverse (permettant de passer d'un vecteur de valeurs à un vecteur de coe cients du polynôme) a un coût proportionnel à nlog n.
Le lecteur attentif remarquera que, dans les réseaux, nous avons besoin de
multiplier les polynômes et de les réduire modulo Xn + 1 (i.e. réaliser la
transposition a Xn+i
a Xi). En pratique, cela se fait automatiquement
si un prétraitement est réalisé sur les vecteurs avant d'appliquer la
NTT puis un autre avant d'appliquer la NTT inverse. Ces traitements
correspondent à une multiplication par une valeur particulière pour chaque
coordonnée.
Comme présenté dans la section 2.1, les polynômes que nous devons manipuler sont dé nis par le degré maximum n 1 et par le module q utilisé pour les coe cients. En utilisant une représentation de type NTT, nous avons la garantie que toutes les opérations sur les polynômes ont un coût linéaire en n (additions, soustractions, multiplications), ou quasi-linéaire (application de la NTT ou de la NTT inverse).
En revanche, sans autre technique, le coût des opérations peut augmenter rapidement en log q, le nombre de bits de q. Les additions et soustractions ont un coût linéaire en log q, mais les multiplications et les divisions (nécessaires pour la réduction modulaire) ont un coût quadratique en log q. Ainsi, si pour un module de 64 bits, une multiplication s'appuiera sur les multiplicateurs hardware et ne prendra (en pipeline) qu'un cycle d'horloge, pour un module de 6400 bits cette opération prendra des dizaines de milliers de cycles.
Pour éviter ce problème, le module que nous utilisons est le produit d'une série de nombres premiers, tous stockés sur des entiers de même taille. Dans un premier temps, l'utilisateur doit choisir une taille d'entier non signé sur laquelle travailler (16, 32 ou 64 bits). Ceci impose que le module soit le produit d'une série de nombres premiers, chacun de taille égale à la taille des entiers choisis moins deux bits (i.e. 14, 30 ou 62 bits). En n, l'utilisateur doit choisir combien de nombres premiers il veut utiliser pour atteindre une taille de module qui lui convienne. Ainsi, par exemple, un utilisateur peut choisir d'utiliser des entiers de 64 bits et 100 premiers, ce qui donnera un module de 6200 bits, ou des entiers de 16 bits et un unique premier ce qui donnera un module de 14 bits.
Cette approche permet de réaliser les calculs e cacement en utilisant le
théorème des restes chinois. Celui-ci dit que, si q = p1 
pt, il est
possible de transformer les nombres modulo q en des séries de t nombres
modulo chacun des petits nombres premiers (cette transformation est appelée
CRT), de réaliser les calculs sur les petits nombres, et de transformer les
résultats naux en un nombre modulo q (CRT inverse). En pratique, au lieu
de réaliser les calculs sur un polynôme en travaillant modulo q sur
les coe cients il est possible de travailler sur t polynômes avec des
coe cients modulo p1 pour le premier, modulo p2 pour le deuxième,
etc.
Grâce à cette technique, si q fait 6200 bits, on travaillera avec 100 polynômes pour faire les opérations (addition, soustraction, multiplication et division) et le coût ne sera que 100 fois plus grand que si on travaillait avec un module de 62 bits. Les coûts augmentent donc linéairement en log q pour la multiplication et la division et pas en log 2q comme ce serait le cas si on n'utilisait pas le théorème des restes chinois.
Le passage d'un nombre modulo q vers la représentation CRT a lui aussi un coût linéaire en log q (cela consiste tout simplement à prendre le reste du nombre modulo chacun des premiers indépendamment). L'opération inverse, en revanche, à un coût en quadratique en log q. De façon générale, quand on crée un polynôme on le stocke directement sous forme NTT et CRT, et on n'applique les opérations de NTT inverse et CRT inverse qu'à la n des opérations, quand cela est nécessaire.
Les standards dé nissant comment faire un échange de clés sont, comme à l'habitude en cryptographie, nombreux. D'un côté, il y a bien sûr les standards du NIST et de l'ANSI : NIST SP 800-56A (pour la cryptographie basée sur le logarithme discret), NIST SP 800-56B (pour la cryptographie basée sur la factorisation), et ANSI X9.24 (considéré obsolète). De l'autre, il y a les RFC de l'IETF correspondant aux principaux protocoles utilisés de nos jours sur Internet : RFC 2409 et RFC 5996 pour IKEv2, et RFC 5246 pour TLS v1.2.
Dans ce document, nous utilisons l'équivalent de l'échange de clés par RSA dans TLS, ou par RSASVE dans NIST SP 800 56B, en remplaçant RSA par notre fonction de chi rement. Le client choisit un message complètement aléatoire et le chi re avec la clé publique du serveur, et le serveur déchi re cette valeur qui sera ensuite utilisée pour dériver (par une fonction de hachage) un secret commun.
Pour illustrer le type de calculs à réaliser dans le système de chi rement utilisé, nous décrivons ici ses sous-fonctions. Ce système est décrit dans [15] et nous orientons le lecteur vers ce papier pour les démonstrations de sécurité et de justesse du déchi rement. Nous utilisons de façon opaque une fonction décrite dans [15], GaussianPoly, qui génère un polynôme avec des coe cients suivant une distribution de type gaussien pour un écart type adapté au paramètre de sécurité. UniformPoly retourne un polynôme avec des coe cients choisis uniformément entre 0 et q 1.
Dans un premier temps, voici la fonction pour la génération de clés. 3
__________________________________________________________________
Génération de clés : KeyGen( )
Entrées :
- Un paramètre de sécurité k
Sortie : Une paire de clés (pk;sk)
__________________________________________________________________
Pour simpli er le code et donner une idée des paramètres utilisés, nous avons explicité les sorties pour k = 128 et k = 256 et rendu les autres paramétrages impossibles. Une fois la paire de clés générée, il est possible de chi rer/déchi rer avec les fonctions suivantes.
__________________________________________________________________
Chi rement : Enc(pk;m)
Entrées :
- Une clé publique pk obtenue par KeyGen
- Un message m (polynôme à coe cients binaires) à chi rer
Sortie : Un chi ré
Déchi rement : Dec(sk; )
Entrées :
- Une clé secrète sk issue de KeyGen
- Un chi ré = ( 1; 2) issu de Enc
Sortie : Un message en clair m
__________________________________________________________________
L'objectif de ce schéma étant de transporter une clé, on choisit les plus petites valeurs de log q et n permettant d'atteindre la sécurité demandée. Ainsi les opérations entre coe cients seront très peu coûteuses, mais pour les optimiser il faudra faire attention à la vectorisation du code. Au niveau des opérations entre polynômes, les multiplications de type pka u, pkb u, et 1 sk seraient très coûteuses (millions d'opérations) sans améliorations. Transformer les opérandes par la NTT permettra de réduire fortement les coûts. La NTT inverse ne sera faite qu'avant la dernière étape du déchi rement où un travail par coe cient est nécessaire. Ainsi :
Ces opérations permettent de remplacer le coût des multiplications (millions d'opérations) par le coût des NTTs (milliers d'opérations) et multiplications par coordonnées (milliers d'opérations). Nous appelons notre implémentation de ce système NFLLWE.
Il est important de remarquer que le schéma cryptographique que nous proposons est un schéma standard [15] et qu'en aucun cas les résultats de performance annoncés ne viennent de choix de paramètres audacieux ou d'un choix d'une sous-famille exotique de réseaux.
Dans les réseaux il y a plusieurs problèmes standards réputés infaisables en un temps raisonnable. Au niveau des fonctions de type chi rement les deux grands problèmes sont Learning With Errors (LWE) et Ring Learning With Errors (RLWE). Ces problèmes s'appuient sur d'autres problèmes plus profonds venant de la complexité (trouver un ou des vecteurs courts dans des réseaux) mais nous n'entrerons pas dans les détails, le lecteur voulant approfondir ces questions peut lire l'excellent article de Regev sur le sujet [16].
Le système de chi rement que nous présentons a une sécurité basée sur la di culté du problème RLWE. Le choix des paramètres se fait par rapport aux meilleures attaques connues. Il est important de remarquer que les algorithmes permettant d'attaquer ce genre de systèmes (notamment LLL [13], BKZ [17] et BKZ-2.0 [5]), ont aussi un grand intérêt dans d'autres domaines que la cryptographie, et sont étudiés depuis plusieurs dizaines d'années.
Les paramètres que nous utilisons en section 3 sont obtenus en utilisant l'algorithme de choix de paramètres de [14], connu pour être assez conservateur. Notons que si ces choix ne se montraient pas su samment conservateurs, il su rait de doubler la sécurité, ce qui ne donnerait qu'une augmentation d'un facteur deux des coûts.
Dans cette section nous présentons les performances que notre bibliothèque permet d'atteindre. Tout d'abord, nous comparons NFLLWE aux primitives classiques de la cryptographie et nous montrons qu'il existe un écart très important de performances (facteur supérieur à 200). Dans un deuxième temps, nous comparons NFLLWE avec l'implémentation qu'on obtient en utilisant d'autres bibliothèques comme NTL et FLINT. Nous montrons ainsi que le gain en performance découle de l'utilisation des réseaux (facteur 10 par rapport aux bibliothèques alternatives) mais surtout des optimisations de notre bibliothèque (facteur 20 par rapport aux implémentations NTL ou FLINT)
La cryptographie classique, basée sur la factorisation ou sur le logarithme discret, a deux problèmes par rapport à la cryptographie basée sur les réseaux : une coût pour les niveaux de sécurité basiques relativement élevé et une mauvaise mise à l'échelle quand la sécurité augmente.
Au niveau de l'évolution des coûts, le tableau 1 montre les paramétrages pour 128 bits de sécurité et pour 256 bits de sécurité pour des échanges de clés basés sur : RSA, DH (Di e-Hellman sur des entiers), ECDH (Di e-Hellman sur les courbes elliptiques), et NFLLWE notre implémentation basée sur RLWE.
| Protocole | Paramètres | Paramètres | Surcoût |
| pour 128 bits | pour 256 bits | calculatoire | |
| RSA | 3072 | 15360 | 125 |
| DH | 256=3072 | 512=15360 | 50 |
| ECDH | 256 | 521 | 8 |
| NFLLWE | 14=256 | 14=512 | 2 |
Comme c'est bien connu, RSA est le moins bon élève pour la mise à l'échelle au niveau de la sécurité. Ceci à d'ailleurs été le principal argument qui a propulsé les courbes elliptiques au devant de la scène. DH et surtout ECDH font mieux mais on voit qu'il n'y a pas un rapport linéaire (mais au moins cubique) entre l'augmentation au niveau de la sécurité et l'augmentation des coûts théoriques.
Ceci a une importance signi cative au niveau de la crédibilité de la résistance à de nouvelles attaques. Si un jour un nouvel algorithme ou une nouvelle technologie (par exemple l'ordinateur quantique) permet de diviser par dix la sécurité d'un système basé sur les réseaux, il su ra d'augmenter les paramètres linéairement et les performances seront divisées par dix. Ceci nous laisserait encore 400 000 échanges de clés par seconde, 20 fois plus qu'avec ECDH. Si ECDH subissait la même attaque les coûts augmenteraient d'un facteur 1000 et pour RSA ça serait encore pire.
| Protocole | 80bits | 128 bits | 256 bits |
| RSA | 7:95 Kops/s | 0:31 Kops/s | N/D |
| ECDH | 7:01 Kops/s | 5:93 Kops/s | 1:61 Kops/s |
| NFLLWE | N/D | 1020 Kops/s | 508 Kops/s |
Le tableau 2 montre les performances des di érents protocoles pour 80, 128 et 256 bits de sécurité. Dans RSA et NFLLWE l'opération que doit réaliser le serveur est un déchi rement, dans ECDH c'est l'opération de base de Di e-Hellman, une exponentiation modulaire. NFLLWE permet de traiter plus de clients ou d'utiliser moins de temps processeur pour un même nombre de clients. L'écart est d'au moins un facteur 200, ce qui permet de gagner sur tous les plans. Par exemple il est possible de traiter 10 fois plus de clients avec 10 fois moins de temps processeur et en doublant la sécurité par rapport à ECDH à 128 bits de sécurité.
Comme mentionné en introduction, les bibliothèques NTL [18] et FLINT [12] permettent de manipuler aisément les polynômes utilisés en cryptographie basée sur les réseaux. Ces bibliothèques sont génériques : elles peuvent donc être utilisées pour manipuler des polynômes de degrés arbitraires, modulo des entiers arbitraires. Inversement, on rappelle que la bibliothèque NFLlib se restreint volontairement à des polynômes de degré n 1 (où n est une puissance de 2), modulo des entiers produits de plus petits entiers (pour manipuler les coe cients sous forme CRT), c'est-à-dire des paramètres utilisés en cryptographie basée sur les réseaux (voir par exemple [6]). Cette restriction permet, du fait des nombreuses optimisations décrites dans cet article, des performances signi cativement supérieures à NTL et FLINT pour les mêmes opérations. Nous présentons les gains obtenus dans la suite de la section. Tous les benchmarks ont été obtenus sur un processeur Intel Xeon E5-2666 v3. 4
Paramètres. Dans les trois bibliothèques, nous avons utilisé les mêmes quatre ensembles de paramètres :
Pour les tests sous NFLlib, nous avons utilisé respectivement des mots de base de 16, 32, 64 et 64 bits, pour pro ter des implémentations SIMD optimisées (dans les deux premiers cas, voir section 4.7). Pour NTL, nous avons utilisé la classe zz_pX pour les paramètres (1) et (2) puisque le module fait moins de 50 bits, et la classe ZZ_pX pour les paramètres (3) et (4). Finalement, nous avons travaillé avec le type fmpz_mod_poly_t pour FLINT.
Génération de polynômes aléatoires. Un élément clé en cryptographie basée sur les réseaux consiste à générer des polynômes aléatoires, c'est-à-dire dont les coe cients sont indépendamment et uniformément échantillonnés modulo q. Nous avons utilisé les fonctions de génération de nombres aléatoires proposées dans chaque bibliothèque, à savoir la fonction random de NTL, le générateur donné par le type flint_rand_t dans FLINT, et le générateur par défaut 5 de NFLlib. Les résultats sont illustrés par le tableau 3.
| Bibliothèque | NTL | FLINT | NFLlib (seq.) |
| (1) = (256;14) | 8:7 s | 4:6 s | 0:6 s |
| (2) = (512;30) | 22:1 s | 9:2 s | 2:5 s |
| (3) = (1024;62) | 169 s | 18:1 s | 9:3 s |
| (4) = (1024;6200) | 8149 s | 1010 s | 992 s |
NFLlib permet un gain signi catif comparé à NTL, mais le générateur d'aléa de FLINT (qui est essentiellement celui de GMP) est aussi rapide que celui de NFLlib quand une grande quantité d'aléa est générée. Néanmoins, il utilise l'algorithme Mersenne Twister. Ce dernier est très e cace, mais malheureusement insu sant pour une utilisation en cryptographie : connaître une grande quantité d'aléa permet de prédire avec certitude les nombres aléatoires qui seront générés dans le futur. A contrario, l'aléa dans NTL et NFLlib provient de générateurs de nombres pseudo-aléatoires qui conviennent pour une utilisation en cryptographie.
Addition. Comme expliqué précédemment, que les polynômes soient en représentations NTT ou représentés par leurs coe cients, additionner deux polynômes revient à additionner des vecteurs de n valeurs modulo q. Pour NTL nous avons utilisé la fonction add, pour FLINT la fonction fmpz_mod_poly_add, et pour NFLlib l'opérateur +. Les résultats sont donnés au tableau 4. NFLlib permet un gain d'un facteur entre 4 et 20 en vitesse comparé à NTL et FLINT.
| Bibliothèque | NTL | FLINT | NFLlib (seq.) |
| (1) = (256;14) | 1:4 s | 3:6 s | 0:1 s |
| (2) = (512;30) | 2:6 s | 6:8 s | 0:3 s |
| (3) = (1024;62) | 37:6 s | 13:3 s | 1:3 s |
| (4) = (1024;6200) | 588 s | 521 s | 168 s |
Calcul de la représentation NTT et multiplication. La représentation sous forme NTT est un élément clé de notre optimisation qui permet d'accélérer la multiplication de deux polynômes. Calculer la représentation NTT est possible dans NTL grâce aux fonctions TofftRep et ToFFTRep (pour zz_pX et ZZ_pX respectivement) mais n'a malheureusement pas l'air d'être une fonction disponible dans FLINT. Les résultats sont donnés dans les tableaux 5 et 6. L'algorithme de conversion vers ou depuis une représentation NTT est 10 à 30 fois plus rapide dans NFLlib que dans NTL.
| Bibliothèque | NTL | FLINT | NFLlib | NFLlib | NFLlib |
| (seq.) | (SSE) | (AVX2) | |||
| (1) = (256;14) | 6:7 s | 1:6 s | 0:4 s | 0:4 s | |
| (2) = (512;30) | 14:0 s | 3:4 s | 2:2 s | 1:7 s | |
| (3) = (1024;62) | 46:2 s | 11:1 s | |||
| (4) = (1024;6200) | 31568 s | 1126 s |
| Bibliothèque | NTL | FLINT | NFLlib | NFLlib | NFLlib |
| (seq.) | (SSE) | (AVX2) | |||
| (1) = (256;14) | 11:4 s | 2:3 s | 0:9 s | 0:9 s | |
| (2) = (512;30) | 24:9 s | 3:6 s | 2:4 s | 1:9 s | |
| (3) = (1024;62) | 188 s | 12:1 s | |||
| (4) = (1024;6200) | 38131 s | 1218 s |
Multiplication avec et sans représentation de Shoup. Nous avons ensuite simulé une multiplication sous représentation NTT dans NTL et FLINT (les fonctions n'existant pas par défaut) pour se comparer à l'opérateur dans NFLlib. Cette opération consiste en la multiplication coe cient par coe cient de deux tableaux de nombres modulo q. Nous avons aussi benchmarcké la multiplication quand une représentation de Shoup des nombres est connue. Les résultats sont donnés dans le tableaux 7. La multiplication classique est déjà 7 à 10 fois plus rapide dans NFLlib que dans NTL ou FLINT. Mais quand une représentation de Shoup d'un des opérandes est connue, un facteur 10 supplémentaire peut être obtenu. Cette technique n'est actuellement pas disponible dans NTL et FLINT : nos résultats illustrent donc le gain potentiel qu'une telle technique pourrait apporter à ces bibliothèques.
| Bibliothèque | NTL | FLINT | NFLlib (seq.) | NFLlib (seq, w/ Shoup) |
| (1) = (256;14) | 1:0 s | 4:8 s | 0:1 s | 0:15 s |
| (2) = (512;30) | 1:7 s | 9:7 s | 0:8 s | 0:6 s |
| (3) = (1024;62) | 52:6 s | 33:5 s | 28:0 s | 2:3 s |
| (4) = (1024;6200) | 15259 s | 15839 s | 2801 s | 231 s |
Implémentation d'un schéma de chi rement à clé publique. Tous les benchmarks précédents illustrent étape par étape les gains en performance que NFLlib permet d'obtenir par rapport à NTL et FLINT. Cependant, ceci ne re ète pas totalement le comportement de chaque bibliothèque lorsqu'elle est utilisée en pratique pour implémenter e.g. un schéma cryptographique. Par exemple, les benchmarks des multiplications proviennent d'implémentations faites-main qui peuvent ne pas correspondre aux algorithmes sous-jacents utilisés dans les bibliothèques. De même la conversion vers une représentation NTT n'est pas disponible dans FLINT, ce qui fait pressentir un comportement en pratique assez coûteux.
Pour comparer l'e cacité relative des trois bibliothèques sur un cas pratique, nous avons choisi d'implémenter le schéma de chi rement basé sur les réseaux tel que décrit dans la section 2.3 . Les paramètres sont choisis a n d'assurer 128 ou 256 bits de sécurité selon [14]. Cependant pour atteindre un niveau su sant de sécurité, nous devons modi er les paramètres (4), et travaillons donc à la place avec les paramètres suivants :
Nous avons implémenté ce schéma en utilisant les trois bibliothèques. Les polynômes des clés publiques et secrètes étant constants, nous avons cherché à optimiser les multiplications par ces derniers. Pour NFLlib, nous avons calculé leur représentation de Shoup. Pour NTL, nous avons utilisé les fonctions zz_pXMultiplier et zz_pXModulus (et leurs équivalents ZZ_) qui permettent respectivement d'optimiser les multiplications par un polynôme constant d'une manière similaire à notre représentation de Shoup), et d'optimiser les opérations de réduction modulo Xn + 1. Pour FLINT, nous calculé l'inverse de Xn + 1 modulo Xn+1 pour optimiser la multiplication modulaire en utilisant la fonction fmpz_mod_poly_mulmod_preinv au lieu de fmpz_mod_poly_mulmod. Finalement, nous obtenons les résultats donnés dans les tableaux 8 et 9. Utiliser NFLlib permet de gagner un à deux ordres de magnitudes par rapport à l'utilisation des bibliothèques génériques que sont NTL et FLINT.
| Bibliothèque | NTL | FLINT | NFLlib | NFLlib | NFLlib |
| (seq.) | (SSE) | (AVX2) | |||
| (1) = (256;14) | 156:9 s | 134:8 s | 10:9 s | 7:1 s | 6:7 s |
| (2) = (512;30) | 321:9 s | 296:3 s | 18:2 s | 15:8 s | 14:1 s |
| (3) = (1024;62) | 1599:8 s | 673:5 s | 69:7 s | ||
| (40) = (16384;620) | 233068 s | 221863 s | 10723 s |
| Bibliothèque | NTL | FLINT | NFLlib | NFLlib | NFLlib |
| (seq.) | (SSE) | (AVX2) | |||
| (1) = (256;14) | 54:3 s | 52:1 s | 2:7 s | 1:20 s | 1:12 s |
| (2) = (512;30) | 111:8 s | 130:4 s | 4:3 s | 3:58 s | 3:1 s |
| (3) = (1024;62) | 570:8 s | 301:9 s | 16:6 s | ||
| (40) = (16384;620) | 112358 s | 111625 s | 4528 s |
L'amélioration des performances peut se faire à plusieurs niveaux :
Les deux premières parties ont été décrites section 2. Les sections suivantes décrivent les améliorations réalisées au niveau de l'implémentation.
La bibliothèque NFLlib fournit principalement une classe poly fournissant les abstractions nécessaires pour e ectuer les opérations décrites dans la section 2. Cette section présente les di érents composants de l'architecture décrite dans la gure 1.
ScalaireSSEAVX2Moteur
Expression templates
transfo. NTT
poly
Chaque opération de calcul sur les polynômes jugée critique a été identi ée grâce à une analyse dynamique permettant de détecter les points chauds du binaire produit, comme présenté section 4.5. Il apparaît que plusieurs fonctions peuvent béné cier d'une vectorisation manuelle, basée sur les jeux d'instructions SSE et AVX2 si ces derniers sont disponibles sur la machine cible.
Ainsi, si une version de fonction spécialisée pour les jeux d'instructions SSE et/ou AVX2 s'avère nécessaire a n de gagner en performance, alors cette opération est extraite a n de pouvoir être spécialisée. Pour éviter les doublons par architectures, le mécanisme de vectorisation générique suivant a été adopté :
La liste des moteurs SIMD disponibles pour l'instant est :
Une version naïve de la classe des polynômes encapsulerait un pointeur vers une zone mémoire allouée dynamiquement. En procédant ainsi, on remarque que l'opération inv_ntt est particulièrement coûteuse. Elle est composée d'un appel à la fonction ntt entourée de deux permutations, comme illustré au listing 1.1.
Chaque itération exécute donc des accès à trois tableaux di érents dont un accès avec une indirection.
En se basant sur l'observation que la permutation est calculée à l'initialisation de la bibliothèque et ne dépend que du degré du polynôme, degree, nous avons transformé l'argument degree en un paramètre template, ce qui permet de réécrire la fonction précédente sous la forme donnée au listing 1.2
En utilisant plusieurs techniques de méta-programmation connues, le tableau perm est remplacé par un calcul à la compilation, au prix d'un déroulage complet de la boucle d'origine. Ainsi, chaque itération ne fait plus que deux accès de tableaux à des indices constants.
Un e et de bord important de la paramétrisation est que l'allocation dynamique du tableau temporaire y est remplacée par une allocation statique, phénomène également observé pour le tableau utilisé pour représenter le polynôme, ce qui nous permet d'éviter quelques appels et surtout d'avoir une meilleur localité mémoire. On pousse la logique en rendant le polynôme également paramétré par le type d'entier utilisé pour stocker les coe cient et la taille de la série de nombre premiers utilisés, ce qui permet de supprimer toute forme d'allocation dynamique à la création du polynôme.
Rendre ces paramètres constants fait également apparaître de nouvelles possibilité d'optimisation pour le compilateur (e.g. constant folding, full loop unrolling, partial evaluation...).
Au nal, le gain en temps d'exécution observé pour cette optimisation est de l'ordre de 15% et la classe polynôme devient une classe template paramétrée par un type et deux valeurs, au prix d'un temps de compilation supérieur.
Un problème classique en C++ est la création d'objets temporaires lors du calcul d'une expression complexe. Par exemple, en supposant que les opérateur idoines aient été surchargés, l'évaluation de l'expression polynomiale p0 + p1 p2 conduira à la création de deux objets temporaires, l'un pour la multiplication, l'autre pour l'addition, comme représenté dans le listing qui suit :
Cette forme est loin d'être optimale : les boucles pourraient être fusionnées, et le polynôme intermédiaire pourrait être supprimé pour aboutir à :
On notera par ailleurs que cette forme est plus intéressante du point de vue des instructions vectorielles, puisqu'elle donne un ratio de deux opérations pour un store et trois load, là où la précédente donnait un ratio de deux opérations pour deux store et quatre load 6 .
L'approche qui consiste à fournir une fonction optimisée pour chaque combinaison d'opérateurs ne passe bien évidement pas à l'échelle. Les expression templates [19] proposent une solution élégante à ce problème en retardant l'évaluation d'une expression à l'assignation. L'idée est de construire l'arbre d'évaluation à travers le système de type et de déclencher l'évaluation de l'expression au moment de l'assignation en se servant du type de retour de l'expression pour reconstruire la boucle fusionnée. Ainsi, dans notre exemple, le type de retour sera de la forme donnée au listing 1.3.
Cette construction est compatible avec la vectorisation manuelle, pour peu qu'une forme vectorielle de chacun des opérateurs soit disponible, ce qui a été fait à chaque fois que possible. Dans la cas contraire, un mécanisme de trait permet de détecter à la compilation, et sans intervention de l'utilisateur, si la forme vectorielle est disponible pour toute l'expression ou si la forme séquentielle doit être utilisée. En ce sens, notre approche est très semblable à celle utilisée par boost.simd [7].
Un autre avantage des expression templates est qu'elles permettent la
réécriture de l'arbre avant son évaluation. Dans notre cas, nous disposons
d'une version accélérée du multiply-add qui évite un coûteux calcul
de modulo. Toujours à la compilation, en utilisant la spécialisation
partielle des templates, on peut donc remplacer l'expression donnée
au listing 1.3 par expr
A n d'optimiser les performances de la bibliothèque NFLlib, un cas test représentatif des opérations de chi rement et déchi rement asymétrique a été étudié grâce à valgrind/callgrind7 . Cela nous a permis d'identi er les points chauds de ces deux opérations, et de s'attarder premièrement sur ceux-ci. Après optimisations du code associé, une nouvelle analyse est lancée a n de découvrir éventuellement de nouveaux points chauds. Ce processus est répété jusqu'à ce qu'il devienne di cile d'optimiser les parties coûteuses.
Le pro lage montre que le calcul du chi rement est réparti entre le calcul de la transformation NTT ( 64%), des opérations arithmétiques sur les polynômes considérés (modular addition, modular multiply shoup et la fusion de ces deux opérations) ( 20%) et le calcul d'aléa ( 16%) . Le calcul d'aléa étant considéré comme déjà optimisé, les e orts sont ainsi à concentrer sur la fonction ntt.
En ce qui concerne le déchi rement, la fonction la plus importante en terme de temps de calcul est inv_ntt ( 80%), qui appelle elle-même ntt ( 96% du temps d'exécution de inv_ntt). Il faudra ainsi se focaliser sur cette fonction après avoir optimisé la fonction ntt. Le reste du temps de calcul est réparti entre les opérations arithmétiques polynomiales citées ci-dessus.
Les sections suivantes décrivent les di érentes étapes de transformation qui ont été appliquées a n d'optimiser ces fonctions et d'autres parties du code.
La boucle NTT a tout d'abord été réécrite a n d'expliciter plus facilement les accès mémoires. La version originale est basée sur l'implémentation de David Harvey. 8
La partie du code prenant le plus de temps CPU, modi ée pour utiliser des entiers 32 bits, est présentée listing 1.4 .
La boucle while est manuellement déroulée d'un pas de deux. Les compilateurs e ectuent cette opération automatiquement et auraient même tendance à être perturbés par cette modi cation, nous commençons donc par réécrire cette boucle en une boucle for canonique, en enlevant les pré-calculs d'indices qui seront optimisés par le compilateur (passe -fmove-loop-invariants), pour aboutir au listing 1.5.
Le compilateur est capable d'analyser la dernière boucle et de la vectoriser, impliquant ainsi un gain de performance.
Nous avons comparé les performances obtenues en compilant chacune des versions de la boucle avec di érents drapeaux, simulant di érentes architectures cibles :
Le tableau 10 résume les résultats obtenus. On observe que nos changements impliquent au moins une augmentation de performances dans tous les cas, et ce dû principalement à la vectorisation automatique rendue possible de la dernière boucle de la fonction ntt.
| NTT (référence)
| |||
| Type | Sans vectorisation | SSE4 | AVX2 |
| 64 bits | 16.7 s | 14.5 s | 13.5 s |
| 32 bits | 6.9 s | 4.3us | 4.3 s |
| 16 bits | 7.4 s | 5.0us | 5.0 s |
| NTT (nouvelle boucle)
| |||
| Type | Sans vectorisation | SSE4 | AVX2 |
| 64 bits | 14.0 s | 13.7 s | 13.4 s |
| 32 bits | 5.7 s | 3.6 s | 3.4 s |
| 16 bits | 7.2 s | 3.4 s | 3.4 s |
Plusieurs boucles ont été vectorisées en utilisant les jeux d'instructions SSE et AVX2 (suivant disponibilité sur la machine cible). Les compilateurs modernes sont capables d'une telle transformation sur certains algorithmes. Une première étape a ainsi été d'inspecter le code généré par le compilateur utilisé (GCC 4.9.2), et de regarder s'il n'était pas possible de l'améliorer. Nous allons dans cette section décrire comment certaines opérations ont été optimisées grâce au jeu d'instructions SSE par rapport aux versions produites par le compilateur utilisé (GCC 4.9.2 sauf mention contraire). Nous n'avons pas décrit en détail l'optimisation de toutes les diverses opérations contenues dans la bibliothèque (et l'utilisation du jeu d'instructions AVX2), car les mêmes techniques ont globalement été utilisées.
Une des opérations présente à plusieurs endroits dans la bibliothèque est multiply high. Pour deux nombres a et b entiers non signés de N bits, elle consiste à calculer (a b) >> N. Autrement dit, cette opération consiste à multiplier deux nombres de N bits et récupérer la partie supérieure comprise entre les bits N et 2 N. De manière plus détaillée, cette opération peut être décrite de la façon suivante :
L'équivalent en langage C avec des entiers 32 bits non signés est le suivant :
Pour la suite, nous nous plaçons dans le cas d'entiers non signés 32 bits. Nous discuterons ensuite des versions avec des entiers non signés 64 et 16 bits.
L'instruction mul présente dans l'architecture Intel x86 32 bits multiplie deux entiers de 32 bits et renvoie le résultat sur 64 bits, réparti entre deux registres (eax pour la partie basse, et edx pour la partie haute). Il su t ainsi de récupérer la valeur nécessaire dans le bon registre (edx en l'occurrence). Un compilateur comme GCC reconnaît cette opération et fait exactement cela. En e et, la version désassemblée de la fonction ci-dessus ressemble à ceci :
Par contre, avec le jeu d'instructions Intel x86 64 bits, GCC utilise l'opération native 64 bit et fait un shift logique à droite de 32 bits :
Il s'avère que sur un processeur Intel Core i7-3520M avec un système d'exploitation 64-bit, la version 64-bit est meilleure d'environ 10%.
Ce qui nous intéresse est l'utilisation de cette opération au sein d'une boucle, à savoir un code équivalent à celui-ci :
GCC arrive à vectoriser la boucle ci-dessus en utilisant le jeu d'instruction SSE ou AVX2 (et ce de la même façon sur x86 32 ou 64 bits). En prenant pour exemple la version SSE, le corps de boucle est le suivant :
En réécrivant cela de manière symbolique, ce code est équivalant à :
L'idée est donc d'utiliser l'instruction mul_epu32, qui va multiplier seulement deux entiers des quatre disponibles dans un registre SSE et stocker le résultat sur 64 bits, comme décrit sur le schéma ci-dessous :
| sse_a | = | 31a0 63a1 95a2 127a3 0 |
| sse_b | = | 31b0 63b1 95b2 127b3 0 |
| mul_epi32(sse_a,sse_b) | = | 127a2 b263a0 b00 |
L'opération totale doit ainsi être faite grâce à 2 mul_epu32. Il faut ainsi ensuite réordonner les vecteurs sse_a et sse_b. Les instructions unpacklo_epi32 et unpackhi_epi32 sont utilisées à ces ns. Ces deux fonctions sont décrites ci-dessous :
| sse_a | = | 31a0 63a1 95a2 127a3 0 |
| unpacklo_epi32(sse_a,sse_a) | = | 31a0 63a0 95a2 127a2 0 |
| unpackhi_epi32(sse_a,sse_a) | = | 31a1 63a1 95a3 127a3 0 |
Ainsi, la combinaison de unpack*_epi32 et mul_epu32 va nous donner, pour mullowt et mulhight :
| alow | = | 31a0 63a0 95a2 127a2 0 |
| blow | = | 31b0 63b0 95b2 127b2 0 |
| mullowt | = | 127a2 b263a0 b00 |
| ahigh | = | 31a1 63a1 95a3 127a3 0 |
| bhigh | = | 31b1 63b1 95b3 127b3 0 |
| mulhight | = | 127a3 b363a1 b10 |
L'instruction srli_epi64 pemet d'appliquer un shift logique sur les entiers 64 bits qui viennent d'être produits. Cela donne :
| mullow | = | 127(a2 b2) 3263(a0 b0 ) 320 |
| mulhigh | = | 127(a3 b3) 3263(a1 b1 ) 320 |
A n de reconstruire le vecteur nal, GCC utilise l'instruction shuffle_ps avec le coe cient 0x88, ce qui est équivalent à :
| mullow | = | 31(a0 b0) 3263095(a2 b2 ) 3212700 |
| mulhigh | = | 31(a1 b1) 3263095(a3 b3 ) 3212700 |
| sse_res | = | 31(a0 b0) 3263(a1 b1 ) 3295(a2 b2 ) 32127(a3 b3 ) 320 |
La question est de savoir si nous pouvons optimiser ce calcul. Il est en e et présent dans un certain nombres d'opérations de la bibliothèque. Si nous regardons un peu plus en détail, nous voyons que les deux premières opérations unpacklo_epi32 sont inutiles. En e et, utiliser l'instruction mul_epi32 juste après les deux opérations sse_load donne déjà la valeur de mullowt. Nous pouvons ensuite appliquer le décalage de 32 bits.
| sse_a | = | 31a0 63a1 95a2 127a3 0 |
| sse_b | = | 31b0 63b1 95b2 127b3 0 |
| mullowt | = | mul_epi32(sse_a, sse_b) |
| mullowt | = | 127a2 b263a0 b00 |
| mullow | = | 127(a2 b2) 3263(a0 b0 ) 320 |
Pour calculer mulhigh, les opérations unpackhi_epi32 restent par contre nécessaire. En e et, aucune instruction SSE utilisant des entiers sur 32 bits ne fait de multiplication permettant de faire 127a3 b363a1 b10 . Par contre, la dernière opération srli_epi64 peut être omise. En e et, nous avons pour l'instant :
| mullow | = | 127(a2 b2) 3263(a0 b0 ) 320 |
| mulhight | = | 127a3 b363a1 b10 |
En considérant ces vecteurs comme quatre entiers de 32 bits, nous avons :
| mullow | = | 31(a0 b0) 3263095(a2 b2 ) 3212700 |
| mulhight | = | 31(a1 b1)[0:31]63(a1 b1 )[32:63]95(a3 b3 )[0:31]127(a3 b3 )[32:63]0 |
Les valeurs que nous recherchons sont ainsi déjà présentes mais de manière entrelacées dans les vecteurs mullow et mulhight. L'instruction blend_ps permet de mélanger ces deux vecteurs.
Ainsi, en utilisant une valeur de 0b1010 pour imm8, les deux vecteurs précédents peuvent être mélangés directement a n d'obtenir le résultat attendu :
| res | = | blend_ps(mullow, mulhight, 0b1010) |
| res | = | 31(a0 b0) 3263(a1 b1 )[32:63]95(a2 b2 ) 32127(a3 b3 )[32:63]0 |
| res | = | 31(a0 b0) 3263(a1 b1 ) 3295(a2 b2 ) 32127(a3 b3 ) 320 |
L'algorithme nal est ainsi le suivant :
Nous avons donc gagné trois instructions (deux unpack_epi32 et un srli_epi32). En ce qui concerne les entiers sur 16 bits, GCC va vectoriser la boucle d'origine de la même façon qu'il le fait pour 32 bits. Cela est dommage car il existe une instruction SSE qui fait directement ce que nous recherchons, à savoir _mm_mulhi_epi16. C'est cette instruction que nous allons utiliser dans ce cas-là. Pour les entiers sur 64 bits, il n'existe aucune instruction SSE/AVX/AVX2 permettant d'e ectuer des multiplications sur ce type d'entiers. Le code séquentiel est ainsi utilisé.
Le même principe a été appliqué avec l'utilisation du jeu d'instructions AVX2.
L'opération multiply high est utilisée lors de plusieurs noyaux de calcul, à savoir :
Nous allons maintenant nous intéresser à l'opération modular multiply shoup, disponible dans le listing 4.7.
Lorsque des entiers de 16 bits sont utilisés, GCC 4.9 n'arrive pas à vectoriser cette opération, principalement à cause du passage par greater_value_type. Or obtenir une version vectorielle ce code est possible, et une écriture manuelle est ainsi nécessaire.
Nous avons vu ci-dessus comment faire l'opération multiply high, et pouvons ainsi déjà réutiliser cette opération. Nous avons ainsi pour l'instant :
Pour e ectuer les opérations x y et q p, nous devons d'abord convertir nos vecteurs d'entiers de 16 bits en vecteur d'entiers de 32 bits. Dans le cas où seul le jeu d'instruction SSE est disponible, le résultat de cette conversion sera stocké dans un registre 128 bits. Il faudra ainsi faire l'opération en deux temps, en traitant d'abord les quatre premiers entiers de 16 bits puis réitérer avec les quatre derniers.
Nous avons premièrement besoin d'un vecteur de quatre entiers de 32 bits contenant tous la valeur de p. Cela se fait simplement avec l'instruction set1_epi32 :
| sse_p | = | set1_epi32(p) |
| sse_p | = | 31p63p95p127p0 |
L'instruction cvtepu16_epu32 nous permet de convertir les quatre premiers entiers de 16 bits en quatre entiers de 32 bits (avec ze = zero_extend) :
| sse_x | = | 15x4 31x5 47x6 63x7 0 15x0 31x1 47x2 63x3 0 |
| sse_x_32l | = | cvtepu16_epu32(sse_x) |
| sse_x_32l | = | 31ze(x0)63ze(x1 )95ze(x2 )127ze(x3 )0 |
En faisant la même opération avec sse_y, sse_q et sse_p, nous pouvons ensuite utiliser l'instruction mullo_epi32, qui multiple deux entiers 32 bits et ne renvoie que la partie basse, créant ainsi un vecteur de quatre entiers de 32 bits avec le résultat attendu :
| sse_x_32l | = | 31ze(x0)63ze(x1 )95ze(x2 )127ze(x3 )0 |
| sse_y_32l | = | 31ze(y0)63ze(y1 )95ze(y2 )127ze(y3 )0 |
| mullo_xy | = | 31(x0 y0)[0:31]63(x1 y1 )[0:31]95(x2 y2 )[0:31]127(x3 y3 )[0:31]0 |
| sse_q_32l | = | 31ze(q0)63ze(q1 )95ze(q2 )127ze(q3 )0 |
| sse_p_32l | = | 31p63p95p127p0 |
| mullo_qp | = | 31(q0 p)[0:31]63(q1 p)[0:31]95(q2 p)[0:31]127(q3 p)[0:31]0 |
Il ne reste plus qu'à soustraire ces deux résultats intermédiaire avec l'opération sub_epi32.
| sse_res | = | sub_epi32(mullow_xy,mullow_qp) |
Il faut maintenant e ectuer la dernière opération, à savoir :
Concrètement, il faut comparer sse_res à sse_p, et suivant ce résultat, soustraire ou non l'entier p à l'entier correspondant dans sse_res.
L'opération cmp_epi32 va donner ce résultat (avec cmp32(b) = b ? 0xFFFFFF : 0) :
| sse_cmp | = | cmp_epi32(sse_res, sse_p) |
| sse_cmp | = | 31cmp32(res0 > p)63cmp32(res1 > p)95cmp32(res2 > p)127cmp32(res3 > p)0 |
Nous avons cependant deux problèmes ici :
Une technique classique pour résoudre le second problème est de simplement soustraire 231 (soit 0x80000000) aux deux entiers à comparer. En e et, cela a pour e et de rétablir l'ordre de nos deux entiers non signés dans l'espace des entiers signés en projetant 0 sur 231.
Une fois que la comparaison est faite et valide, il su t de prendre le vecteur résultat et de faire un ET bit à bit avec sse_p :
| sse_cmp | = | 31cmp32(res0 p)63cmp32(res1 p)95cmp32(res2 p)127cmp32(res3 p)0 |
| sse_p | = | 31p63p95p127p0 |
| sse_cmp | = | and_si128(sse_cmp, sse_p) |
| sse_cmp | = | 31res0 p?p : 063res1 p?p : 095res2 p?p : 0127res3 p?p : 00 |
| sse_res | = | sub_epi32(sse_res, sse_cmp) |
L'algorithme nal pour traiter les quatre premiers entiers de 16 bits est donc le suivant :
Pour traiter les quatre derniers entiers de 16 bits, une permutation est e ectuée sur sse_x, sse_y et sse_q a n de placer ces quatre derniers entiers en premiers, et réitérer le même processus.
Nous arrivons ainsi avec ces deux vecteurs :
| sse_reslow | = | 31res063res195res2127res30 |
| sse_reshigh | = | 31res463res595res6127res70 |
Il reste donc à tronquer chaque entier de 32 bits en 16 bits et créer le résultat nal. L'instruction packus_epi32 fait exactement cela :
| sse_res | = | packus_epi32(sse_reslow, sse_reshigh) |
| sse_res | = | 15res431res547res663res70 15res031res147res263res30 |
Nous avons ainsi le résultat escompté !
En ce qui concerne l'opération modular multiply shoup avec des entiers 32 bits, GCC arrive ici à vectoriser la boucle. Elle est néanmoins spécialisée dans la bibliothèque a n de tenir compte des optimisations e ectuées sur l'opération multiply high. Nous n'avons pas connaissance d'une technique permettant de faire ces mêmes calculs vectoriels avec des entiers de 64 bits, principalement à cause du manque de multiplication vectorielles avec ce type d'entiers dans les jeux d'instructions SSE et AVX2. GCC ne vectorise pas cette opération.
Benchmarker individuellement chaque opération n'est pas évident, car la limite du bus mémoire est vite atteinte sur ce type d'opérations. Par exemple, si nous mesurons le temps d'exécution des versions optimisées par GCC et écrites manuellement de l'opération multiply high, nous obtenons ceci (sur un processeur Intel Core i7-3520M avec un OS 64 bit) :
gcc-* est associé au code vectorisé généré par gcc. man-* correspond au code vectorisé écrit manuellement.
Le calcul a été fait sur des vecteurs de 10.000.000 entiers, lancé 100 fois en moyennant les temps d'exécution et en ne prenant pas en compte les temps aux extrémités (pour ne pas fausser les résultats par des cas dégénérés).
Nous pouvons voir que les versions 16 bits vont deux fois plus vite que les versions 32 bits. Cela n'est pas dû au fait que les instructions vectorielles travaillant sur des entiers 16 bits vont deux fois plus vite leurs homologues sur 32 bits, mais bien que la limite dans ce cas n'est pas le CPU, mais le bus mémoire. En e et, le vecteur de 10.000.000 entiers de 16 bits est bel et bien deux fois plus petit que celui composé d'entiers de 32 bits. Cela se con rme avec le calcul de la bande passante moyenne de traitement du calcul, qui reste constante entre les versions 16 et 32 bits. Ainsi, le gain de la vectorisation manuelle n'est ici pas apparent.
La di érence de performance obtenue grâce au travail précédent commence à se voir lorsque les di érentes opérations optimisées sont enchaînées, comme la transformation NTT (voir section 4.6). Ainsi, en compilant le code de la bibliothèque en laissant GCC vectoriser les boucles de calcul, nous obtenons comme performances (temps par opération) (G = temps_gcc=temps_manuel) 9 :
NTT (vectorisée par GCC, résultats de la section 4.6)
| ||
| Type | SSE | AVX2 |
| 32 bits | 3.6 s | 3.4 s |
| 16 bits | 3.4 s | 3.4 s |
| NTT (vectorisation manuelle)
| ||
| Type | SSE | AVX2 |
| 32 bits | 2.4 s (G = 1.5) | 1.9 s (G = 2.8) |
| 16 bits | 1.2 s (G = 2.8) | 0.9 s (G = 3.7) |
Le cas lors d'un chi rement ou déchi rement asymétrique a aussi été benchmarké, soit en laissant GCC vectoriser les di érentes boucles, soit en utilisant les versions vectorielles décrites ci-dessus. Nous obtenons les résultats suivant (avec (G = temps_gcc=temps_manuel) :
| Chi rement (vectorisée par GCC)
| |||
| Type | Sans vectorisation | SSE | AVX2 |
| 32 bits | 27.8 s | 26.1 s | 17.3 s |
| 16 bits | 23.3 s | 22.1 s | 21.3 s |
| Chi rement (vectorisation manuelle)
| |||
| Type | Sans vectorisation | SSE | AVX2 |
| 32 bits | 27.8 s | 22.8 s (G = 1.1) | 14.0 s (G = 1.2) |
| 16 bits | 23.3 s | 15.4 s (G = 1.4) | 13.6 s (G = 1.6) |
| Déchi rement (vectorisée par GCC)
| |||
| Type | Sans vectorisation | SSE | AVX2 |
| 32 bits | 5.1 s | 5.2 s | 4.7 s |
| 16 bits | 6.2 s | 6.2 s | 5.9 s |
| Déchi rement (vectorisation manuelle)
| |||
| Type | Sans vectorisation | SSE | AVX2 |
| 32 bits | 5.1 s | 3.6 s (G = 1.4) | 3.0 s (G = 1.6) |
| 16 bits | 6.2 s | 2.7 s (G = 2.3) | 2.2 s (G = 2.7) |
Après toutes les optimisations décrites ci-dessus, une nouvelle étude avec valgrind/callgrind a été e ectuée, pour les mêmes opérations de chi rement et de déchi rement dé nies à la section 4.5.
En ce qui concerne le chi rement, la fonction de génération d'aléa occupe maintenant 41% du temps d'exécution de la fonction encrypt, contre 16% au départ. Cette fonction ayant été la seule à ne pas avoir été optimisée, il est normal qu'elle devienne la partie dominante du chi rement. Il pourrait ainsi maintenant être intéressant de voir si des optimisations sont possibles au sein de la génération d'aléa.
Pour la fonction de déchi rement, la fonction prépondérante reste les fonctions inv_ntt et ntt, même si moins de temps CPU y est relativement consacré. Il pourrait ainsi être intéressant d'essayer d'améliorer encore cette fonction.
NFLlib permet d'obtenir des performances très supérieures à l'existant sur des preuves de concept. Pour passer à un prototypage plus près d'un usage réel, il reste encore de nombreux jalons. Parmi eux, la résistance aux attaques par canaux cachés est probablement le plus important. Une telle propriété aura sans le moindre doute un coût signi catif et il ne sera pas trivial de le limiter.
La bibliothèque NFLlib est en développement mais vise, à terme, à être utilisée dans des applications grand public. Pour le moment, elle reste un outil de recherche permettant d'expérimenter simplement sur des algorithmes cryptographiques actuels et nouveaux. Nous espérons que le niveau de performance des versions ultérieures sera à la hauteur de ces premiers résultats.
1. Carlos Aguilar-Melchor, Joris Barrier, Laurent Fousse, and Marc-Olivier Killijian. XPIRe : Private Information Retrieval for Everyone. 2014.
2. Daniel J. Bernstein. The salsa20 family of stream ciphers. In Matthew J. B. Robshaw and Olivier Billet, editors, New Stream Cipher Designs - The eSTREAM Finalists, volume 4986 of LNCS, pages 84 97. Springer, 2008.
3. Joppe W. Bos, Craig Costello, Michael Naehrig, and Douglas Stebila. Post-quantum key exchange for the TLS protocol from the ring learning with errors problem. August 2014.
4. Zvika Brakerski, Craig Gentry, and Vinod Vaikuntanathan. (leveled) fully homomorphic encryption without bootstrapping. TOCT, 6(3) :13, 2014.
5. Yuanmi Chen and Phong Q. Nguyen. BKZ 2.0 : Better lattice security estimates. In Dong Hoon Lee and Xiaoyun Wang, editors, Advances in Cryptology - ASIACRYPT 2011 - 17th International Conference on the Theory and Application of Cryptology and Information Security, Seoul, South Korea, December 4-8, 2011. Proceedings, volume 7073 of LNCS, pages 1 20. Springer, 2011.
6. Léo Ducas, Alain Durmus, Tancrède Lepoint, and Vadim Lyubashevsky. Lattice signatures and bimodal Gaussians. In Ran Canetti and Juan A. Garay, editors, Advances in Cryptology - CRYPTO 2013 - 33rd Annual Cryptology Conference, Santa Barbara, CA, USA, August 18-22, 2013. Proceedings, Part I, volume 8042 of LNCS, pages 40 56. Springer, 2013.
7. Pierre Estérie, Mathias Gaunard, Joel Falcou, Jean-Thierry Lapresté, and Brigitte Rozoy. Boost. simd : generic programming for portable simdization. In Proceedings of the 21st international conference on Parallel architectures and compilation techniques, pages 431 432. ACM, 2012.
8. Sanjam Garg, Craig Gentry, and Shai Halevi. Candidate multilinear maps from ideal lattices. In Thomas Johansson and Phong Q. Nguyen, editors, Advances in Cryptology - EUROCRYPT 2013, 32nd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Athens, Greece, May 26-30, 2013. Proceedings, volume 7881 of LNCS, pages 1 17. Springer, 2013.
9. Craig Gentry. Fully homomorphic encryption using ideal lattices. In Michael Mitzenmacher, editor, Proceedings of the 41st Annual ACM Symposium on Theory of Computing, STOC 2009, Bethesda, MD, USA, May 31 - June 2, 2009, pages 169 178. ACM, 2009.
10. Tim Güneysu, Tobias Oder, Thomas Pöppelmann, and Peter Schwabe. Software speed records for lattice-based signatures. In Philippe Gaborit, editor, Post-Quantum Cryptography - 5th International Workshop, PQCrypto 2013, Limoges, France, June 4-7, 2013. Proceedings, volume 7932 of LNCS, pages 67 82. Springer, 2013.
11. Shai Halevi and Victor Shoup. Algorithms in helib. In Juan A. Garay and Rosario Gennaro, editors, Advances in Cryptology - CRYPTO 2014 - 34th Annual Cryptology Conference, Santa Barbara, CA, USA, August 17-21, 2014, Proceedings, Part I, volume 8616 of LNCS, pages 554 571. Springer, 2014.
12. William Hart et al. Fast Library for Number Theory (Version 2.4.4), 2015. http ://www.flintlib.org.
13. Arjen K. Lenstra, Hendrik W. Lenstra Jr., and László Lovász. Factoring polynomials with rational coe cients. Mathematische Annalen, 261(4) :515 534, 1982.
14. Richard Lindner and Chris Peikert. Better key sizes (and attacks) for lwe-based encryption. In Aggelos Kiayias, editor, Topics in Cryptology - CT-RSA 2011 - The Cryptographers' Track at the RSA Conference 2011, San Francisco, CA, USA, February 14-18, 2011. Proceedings, volume 6558 of LNCS, pages 319 339. Springer, 2011.
15. Michael Naehrig, Kristin E. Lauter, and Vinod Vaikuntanathan. Can homomorphic encryption be practical ? In Christian Cachin and Thomas Ristenpart, editors, Proceedings of the 3rd ACM Cloud Computing Security Workshop, CCSW 2011, Chicago, IL, USA, October 21, 2011, pages 113 124. ACM, 2011.
16. Oded Regev. On lattices, learning with errors, random linear codes, and cryptography. J. ACM, 56(6), 2009.
17. Claus-Peter Schnorr and M. Euchner. Lattice basis reduction : Improved practical algorithms and solving subset sum problems. Math. Program., 66 :181 199, 1994.
18. Victor Shoup. Number Theory Library (Version 8.1), 2015. http ://www.shoup.net/ntl.
19. Todd Veldhuizen. Expression templates. C++ Report, 7 :26 31, 1995.