💻 computer science

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

This paper presents a GPU-accelerated implementation of a Learning with Errors (LWE) based Key Encapsulation Mechanism using OpenACC, demonstrating significant speedups (up to 208×) and improved energy efficiency on NVIDIA GPUs, particularly the Grace Hopper Superchip, compared to traditional CPU and H100-based systems.

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

Published 2026-06-02

📖 5 min read🧠 Deep dive

CC BY 4.0

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

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to lock a treasure chest with a key so complex that even a super-smart robot from the future (a quantum computer) couldn't pick it. This is the goal of Post-Quantum Cryptography. The specific "lock" this paper focuses on is called Learning With Errors (LWE).

Think of LWE like trying to solve a giant math puzzle where someone has intentionally added a little bit of "static" or "noise" to the signal. It's easy to make the noise, but incredibly hard to filter it out and find the original message without the secret key. The problem is, solving this puzzle on a standard computer is like trying to move a mountain one grain of sand at a time—it takes forever.

Here is what the researchers did to speed things up, explained simply:

1. The Problem: The CPU is the Slow Truck

The authors started with a version of this encryption that runs on a standard computer processor (the CPU). They found that the CPU was struggling. It was like a single delivery truck trying to move thousands of boxes. Every time it needed to move a box (a piece of data) from the warehouse (memory) to the truck bed, it had to stop, load it, and drive it. The truck was spending most of its time waiting, not working.

2. The Solution: The GPU is the Fleet of Drones

To fix this, they moved the heavy lifting to a GPU (Graphics Processing Unit). If the CPU is a single delivery truck, the GPU is a fleet of thousands of tiny, super-fast drones.

The Analogy: Instead of one truck carrying one box at a time, the GPU can carry thousands of boxes simultaneously.
The Tool: They used a programming language called OpenACC. Think of this as a universal remote control. Instead of rewriting the entire instruction manual for the drones (which would be hard and error-prone), they just pointed the remote at the existing truck instructions and said, "Hey, you do this part too, but faster!" This made it easy to upgrade the software without breaking it.

3. The Bottleneck: The "Noise" Generator

In this encryption, you need a lot of random "noise" to make the puzzle hard.

The Old Way: The CPU would generate the noise, write it down, and then drive it over to the GPU. This was like the truck driver stopping to write a shopping list, driving to the store, buying the items, and driving back. It wasted a lot of time.
The Fix: They installed a "noise generator" directly inside the GPU's warehouse. Now, the drones can generate their own random noise on the spot. They don't need to wait for the truck to bring it. This cut down the waiting time dramatically.

4. The "Batching" Trick

The encryption process involves solving 256 tiny puzzles at once (one for each bit of a message).

The Old Way: The GPU would solve one puzzle, stop, wait for instructions, solve the next, stop, wait... like a chef cooking one egg at a time and waiting for the stove to cool down between each.
The Fix: They used a strategy called Intra-Operation Batching. This is like the chef putting all 256 eggs in a giant pan at once and cooking them all together. The GPU does one big "launch" to solve all 256 puzzles simultaneously, saving a massive amount of time.

5. The Results: Speed and Energy

The researchers tested this on different types of super-fast computers (GPUs) and compared them to the old CPU method.

Speed: On the newest, most powerful computer they tested (the Grace Hopper Superchip), their new method was 208 times faster than the old CPU method.
- Analogy: If the old truck took 3 hours to deliver a package, the new drone fleet does it in less than a minute.
- They were even able to solve puzzle sizes that were so huge the old CPU would have run out of memory and crashed.
Energy: The new method also used less energy. The Grace Hopper computer used about half the energy to do the same job compared to a standard computer with a different type of fast GPU.
- Analogy: It's like getting the same delivery done but using a hybrid car instead of a gas-guzzling truck.

6. Why It Matters

The paper shows that by using these "drones" (GPUs) and smart management tricks (OpenACC, batching, and on-device noise), we can make these super-secure, quantum-proof locks practical to use. Without these speedups, the math is too slow to be useful in the real world. With them, we can secure our data against future quantum computers without waiting days for a single lock to click into place.

In short: They took a slow, heavy-lifting encryption method and gave it a massive speed boost by using thousands of tiny workers (GPUs) that work together, generate their own supplies, and stop waiting for instructions. The result is a system that is hundreds of times faster and much more energy-efficient.

Technical Summary: GPU Acceleration of Learning With Errors KEMs Using OpenACC

Problem Statement
The advent of large-scale quantum computers threatens current asymmetric cryptographic protocols (e.g., RSA, ECC) via Shor's algorithm. Post-Quantum Cryptography (PQC) has emerged as a solution, with lattice-based schemes, particularly those relying on the Learning With Errors (LWE) problem, being central to Key Encapsulation Mechanisms (KEMs). However, LWE-based schemes introduce significant computational overhead due to large-scale matrix operations and randomness generation, often rendering them impractical for high-throughput server-side applications on standard CPU architectures. While GPU acceleration has been explored for PQC, most existing implementations rely on CUDA-specific optimizations, limiting portability and developer productivity. Furthermore, naive porting often fails to address bottlenecks such as host-device memory transfer latency and serialization of random number generation.

Methodology
The authors propose a Key Encapsulation Mechanism (KEM) based on "plain" LWE (avoiding additional algebraic structures like Ring-LWE) and develop a GPU-oriented implementation using the OpenACC directive-based programming model. The work proceeds through the following methodological steps:

Baseline Implementation: A C++ implementation of the LWE-KEM was parallelized using OpenMP for multicore CPUs. The scheme utilizes the Fujisaki-Okamoto (FO) transform to achieve IND-CCA2 security, involving KeyGen, Encaps, and Decaps phases.
OpenACC Porting and Optimization: The CPU code was ported to GPUs using OpenACC. To overcome performance bottlenecks, the authors implemented three primary strategies:
- Intra-Operation Batching: Instead of processing 256 independent message bits sequentially (triggering separate kernel launches and memory transfers), the implementation fuses all 256 encryptions into a single GPU kernel launch. This exposes fine-grained parallelism ( $256 \times n$ work items) and amortizes invocation overhead.
- Device-Resident Random Number Generation (RNG): Recognizing that transferring random noise vectors over PCIe creates a severe bottleneck, the authors integrated the RNGonGPU library. This library implements an AES-256 Deterministic Random Bit Generator (DRBG) directly on the GPU. Only a 64-bit seed is transferred from host to device, reducing data transfer volume by approximately six orders of magnitude compared to transferring pre-generated noise vectors.
- Explicit Data Management: The authors avoided CUDA Unified Memory in favor of explicit enter data and exit data directives to control host-device transfers deterministically, minimizing unnecessary communication and ensuring data consistency only at specific synchronization points (e.g., before hashing).
Kernel Parallelization: Matrix-vector multiplications, the dominant computational cost, were parallelized hierarchically. For encryption/decryption, independent message encryptions were assigned to OpenACC gangs, while ciphertext components were computed concurrently across vector lanes.

Key Contributions

Open-Source Implementation: The authors provide an open-source implementation of a plain LWE-based KEM for both CPU (OpenMP) and GPU (OpenACC), enabling reproducible benchmarks.
Directive-Based Optimization: A set of GPU-oriented optimizations applicable to a broad class of LWE schemes, demonstrating that directive-based models (OpenACC) can achieve high performance without deep CUDA expertise.
Comprehensive Evaluation: A detailed study of performance, energy efficiency, and scalability across multiple NVIDIA GPU generations (Volta, Ampere, Hopper) and architectures (x86 + Hopper vs. ARM-based Grace Hopper Superchip).

Results
The evaluation was conducted on various platforms, including the NVIDIA GH200 Grace Hopper Superchip, A100, and V100S.

Speedup: The optimized OpenACC implementation achieved significant speedups over the multithreaded CPU baseline. On the GH200 platform, speedups reached up to 208× for large problem sizes ( $n=4096$ ). The GPU implementation began to outperform the CPU baseline at $n \ge 256$ .
Scalability: The GPU implementation demonstrated superior scalability compared to the CPU version as problem sizes increased, effectively handling parameter sets (e.g., $n=32768$ ) that were impractical to process on CPUs due to memory contention and synchronization overhead.
Energy Efficiency: On the GH200 Superchip, the implementation achieved a 1.78× reduction in energy-to-solution compared to an x86 + H100 system, primarily driven by the lower power consumption of the ARM-based Grace CPU. The time-to-solution improvement on GH200 vs. x86+Hopper was more modest (1.19×).
Architectural Scaling: Cross-generational analysis (V100S $\to$ A100 $\to$ GH200) revealed that performance scaling is primarily driven by High Bandwidth Memory (HBM) bandwidth. However, as bandwidth increases, the relative overhead of on-demand matrix element generation (arithmetic cost) and fixed CPU-side FO transform costs begin to limit scaling, shifting the bottleneck from purely memory-bound to a mix of compute and synchronization constraints.
Optimization Impact: Profiling showed that the naive implementation was dominated by host-side computation and PCIe transfers (GPU starvation). The optimized implementation shifted the bottleneck to synchronization, with GPU activity sustained at ~98% of iteration time.

Significance
The paper claims that its results highlight the effectiveness of GPU acceleration for computationally demanding LWE-based cryptographic workloads. By leveraging OpenACC, the authors demonstrate a path to high-performance PQC that balances programmability and performance, avoiding the need for low-level CUDA coding. The work suggests that with appropriate optimizations (specifically intra-operation batching and device-resident RNG), "plain" LWE schemes—which offer conservative security assumptions but higher computational costs—can become practical on modern heterogeneous platforms. The study also underscores the importance of co-optimizing the full heterogeneous pipeline, as CPU-side operations and interconnects increasingly constrain scalability in next-generation architectures. Future work is proposed to extend this approach to multi-GPU environments and other accelerator architectures (AMD, Intel).