💻 computer science

GPU Acceleration of Learning With Errors KEMs Using OpenACC for Post-Quantum Cryptography

Cet article présente une implémentation accélérée par GPU d'un mécanisme d'encapsulation de clé basé sur le Learning with Errors (LWE) utilisant OpenACC, démontrant des accélérations significatives (jusqu'à 208×) et une efficacité énergétique améliorée sur les GPU NVIDIA, particulièrement sur le Superchip Grace Hopper, par rapport aux systèmes traditionnels basés sur CPU et H100.

Auteurs originaux : Tiziana Liberati, Nitin Shukla, Matteo Barbieri, Gabriella Bettonte, Elisabetta Boella, Simone Rizzo, Daniele Gregori, Marco Pedicini

Publié 2026-06-02

📖 5 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Tiziana Liberati, Nitin Shukla, Matteo Barbieri, Gabriella Bettonte, Elisabetta Boella, Simone Rizzo, Daniele Gregori, Marco Pedicini

Article original sous licence CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Ceci est une explication générée par l'IA de l'article ci-dessous. Elle n'a pas été rédigée ni approuvée par les auteurs. Pour une précision technique, consultez l'article original. Lire la clause de non-responsabilité complète

Imaginez que vous essayez de verrouiller un coffre au trésor avec une clé si complexe que même un robot super intelligent du futur (un ordinateur quantique) ne pourrait pas la crocheter. C'est l'objectif de la Cryptographie Post-Quantique. Le "verrou" spécifique sur lequel se concentre ce document s'appelle LWE (Learning With Errors).

Considérez le LWE comme une tentative de résoudre un immense puzzle mathématique où quelqu'un a intentionnellement ajouté un peu de "statique" ou de "bruit" au signal. Il est facile de créer le bruit, mais incroyablement difficile de filtrer ce bruit pour trouver le message original sans la clé secrète. Le problème est que résoudre ce puzzle sur un ordinateur standard est comme essayer de déplacer une montagne grain de sable par grain de sable — cela prend une éternité.

Voici ce que les chercheurs ont fait pour accélérer les choses, expliqué simplement :

1. Le Problème : Le CPU est un camion lent

Les auteurs sont partis d'une version de ce chiffrement qui s'exécute sur un processeur d'ordinateur standard (le CPU). Ils ont constaté que le CPU peinait. C'était comme un seul camion de livraison essayant de déplacer des milliers de boîtes. Chaque fois qu'il devait déplacer une boîte (une donnée) de l'entrepôt (la mémoire) vers le plateau du camion, il devait s'arrêter, charger et conduire. Le camion passait la majeure partie de son temps à attendre, et non à travailler.

2. La Solution : Le GPU est une flotte de drones

Pour corriger cela, ils ont transféré le gros du travail vers un GPU (Processeur de Graphismes). Si le CPU est un seul camion de livraison, le GPU est une flotte de milliers de petits drones ultra-rapides.

L'analogie : Au lieu d'un seul camion transportant une boîte à la fois, le GPU peut transporter des milliers de boîtes simultanément.
L'outil : Ils ont utilisé un langage de programmation appelé OpenACC. Considérez cela comme une télécommande universelle. Au lieu de réécrire tout le manuel d'instructions pour les drones (ce qui serait difficile et sujet aux erreurs), ils ont simplement pointé la télécommande vers les instructions existantes du camion et ont dit : « Hé, fais ça aussi, mais plus vite ! » Cela a permis de mettre à jour le logiciel facilement sans le casser.

3. Le Goulot d'Étranglement : Le générateur de "Bruit"

Dans ce chiffrement, vous avez besoin de beaucoup de "bruit" aléatoire pour rendre le puzzle difficile.

L'ancienne méthode : Le CPU générait le bruit, l'écrivait, puis le transportait vers le GPU. C'était comme si le chauffeur du camion s'arrêtait pour écrire une liste de courses, allait au magasin, achetait les articles, puis revenait en conduisant. Cela gaspillait énormément de temps.
La correction : Ils ont installé un "générateur de bruit" directement à l'intérieur de l'entrepôt du GPU. Désormais, les drones peuvent générer leur propre bruit aléatoire sur place. Ils n'ont plus besoin d'attendre que le camion leur apporte. Cela a réduit considérablement le temps d'attente.

4. L'astuce du "Batching" (Traitement par lots)

Le processus de chiffrement consiste à résoudre 256 petits puzzles à la fois (un pour chaque bit d'un message).

L'ancienne méthode : Le GPU résolvait un puzzle, s'arrêtait, attendait des instructions, résolvait le suivant, s'arrêtait, attendait... comme un chef cuisinier préparant un œuf à la fois et attendant que la cuisinière refroidisse entre chaque œuf.
La correction : Ils ont utilisé une stratégie appelée Intra-Operation Batching. C'est comme si le chef mettait les 256 œufs dans une grande poêle à la fois et les cuisait tous ensemble. Le GPU effectue un seul grand "lancement" pour résoudre les 256 puzzles simultanément, ce qui permet de gagner un temps précieux.

5. Les Résultats : Vitesse et Énergie

Les chercheurs ont testé cela sur différents types d'ordinateurs ultra-rapides (GPU) et les ont comparés à l'ancienne méthode CPU.

Vitesse : Sur l'ordinateur le plus récent et le plus puissant qu'ils aient testé (le Grace Hopper Superchip), leur nouvelle méthode était 208 fois plus rapide que l'ancienne méthode CPU.
- Analogie : Si l'ancien camion mettait 3 heures pour livrer un colis, la nouvelle flotte de drones le fait en moins d'une minute.
- Ils ont même pu résoudre des tailles de puzzles si énormes que l'ancien CPU aurait manqué de mémoire et aurait planté.
Énergie : La nouvelle méthode consomme également moins d'énergie. Le Grace Hopper a utilisé environ la moitié de l'énergie pour faire le même travail par rapport à un ordinateur standard doté d'un autre type de GPU rapide.
- Analogie : C'est comme effectuer la même livraison en utilisant une voiture hybride plutôt qu'un camion gourmand en essence.

6. Pourquoi c'est important

Ce document montre qu'en utilisant ces "drones" (GPU) et des astuces de gestion intelligentes (OpenACC, batching et bruit sur l'appareil), nous pouvons rendre ces verrous ultra-sécurisés et résistants au quantique utilisables en pratique. Sans ces accélérations, la mathématique est trop lente pour être utile dans le monde réel. Avec elles, nous pouvons sécuriser nos données contre les futurs ordinateurs quantiques sans attendre des jours pour qu'un seul verrou s'enclenche.

En bref : Ils ont pris une méthode de chiffrement lente et lourde et lui ont donné un coup de boost massif en utilisant des milliers de petits travailleurs (GPU) qui travaillent ensemble, génèrent leurs propres fournitures et ne perdent plus de temps à attendre des instructions. Le résultat est un système des centaines de fois plus rapide et beaucoup plus efficace sur le plan énergétique.

Résumé Technique : Accélération par GPU des KEM basés sur le problème Learning With Errors via OpenACC

Énoncé du Problème
L'avènement d'ordinateurs quantiques à grande échelle menace les protocoles cryptographiques asymétriques actuels (par exemple, RSA, ECC) via l'algorithme de Shor. La cryptographie post-quantique (PQC) est apparue comme une solution, les schémas basés sur les réseaux euclidiens, particulièrement ceux reposant sur le problème Learning With Errors (LWE), étant au centre des mécanismes d'encapsulation de clé (KEM). Cependant, les schémas basés sur le LWE introduisent une surcharge de calcul significative en raison des opérations matricielles à grande échelle et de la génération de nombres aléatoires, ce qui les rend souvent impraticables pour les applications serveurs à haut débit sur les architectures CPU standards. Bien que l'accélération par GPU ait été explorée pour la PQC, la plupart des implémentations existantes reposent sur des optimisations spécifiques à CUDA, ce qui limite la portabilité et la productivité des développeurs. De plus, un portage naïf échoue souvent à traiter les goulots d'étranglement tels que la latence de transfert de mémoire hôte-périphique et la sérialisation de la génération de nombres aléatoires.

Méthodologie
Les auteurs proposent un mécanisme d'encapsulation de clé (KEM) basé sur le « LWE pur » (évitant les structures algébriques supplémentaires comme le Ring-LWE) et développent une implémentation orientée GPU utilisant le modèle de programmation par directives OpenACC. Le travail suit les étapes méthodologiques suivantes :

Implémentation de Référence : Une implémentation C++ du LWE-KEM a été parallélisée en utilisant OpenMP pour les processeurs multicœurs. Le schéma utilise la transformée de Fujisaki-Okamoto (FO) pour atteindre la sécurité IND-CCA2, impliquant les phases KeyGen, Encaps et Decaps.
Portage et Optimisation OpenACC : Le code CPU a été porté sur GPU via OpenACC. Pour surmonter les goulots d'étranglement de performance, les auteurs ont mis en œuvre trois stratégies principales :
- Regroupement Intra-Opérationnel (Batching) : Au lieu de traiter les 256 bits de messages indépendants séquentiellement (déclenchant des lancements de kernels et des transferts de mémoire séparés), l'implémentation fusionne les 256 chiffrements en un seul lancement de kernel GPU. Cela expose un parallélisme fin ( $256 \times n$ éléments de travail) et amortit les frais d'invocation.
- Génération de Nombres Aléatoires Résidente sur Périphérique (RNGonGPU) : Reconnaissant que le transfert de vecteurs de bruit aléatoires via PCIe crée un goulot d'étranglement sévère, les auteurs ont intégré la bibliothèque RNGonGPU. Cette bibliothèque implémente un générateur de nombres pseudo-aléatoires déterministe (DRBG) AES-256 directement sur le GPU. Seule une graine (seed) de 64 bits est transférée de l'hôte vers le périphérique, réduisant le volume de transfert de données d'environ six ordres de grandeur par rapport au transfert de vecteurs de bruit pré-générés.
- Gestion Explicite des Données : Les auteurs ont évité la mémoire unifiée CUDA au profit de directives explicites enter data et exit data pour contrôler les transferts hôte-périphique de manière déterministe, minimisant les communications inutiles et garantissant la cohérence des données uniquement à des points de synchronisation spécifiques (par exemple, avant le hachage).
Parallélisation des Kernels : Les multiplications matrice-vecteur, qui constituent le coût de calcul dominant, ont été parallélisées de manière hiérarchique. Pour le chiffrement/déchiffrement, les chiffrements de messages indépendants sont assignés à des gangs OpenACC, tandis que les composants du texte chiffré sont calculés simultanément à travers les voies vectorielles (lanes).

Principales Contributions

Implémentation Open-Source : Les auteurs fournissent une implémentation open-source d'un KEM basé sur le LWE pur pour CPU (OpenMP) et GPU (OpenACC), permettant des benchmarks reproductibles.
Optimisation par Directives : Un ensemble d'optimisations orientées GPU applicables à une large classe de schémas LWE, démontrant que les modèles basés sur des directives (OpenACC) peuvent atteindre des performances élevées sans une expertise approfondie en CUDA.
Évaluation Complète : Une étude détaillée des performances, de l'efficacité énergétique et de la scalabilité sur plusieurs générations de GPU NVIDIA (Volta, Ampere, Hopper) et architectures (x86 + Hopper vs. puce Grace Hopper basée sur ARM).

Résultats
L'évaluation a été menée sur diverses plateformes, incluant la puce NVIDIA GH200 Grace Hopper, A100 et V100S.

Accélération (Speedup) : L'implémentation OpenACC optimisée a obtenu des accélérations significatives par rapport à la base de référence multithreadée sur CPU. Sur la plateforme GH200, les accélérations ont atteint jusqu'à 208× pour de grandes tailles de problèmes ( $n=4096$ ). L'implémentation GPU commence à surpasser la base de référence CPU pour $n \ge 256$ .
Scalabilité : L'implémentation GPU a démontré une scalabilité supérieure par rapport à la version CPU à mesure que la taille des problèmes augmentait, gérant efficacement des ensembles de paramètres (ex: $n=32768$ ) qui étaient impraticables sur CPU en raison de la contention de la mémoire et des frais de synchronisation.
Efficacité Énergétique : Sur la puce superchip GH200, l'implémentation a atteint une réduction de 1,78× de l'énergie par solution par rapport à un système x86 + H100, principalement grâce à la consommation d'énergie plus faible du CPU ARM Grace. L'amélioration du temps de résolution (time-to-solution) entre GH200 et x86+Hopper était plus modeste (1,19×).
Mise à l'échelle Architecturale : L'analyse intergénérationnelle (V100S $\to$ A100 $\to$ GH200) a révélé que la montée en performance est principalement pilotée par la bande passante de la mémoire à haute bande passante (HBM). Cependant, à mesure que la bande passante augmente, le coût relatif de la génération de matrice à la demande (coût arithmétique) et les coûts fixes de la transformée FO côté CPU commencent à limiter la montée en charge, déplaçant le goulot d'étranglement d'une limitation purement liée à la mémoire vers un mélange de contraintes de calcul et de synchronisation.
Impact de l'Optimisation : Le profilage a montré que l'implémentation naïve était dominée par le calcul côté hôte et les transferts PCIe (famine du GPU). L'implémentation optimisée a déplacé le goulot d'étranglement vers la synchronisation, avec une activité GPU soutenue à environ 98 % du temps d'itération.

Signification
L'article affirme que ses résultats soulignent l'efficacité de l'accélération GPU pour les charges de travail cryptographiques basées sur le LWE exigeantes en calcul. En exploitant OpenACC, les auteurs démontrent une voie vers une PQC de haute performance qui équilibre programmabilité et performance, évitant le besoin de codage CUDA de bas niveau. Le travail suggère qu'avec des optimisations appropriées (spécifiquement le regroupement intra-opérationnel et le RNG sur périphérique), les schémas LWE « purs » — qui offrent des hypothèses de sécurité plus conservatrices mais des coûts de calcul plus élevés — peuvent devenir pratiques sur les plateformes hétérogènes modernes. L'étude souligne également l'importance de la co-optimisation de l'ensemble du pipeline hétérogène, car les opérations côté CPU et les interconnexions contraignent de plus en plus la scalabilité dans les architectures de nouvelle génération. Des travaux futurs sont proposés pour étendre cette approche aux environnements multi-GPU et à d'autres architectures d'accélérateurs (AMD, Intel).