💻 computer science

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

Diese Arbeit präsentiert eine GPU-beschleunigte Implementierung eines auf Learning with Errors (LWE) basierenden Key Encapsulation Mechanism unter Verwendung von OpenACC, die signifikante Beschleunigungen (bis zu 208×) und eine verbesserte Energieeffizienz auf NVIDIA-GPUs, insbesondere dem Grace Hopper Superchip, im Vergleich zu herkömmlichen CPU- und H100-basierten Systemen demonstriert.

Ursprüngliche Autoren: Tiziana Liberati, Nitin Shukla, Matteo Barbieri, Gabriella Bettonte, Elisabetta Boella, Simone Rizzo, Daniele Gregori, Marco Pedicini

Veröffentlicht 2026-06-02

📖 5 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Tiziana Liberati, Nitin Shukla, Matteo Barbieri, Gabriella Bettonte, Elisabetta Boella, Simone Rizzo, Daniele Gregori, Marco Pedicini

Originalarbeit lizenziert unter CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dies ist eine KI-generierte Erklärung des untenstehenden Papers. Sie wurde nicht von den Autoren verfasst oder gebilligt. Für technische Genauigkeit konsultieren Sie das Originalpaper. Vollständigen Haftungsausschluss lesen

Stellen Sie sich vor, Sie versuchen, eine Schatzkiste mit einem Schlüssel zu verschließen, der so komplex ist, dass selbst ein superintelligenter Roboter aus der Zukunft (ein Quantencomputer) ihn nicht knacken könnte. Das ist das Ziel der Post-Quanten-Kryptographie. Der spezifische „Schlossmechanismus“, auf den sich dieses Paper konzentriert, wird als Learning With Errors (LWE) bezeichnet.

Betrachten Sie LWE wie den Versuch, ein riesiges mathematisches Rätsel zu lösen, bei dem jemand absichtlich ein wenig „Statik“ oder „Rauschen“ zum Signal hinzugefügt hat. Es ist einfach, das Rauschen zu erzeugen, aber unglaublich schwer, es herauszufiltern und die ursprüngliche Nachricht ohne den geheimen Schlüssel zu finden. Das Problem ist: Dieses Rätsel auf einem Standardcomputer zu lösen, ist so, als würde man versuchen, einen Berg Korn für Korn zu bewegen – es dauert ewig.

Hier ist, was die Forscher getan haben, um dies zu beschleunigen, einfach erklärt:

1. Das Problem: Die CPU ist der langsame Lastwagen

Die Autoren begannen mit einer Version dieser Verschlüsselung, die auf einem Standard-Computerprozessor (der CPU) läuft. Sie stellten fest, dass die CPU zu kämpfen hatte. Es war, als würde ein einzelner Lieferwagen versuchen, tausende von Kisten zu bewegen. Jedes Mal, wenn er eine Kiste (ein Stück Daten) vom Lager (Speicher) auf die Ladefläche des Lastwagens transportieren musste, musste er anhalten, laden und losfahren. Der Lastwagen verbrachte die meiste Zeit mit Warten, nicht mit Arbeiten.

2. Die Lösung: Die GPU ist die Flotte von Drohnen

Um dies zu beheben, verlagerten sie die schwere Arbeit auf eine GPU (Graphics Processing Unit). Wenn die CPU ein einzelner Lieferwagen ist, dann ist die GPU eine Flotte von tausenden winzigen, superschnellen Drohnen.

Die Analogie: Anstatt eines Lastwagens, der eine Kiste nach der anderen trägt, kann die GPU tausende Kisten gleichzeitig transportieren.
Das Werkzeug: Sie verwendeten eine Programmiersprache namens OpenACC. Betrachten Sie dies als eine universelle Fernbedienung. Anstatt das gesamte Handbuch für die Drohnen neu zu schreiben (was schwierig und fehleranfällig wäre), zeigten sie die Fernbedienung einfach auf die bestehenden Lastwagen-Anweisungen und sagten: „Hey, du machst diesen Teil auch, aber schneller!“ Dies machte es einfach, die Software aufzurüsten, ohne sie zu beschädigen.

3. Der Engpass: Der „Rausch“-Generator

In dieser Verschlüsselung müssen Sie viel zufälliges „Rauschen“ erzeugen, um das Rätsel schwierig zu machen.

Der alte Weg: Die CPU generierte das Rauschen, schrieb es auf und fuhr es dann zur GPU. Das war so, als ob der Lkwakfahrer anhält, um eine Einkaufsliste zu schreiben, zum Geschäft fährt, die Artikel kauft und dann zurückfährt. Das verschwendete viel Zeit.
Die Lösung: Sie installierten einen „Rauschgenerator“ direkt innerhalb des Lagers der GPU. Jetzt können die Drohnen ihr eigenes zufälliges Rauschen direkt vor Ort erzeugen. Sie müssen nicht darauf warten, dass der Lastwagen ihnen die Vorräte bringt. Dies reduzierte die Wartezeit drastisch.

4. Der „Batching“-Trick

Der Verschlüsselungsprozess beinhaltet das Lösen von 256 winzigen Rätseln gleichzeitig (eines für jedes Bit einer Nachricht).

Der alte Weg: Die GPU löste ein Rätsel, stoppte, wartete auf Anweisungen, löste das nächste, stoppte, wartete... wie ein Koch, der ein Ei nach dem anderen brät und zwischen jedem Ei darauf wartet, dass der Herd abkühlt.
Die Lösung: Sie verwendeten eine Strategie namens Intra-Operation Batching. Dies ist so, als würde der Koch alle 256 Eier gleichzeitig in eine riesige Pfanne geben und sie alle zusammen garen. Die GPU führt einen einzigen großen „Launch“ durch, um alle 256 Rätsel simultan zu lösen, was eine massive Menge an Zeit spart.

5. Die Ergebnisse: Geschwindigkeit und Energie

Die Forscher testeten dies auf verschiedenen Arten von superschnellen Computern (GPUs) und verglichen es mit der alten CPU-Methode.

Geschwindigkeit: Auf dem neuesten, leistungsstärksten Computer, den sie getestet haben (dem Grace Hopper Superchip), war ihre neue Methode 208 Mal schneller als die alte CPU-Methode.
- Analogie: Wenn der alte Lastwagen 3 Stunden brauchte, um ein Paket auszuliefern, erledigt die neue Drohnenflotte dies in weniger als einer Minute.
- Sie konnten sogar Rätselgrößen lösen, die so riesig waren, dass die alte CPU an Speichermangel gelitten und abgestürzt wäre.
Energie: Die neue Methode verbrauchte auch weniger Energie. Der Grace Hopper Computer verbrauchte etwa die halbe Energie, um dieselbe Aufgabe im Vergleich zu einem Standardcomputer mit einer anderen Art von schneller GPU zu erledigen.
- Analogie: Es ist, als würde man die gleiche Lieferung mit einem Hybridauto statt mit einem benzinfressenden Lastwagen durchführen.

6. Warum es wichtig ist

Das Paper zeigt, dass wir durch den Einsatz dieser „Drohnen“ (GPUs) und intelligenter Management-Tricks (OpenACC, Batching und On-Device-Rauschen) diese supergesicherten, quantensicheren Schlösser praktikabel machen können. Ohnd diese Geschwindigkeitssteigerungen wäre die Mathematik zu langsam, um im realen Leben nützlich zu sein. Mit ihnen können wir unsere Daten gegen zukünftige Quantencomputer absichern, ohne darauf warten zu müssen, dass ein einzelnes Schloss tagelang braucht, um einzurasten.

Kurz gesagt: Sie haben eine langsame, schwere Verschlüsselungsmethode genommen und ihr durch den Einsatz von tausenden kleinen Arbeitern (GPUs), die zusammenarbeiten, ihre eigenen Vorräte generieren und nicht auf Anweisungen warten müssen, einen massiven Geschwindigkeitsschub verliehen. Das Ergebnis ist ein System, das hunderte Male schneller und wesentlich energieeffizienter ist.

Technische Zusammenfassung: GPU-Beschleunigung von Learning With Errors KEMs mittels OpenACC

Problemstellung
Der Aufstieg großskaliger Quantencomputer bedroht aktuelle asymmetrische Kryptografieprotokolle (z. B. RSA, ECC) durch den Shor-Algorithmus. Post-Quanten-Kryptografie (PQC) hat sich als Lösung herauskristallisiert, wobei gitterbasierte Verfahren, insbesondere solche, die auf dem Problem des „Learning With Errors“ (LWE) beruhen, zentral für Key Encapsulation Mechanisms (KEMs) sind. LWE-basierte Verfahren führen jedoch aufgrund großflächiger Matrixoperationen und der Generierung von Zufallszahlen einen erheblichen Rechenaufwand ein, was sie für hochdurchsatzorientierte Serveranwendungen auf Standard-CPU-Architekturen oft unpraktikabel macht. Während die GPU-Beschleunigung bereits für PQC untersucht wurde, verlassen sich die meisten bestehenden Implementierungen auf CUDA-spezifische Optimierungen, was die Portabilität und die Produktivität der Entwickler einschränkt. Darüber hinaus scheitert eine naive Portierung oft an Engpässen wie der Latenz beim Datentransfer zwischen Host und Device sowie der Serialisierung der Zufallszahlengenerierung.

Methodik
Die Autoren schlagen einen Key Encapsulation Mechanism (KEM) vor, der auf „plain“ LWE basiert (unter Vermeidung zusätzlicher algebraischer Strukturen wie Ring-LWE), und entwickeln eine GPU-orientierte Implementierung unter Verwendung des OpenACC-direktivenbasierten Programmiermodells. Die Arbeit folgt diesen methodischen Schritten:

Baseline-Implementierung: Eine C++ Implementierung des LWE-KEM wurde für Multicore-CPUs mittels OpenMP parallelisiert. Das Schema nutzt die Fujisaki-Okamoto (FO) Transformation, um eine IND-CCA2-Sicherheit zu erreichen, was Phasen wie KeyGen, Encaps und Decaps umfasst.
OpenACC-Portierung und Optimierung: Der CPU-Code wurde mittels OpenACC auf GPUs portiert. Um Leistungsengpässe zu überwinden, implementierten die Autoren drei primäre Strategien:
- Intra-Operation Batching: Anstatt 256 unabhängige Nachrichtenbits sequenziell zu verarbeiten (was separate Kernel-Aufrufe und Datentransfers auslösen würde), fasst die Implementierung alle 256 Verschlüsselungen in einem einzigen GPU-Kernel-Aufruf zusammen. Dies ermöglicht feinkörnige Parallelität ( $256 \times n$ Work-Items) und amortisiert den Aufruf-Overhead.
- Device-Residente Zufallszahlengenerierung (RNG): In Anerkennung dessen, dass das Übertragen von Zufallsrauschvektoren über PCIe einen schweren Engpass darstellt, integrierten die Autoren die RNGonGPU-Bibliothek. Diese Bibliothek implementiert einen AES-256 Deterministic Random Bit Generator (DRBG) direkt auf der GPU. Es wird lediglich ein 64-Bit-Seed vom Host an das Device übertragen, was das Volumen des Datentransfers im Vergleich zum Übertragen vorgegenerierter Rauschvektoren um etwa sechs Größenordnungen reduziert.
- Explizites Datenmanagement: Die Autoren verzichteten auf CUDA Unified Memory zugunsten expliziter enter data- und exit data-Direktiven, um Host-Device-Transfers deterministisch zu steuern, unnötige Kommunikation zu minimieren und die Datenkonsistenz nur an spezifischen Synchronisationspunkten (z. B. vor dem Hashing) sicherzustellen.
Kernel-Parallelisierung: Matrix-Vektor-Multiplikationen, die dominierenden Rechenkosten, wurden hierarchisch parallelisiert. Für Verschlüsselung/Entschlüsselung wurden unabhängige Nachrichtenverschlüsselungen den OpenACC-Gangs zugewiesen, während die Komponenten des Chiffretextes gleichzeitig über die Vektor-Lanes berechnet wurden.

Wesentliche Beiträge

Open-Source-Implementierung: Die Autoren stellen eine Open-Source-Implementierung eines Plain-LWE-basierten KEM sowohl für CPUs (OpenMP) als als auch für GPUs (OpenACC) zur Verfügung, was reproduzierbare Benchmarks ermöglicht.
Direktivenbasierte Optimierung: Ein Satz von GPU-orientierten Optimierungen, die auf eine breite Klasse von LWE-Schemata anwendbar sind, und die demonstrieren, dass direktivenbasierte Modelle (OpenACC) eine hohe Leistung ohne tiefgreifende CUDA-Expertise erzielen können.
Umfassende Evaluierung: Eine detaillierte Untersuchung von Performance, Energieeffizienz und Skalierbarkeit über mehrere NVIDIA-GPU-Generationen (Volta, Ampere, Hopper) und Architekturen (x86 + Hopper vs. ARM-basierter Grace Hopper Superchip) hinweg.

Ergebnisse
Die Evaluierung wurde auf verschiedenen Plattformen durchgeführt, darunter der NVIDIA GH200 Grace Hopper Superchip, A100 und V100S.

Beschleunigung (Speedup): Die optimierte OpenACC-Implementierung erreichte signifikante Beschleunigungen gegenüber der Multithreading-CPU-Baseline. Auf der GH200-Plattform erreichten die Speedups bis zu 208× für große Problemgrößen ( $n=4096$ ). Die GPU-Implementierung begann bei $n \ge 256$ die CPU-Baseline zu übertreffen.
Skalierbarkeit: Die GPU-Implementierung zeigte eine überlegene Skalierbarkeit im Vergleich zur CPU-Version mit zunehmenden Problemgrößen und bewältigte effektiv Parametersätze (z. B. $n=32768$ ), die auf CPUs aufgrund von Speicherinterferenzen und Synchronisations-Overhead unpraktikabel waren.
Energieeffizienz: Auf dem GH200 Superchip erreichte die Implementierung eine 1,78-fache Reduktion der Energie pro Lösung (energy-to-solution) im Vergleich zu einem x86 + H100 System, was primär auf den geringeren Stromverbrauch des ARM-basierten Grace-CPUs zurückzuführen ist. Die Verbesserung der Zeit bis zur Lösung (time-to-solution) zwischen GH200 und x86+Hopper war mit 1,19× moderater.
Architektonische Skalierung: Eine generationsübergreifende Analyse (V100S $\to$ A100 $\to$ GH200) verdeutlichte, dass die Leistungssteigerung primär durch die Bandbreite des High Bandwidth Memory (HBM) getrieben wird. Mit steigender Bandbreite beginnen jedoch der relative Overhead der On-Demand-Generierung von Matrixelementen (arithmetischer Aufwand) und die fixen CPU-seitigen FO-Transformationskosten die Skalierung zu begrenzen, wodurch sich der Engpass von rein speichergebunden zu einer Mischung aus Rechen- und Synchronisationsbeschränkungen verschiebt.
Auswirkung der Optimierung: Das Profiling zeigte, dass die naive Implementierung von Host-seitiger Berechnung und PCIe-Transfers dominiert wurde (GPU-Starvation). Die optimierte Implementierung verschob den Engpass zur Synchronisation, wobei die GPU-Aktivität bei ca. 98 % der Iterationszeit aufrechterhalten wurde.

Bedeutung
Das Paper behauptet, dass seine Ergebnisse die Effektivität der GPU-Beschleunigung für rechenintensive LWE-basierte kryptografische Workloads hervorheben. Durch die Nutzung von OpenACC zeigen die Autoren einen Weg zu einer Hochleistungs-PQC auf, der Programmierbarkeit und Performance vereint und tiefe CUDA-Programmierung vermeidet. Die Arbeit legt nahe, dass mit angemessenen Optimierungen (insbesondere Intra-Operation Batching und Device-Residente RNG) „Plain“ LWE-Schemata – die konservative Sicherheitsannahmen, aber höhere Rechenkosten bieten – auf modernen heterogenen Plattformen praktikabel werden können. Die Studie unterstreicht zudem die Wichtigkeit der Co-Optimierung der vollständigen heterogenen Pipeline, da CPU-seitige Operationen und Interconnects in der nächsten Generation von Architekturen zunehmend die Skalierbarkeit einschränken. Als zukünftige Arbeit wird vorgeschlagen, diesen Ansatz auf Multi-GPU-Umgebungen und andere Beschleunikertools (AMD, Intel) auszuweiten.