TL;DR
This paper presents the first systematic, high-performance implementation of the Classic McEliece post-quantum cryptography algorithm on NVIDIA GPUs. By employing a novel "CPU-GPU" heterogeneous approach and optimizing core operations like Additive FFT (AFFT) and Transpose AFFT (TAFFT) with strategies like kernel fusion and memory access stepping, the authors achieve significant speedups, making this secure cryptographic scheme more practical for high-throughput applications.
What Problem Does This Paper Address?
The advent of quantum computers poses a significant threat to current asymmetric cryptography like RSA and ECC. Post-Quantum Cryptography (PQC) aims to develop algorithms resistant to quantum attacks. Classic McEliece is a promising PQC candidate, known for its robust security guarantees, but its practical deployment is hindered by its exceptionally large public and secret keys, leading to high computational costs. While GPUs offer massive parallelism well-suited for such large data structures and high-throughput tasks, a systematic and optimized implementation of Classic McEliece on GPUs has been lacking. This paper addresses this gap by developing and evaluating a highly efficient GPU implementation.
Methods
The authors introduce a "CPU-GPU" heterogeneous computing approach. Key generation is performed on the CPU, and public keys are transferred to the GPU's global memory. Each GPU thread then independently handles a full encapsulation or decapsulation operation, a coarse-grained parallelism strategy that minimizes inter-thread communication and global memory accesses.
Key optimizations include:
- Kernel Fusion: Combining multiple operations into a single GPU kernel to reduce overhead.
- Memory Access Optimization:
- MASS (Memory Access Stepping Strategy): A novel strategy for TAFFT that optimizes memory access patterns by viewing the computation as a stepping chain, improving cache hit rates.
- LFMASS (Layer-Fused Memory Access Stepping Strategy): An extension of MASS that fuses layers of the TAFFT and AFFT computations to further reduce complexity and improve performance, addressing the verbosity of pure MASS.
- Core Operation Optimization:
- AFFT and TAFFT: These core components of Classic McEliece decryption are optimized using the developed MASS and LFMASS strategies.
- Data Conversion: Optimized for efficiency between different data representations.
- Data Type Optimization: Investigating the impact of
uint32_tvs.uint64_tfor memory alignment and performance on GPUs, selecting the most efficient type per parameter set.
Datasets
Not discussed in the paper. The paper focuses on implementing and evaluating an existing cryptographic algorithm rather than training a model on a dataset.
Key Insights and Ideas
- GPU Suitability: GPUs are a natural fit for Classic McEliece due to their massive parallelism and large global memory, which can accommodate the algorithm's large keys.
- Memory Access is Key: The primary bottleneck for Classic McEliece on GPUs is not raw computation but efficient memory access. Strategies like MASS and LFMASS are crucial for unlocking performance.
- Layer Fusion for Simplicity and Speed: LFMASS offers a compelling balance between the performance gains of MASS and the complexity of its implementation, making it a practical choice.
- Heterogeneous Computing is Practical: Offloading key generation to the CPU while leveraging the GPU for high-throughput encapsulation/decapsulation is an effective hybrid approach.
- Parameter Set Matters: The choice of data types (
uint32_tvs.uint64_t) and specific layer fusion schemes can significantly impact performance, requiring careful tuning for different McEliece parameter sets.
Key Results
The paper reports significant performance improvements:
- Encapsulation: Achieved up to 28,628,195 ops/s for McEliece348864.
- Decapsulation: Achieved up to 3,051,701 ops/s for McEliece348864.
- Comparison to CPU: The GPU implementation offers up to 344x higher encapsulation and 125x higher decapsulation performance compared to the official CPU-based AVX implementation.
- MASS/LFMASS Speedup: LFMASS achieved up to 38.37% improvement in decapsulation over the native GPU implementation for McEliece6960119.
- Scalability: The implementation demonstrates good scalability across different NVIDIA GPU architectures (RTX 2080 Ti, Titan V, RTX 3090, RTX 4090).
Limitations and Future Work
- Verbosity of MASS: The authors note that the pure MASS implementation is verbose and increases compilation burden, motivating the development of LFMASS.
- Comparison Nuances: Direct comparison of latency with CPU implementations is challenging due to differences in how GPU batch processing and kernel launch overhead are accounted for.
- Future Work: The authors suggest further investigation into fine-grained parallelism strategies and exploring other layer fusion schemes for even higher performance. They also aim to adapt their work to other GPU platforms and potentially other PQC algorithms.
Summary updated