💻 computer science

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

Dit artikel presenteert een met GPU versnelde implementatie van een op Learning with Errors (LWE) gebaseerd Key Encapsulation Mechanism met behulp van OpenACC, die significante versnellingen (tot 208×) en verbeterde energie-efficiëntie op NVIDIA GPU's aantoont, in het bijzonder de Grace Hopper Superchip, vergeleken met traditionele CPU- en op H100 gebaseerde systemen.

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

Gepubliceerd 2026-06-02

📖 5 min leestijd🧠 Diepgaand

CC BY 4.0

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

Oorspronkelijk artikel gelicentieerd onder CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dit is een AI-gegenereerde uitleg van het onderstaande artikel. Het is niet geschreven of goedgekeurd door de auteurs. Raadpleeg het oorspronkelijke artikel voor technische nauwkeurigheid. Lees de volledige disclaimer

Stel je voor dat je een schatkist probeert te vergrendelen met een sleutel die zo complex is dat zelfs een superintelligent robot uit de toekomst (een quantumcomputer) hem niet kan kraken. Dit is het doel van Post-Quantum Cryptografie. De specifieke "slot" waar dit artikel zich op richt, wordt Learning With Errors (LWE) genoemd.

Zie LWE als het proberen op te lossen van een gigantische wiskundige puzzel waarbij iemand opzettelijk een beetje "statische ruis" of "ruis" aan het signaal heeft toegevoegd. Het is makkelijk om de ruis te maken, maar ongelooflijk moeilijk om de oorspronkelijke boodschap zonder de geheime sleutel te filteren. Het probleem is dat het oplossen van deze puzzel op een standaardcomputer is alsof je een berg probeert te verplaatsen korrel voor korrel; het duurt eeuwig.

Hier is wat de onderzoekers hebben gedaan om dit te versnellen, eenvoudig uitgelegd:

1. Het Problek: De CPU is de Langzame Vrachtwagen

De auteurs begonnen met een versie van deze encryptie die draait op een standaard computerprocessor (de CPU). Ze ontdekten dat de CPU moeite had. Het was alsof een enkele bezorgwagen probeerde duizenden dozen te verplaatsen. Elke keer als hij een doos (een stukje data) van het magazijn (geheugen) naar de laadbak van de vrachtwagen moest verplaatsen, moest hij stoppen, laden en rijden. De vrachtwagen was de meeste tijd aan het wachten, niet aan het werken.

2. De Oplossing: De GPU is de Vloot van Drones

Om dit op te lossen, verplaatsten ze het zware werk naar een GPU (Graphics Processing Unit). Als de CPU een enkele bezorgwagen is, dan is de GPU een vloot van duizenden kleine, supersnelle drones.

De Analogie: In plaats van één vrachtwagen die één doos per keer vervoert, kan de GPU duizenden dozen tegelijkertijd vervoeren.
Het Gereedschap: Ze gebruikten een programmeertaal genaamd OpenACC. Zie dit als een universele afstandsbediening. In plaats van de volledige instructiehandleiding voor de drones te herschrijven (wat moeilijk en foutgevoelig zou zijn), wezen ze de afstandsbediening gewoon op de bestaande instructies van de vrachtwagen en zeiden: "Hé, jij doet dit deel ook, maar dan sneller!" Dit maakte het gemakkelijk om de software te upgraden zonder deze te breken.

3. De Bottleneck: De "Ruis"-generator

Bij deze encryptie heb je veel willekeurige "ruis" nodig om de puzzel moeilijk te maken.

De Oude Manier: De CPU genereerde de ruis, schreef het op en reed het vervolgens naar de GPU. Dit was alsof de vrachtwagenchauffeur stopte om een boodschappenlijstje te schrijven, naar de winkel reed, de spullen kocht en weer terugreed. Dit verspilde veel tijd.
De Fix: Ze installeerden een "ruisgenerator" direct in het magazijn van de GPU. Nu kunnen de drones hun eigen willekeurige ruis ter plekke genereren. Ze hoeven niet meer te wachten tot de vrachtwagen de spullen komt brengen. Dit verminderde de wachttijd drastisch.

4. De "Batching"-truc

Het encryptieproces houdt in dat er tegelijkertijd 256 kleine puzzels worden opgelost (één voor elke bit van een boodschap).

De Oude Manier: De GPU loste één puzzel op, stopte, wachtte op instructies, loste de volgende op, stopte, wachtte... als een chef die één ei tegelijk bakt en wacht tot het fornuis afkoelt tussen elke bereiding door.
De Fix: Ze gebruikten een strategie genaamd Intra-Operation Batching. Dit is alsof de chef alle 256 eieren tegelijk in een grote pan legt en ze allemaal tegelijkertijd bakt. De GPU doet één grote "launch" om alle 256 puzzels simultaan op te lossen, wat een enorme hoeveelheid tijd bespaart.

5. De Resultaten: Snelheid en Energie

De onderzoekers testten dit op verschillende soorten supercomputers (GPU's) en vergeleken het met de oude CPU-methode.

Snelheid: Op de nieuwste, krachtigste computer die ze testten (de Grace Hopper Superchip), was hun nieuwe methode 208 keer sneller dan de oude CPU-methode.
- Analogie: Als de oude vrachtwagen 3 uur nodig had om een pakketje te bezorgen, doet de nieuwe dronevloot het in minder dan een minuut.
- Ze waren zelfs in staat om puzzelgroottes op te lossen die zo groot waren dat de oude CPU uit het geheugen zou lopen en zou crashen.
Energie: De nieuwe methode verbruikte ook minder energie. De Grace Hopper-computer gebruikte ongeveer de helft van de energie om hetzelfde werk te doen als een standaardcomputer met een ander type snelle GPU.
- Analogie: Het is alsof je dezelfde bezorging doet met een hybride auto in plaats van een benzine-verslindende vrachtwagen.

6. Waarom het ertoe doet

Het artikel laat zien dat door deze "drones" (GPU's) en slimme beheermethoden (OpenACC, batching en on-device ruis) te gebruiken, deze superveilige, quantum-bestendige sloten praktisch bruikbaar kunnen worden gemaakt. Zonder deze versnellingen is de wiskunde te traag om in de echte wereld nuttig te zijn. Met deze verbeteringen kunnen we onze gegevens beveiligen tegen toekomstige quantumcomputers zonder dagen te hoeven wachten voordat er één slot klikt.

Kortom: Ze namen een trage, zware encryptiemethode en gaven deze een enorme snelheidsslag door duizenden kleine werkers (GPU's) te gebruiken die samenwerken, hun eigen voorraden genereren en stoppen met wachten op instructies. Het resultaat is een systeem dat honderden keren sneller en veel energie-efficiënter is.

Technische Samenvatting: GPU-acceleratie van Learning With Errors KEMs met behulp van OpenACC

Probleemstelling
De komst van grootschalige quantumcomputers vormt een bedreiging voor huidige asymmetrische cryptografische protocollen (bijv. RSA, ECC) via het algoritme van Shor. Post-Quantum Cryptografie (PQC) is naar voren gekomen als een oplossing, waarbij lattice-gebaseerde schema's, in het bijzonder die die steunen op het Learning With Errors (LWE) probleem, centraal staan in Key Encapsulation Mechanisms (KEMs). LWE-gebaseerde schema's introduceren echter aanzienlijke computationele overhead door grootschalige matrixoperaties en randomiteitsgeneratie, wat ze vaak onpraktisch maakt voor high-throughput server-side applicaties op standaard CPU-architecturen. Hoewel GPU-acceleratie voor PQC al is verkend, vertrouwen de meeste bestaande implementaties op CUDA-specifieke optimalisaties, wat de portabiliteit en de productiviteit van ontwikkelaars beperkt. Bov�elijk faalt naïeve porting vaak bij het aanpakken van bottlenecks zoals latentie in host-device geheugenoverdracht en de serialisatie van random number generatie.

Methodologie
De auteurs stellen een Key Encapsulation Mechanism (KEM) voor gebaseerd op "plain" LWE (waarbij extra algebraïsche structuren zoals Ring-LWE worden vermeden) en ontwikkelen een GPU-georiënteerde implementatie met behulp van het OpenACC directive-gebaseerde programmeermodel. Het werk verloopt via de volgende methodologische stappen:

Baseline Implementatie: Een C++ implementatie van de LWE-KEM werd geparallelliseerd met behulp van OpenMP voor multicore CPU's. Het schema maakt gebruik van de Fujisaki-Okamoto (FO) transform om IND-CCA2 beveiliging te bereiken, wat de fasen KeyGen, Encaps en Decaps omvat.
OpenACC Porting en Optimalisatie: De CPU-code werd naar GPU's geport met behulp van OpenACC. Om prestatiebottlenecks te overwinnen, implementeerden de auteurs drie primaire strategieën:
- Intra-Operation Batching: In plaats van 256 onafhankelijke berichtenbits sequentieel te verwerken (wat afzonderlijke kernel-launches en geheugenoverdrachten zou triggeren), voegt de implementatie alle 256 encrypties samen in één enkele GPU kernel launch. Dit legt fijnmazige parallellisme bloot ( $256 \times n$ werkitems) en amortiseert de invocatie-overhead.
- Device-Resident Random Number Generation (RNG): In het besef dat het overdragen van random ruisvectoren over PCIe een ernstige bottleneck vormt, hebben de auteurs de RNGonGPU bibliotheek geïntegreerd. Deze bibliotheek implementeert een AES-256 Deterministic Random Bit Generator (DRBG) direct op de GPU. Alleen een 64-bit seed wordt van host naar device overgedragen, wat het volume van de dataoverdracht met ongeveer zes grootheden vermindert vergeleken met het overdragen van vooraf gegenereerde ruisvectoren.
- Expliciet Gegevensbeheer: De auteurs vermeden CUDA Unified Memory en kozen in plaats daarvan voor expliciete enter data en exit data directives om host-device overdrachten deterministisch te controleren, waardoor onnodige communicatie wordt geminimaliseerd en gegevensconsistentie wordt gewaarborgd op specifieke synchronisatiepunten (bijv. vóór hashing).
Kernel Parallellisatie: Matrix-vector vermenigvuldigingen, de dominante computationele kostenpost, werden hiërarchisch geparallelliseerd. Voor encryptie/decryptie werden onafhankelijke bericht-encrypties toegewezen aan OpenACC gangs, terwijl ciphertext componenten gelijktijdig over vector lanes werden berekend.

Belangrijkste Bijdragen

Open-Source Implementatie: De auteurs bieden een open-source implementatie van een plain LWE-gebaseerde KEM voor zowel CPU (OpenMP) als GPU (OpenACC), wat reproduceerbare benchmarks mogelijk maakt.
Directive-Based Optimalisatie: Een set GPU-georiënteerde optimalisaties die toepasbaar is op een brede klasse van LWE-schema's, waarmee wordt aangetoond dat directive-gebaseerde modellen (OpenACC) hoge prestaties kunnen leveren zonder diepe CUDA-expertise.
Uitgebreide Evaluatie: Een gedetailleerde studie van prestaties, energie-efficiëntie en schaalbaarheid over meerdere NVIDIA GPU-generaties (Volta, Ampere, Hopper) en architecturen (x86 + Hopper vs. ARM-gebaseerde Grace Hopper Superchip).

Resultaten
De evaluatie werd uitgevoerd op diverse platforms, waaronder de NVIDIA GH200 Grace Hopper Superchip, A100 en V100S.

Speedup: De geoptimaliseerde OpenACC implementatie behaalde significante speedups ten opzien van de multithreaded CPU baseline. Op het GH200 platform bereikten de speedups tot wel 208× voor grote probleemgroottes ( $n=4096$ ). De GPU implementatie begon de CPU baseline te overtreffen bij $n \ge 256$ .
Schaalbaarheid: De GPU implementatie vertoonde een superieure schaalbaarheid vergeleken met de CPU-versie naarmate de probleemgroottes toenamen, waarbij zij effectief parametersets (bijv. $n=32768$ ) kon afhandelen die onpraktisch waren voor CPU's vanwege geheugencontentie en synchronisatie-overhead.
Energie-efficiëntie: Op de GH200 Superchip bereikte de implementatie een 1.78× reductie in energy-to-solution vergeleken met een x86 + H100 systeem, primair gedreven door het lagere energieverbruik van de ARM-gebaseerde Grace CPU. De verbetering in time-to-solution van GH200 vs. x86+Hopper was met 1.19× bescheidener.
Architecturale Schaling: Cross-generationele analyse (V100S $\to$ A100 $\to$ GH200) toonde aan dat prestatieschaling primair wordt gedreven door High Bandwidth Memory (HBM) bandbreedte. Echter, naarmate de bandbreedte toeneemt, beginnen de relatieve overhead van on-demand matrix element generatie (arithmetic cost) en vaste CPU-zijde FO transform kosten de schaling te beperken, waardoor de bottleneck verschuift van puur geheugen-gebonden naar een mix van compute en synchronisatie beperkingen.
Impact van Optimalisatie: Profiling toonde aan dat de naïeve implementatie werd gedomineerd door host-zijde berekeningen en PCIe transfers (GPU starvation). De geoptimaliseerde implementatie verschoof de bottleneck naar synchronisatie, waarbij de GPU activiteit werd gehandhaafd op ~98% van de iteratietijd.

Betekenis
Het artikel beweert dat de resultaten de effectiviteit van GPU-acceleratie voor computationeel veeleisende LWE-gebaseerde cryptografische workloads onderstrepen. Door OpenACC te gebruiken, demonstreren de auteurs een pad naar high-performance PQC die een balans vindt tussen programmeerbaarheid en prestaties, zonder de noodzaak voor low-level CUDA codering. Het werk suggereert dat met passende optimalisaties (specifiek intra-operation batching en device-resident RNG), "plain" LWE-schema's — die conservatievere veiligheidsaannames bieden maar hogere computationele kosten hebben — praktisch kunnen worden op moderne heterogene platforms. De studie benadrukt ook het belang van het co-optimaliseren van de volledige heterogene pipeline, aangezien CPU-zijde operaties en interconnects in volgende generaties architecturen steeds meer de schaalbaarheid beperken. Toekomstig werk wordt voorgesteld om deze aanpak uit te breiden naar multi-GPU omgevingen en andere accelerator architecturen (AMD, Intel).