TL;DR
This paper introduces GOLF, a novel GPU-accelerated framework that significantly boosts the performance of FALCON, a post-quantum cryptography (PQC) signature algorithm recently selected by NIST. GOLF achieves unprecedented throughput for FALCON's signature generation and verification, making PQC more practical for real-world applications.
What Problem Does This Paper Address?
The advent of quantum computers poses a significant threat to current cryptographic systems. To counter this, researchers are developing post-quantum cryptography (PQC) algorithms resistant to quantum attacks. FALCON, a lattice-based signature algorithm, has been chosen by NIST for standardization. However, PQC algorithms, including FALCON, are computationally intensive, leading to performance bottlenecks, especially in demanding environments like cloud services. This paper addresses the critical need for faster FALCON implementations to ensure its practical deployment and widespread adoption.
Methods
The authors developed GOLF, a GPU-accelerated framework for FALCON. Key methodological contributions include:
- Algorithm Porting and Modification: The FALCON code was ported to the GPU, with recursive functions refactored into iterative forms to be compatible with GPU execution models.
- Parallelization Strategies: Two parallelization strategies were explored:
- Fine-grain parallelism: Assigning multiple threads to compute parts of a single signature.
-
Coarse-grain parallelism: Assigning each thread to compute an entire signature, enabling multiple signatures to be processed concurrently. The authors found coarse-grain parallelism to be more effective for FALCON's throughput.
-
FFT/iFFT Optimization: The Fast Fourier Transform (FFT) and its inverse (iFFT) are computationally significant components of FALCON (accounting for ~48% of signature generation time). GOLF optimizes these by:
- Improving Temporal Locality: Reordering computations within the FFT/iFFT to minimize the time between accesses to related data, thereby enhancing cache utilization. This was achieved by adopting a depth-first search approach instead of the traditional breadth-first search.
- Kernel Fusion: Combining multiple GPU kernels into a single one to reduce overhead from kernel launches and global memory accesses.
Datasets
Not discussed in the paper. The paper focuses on algorithm implementation and performance evaluation on specific hardware.
Key Insights and Ideas
- GPU Acceleration is Crucial for PQC: The paper strongly advocates for GPU acceleration as a viable and necessary solution to overcome the performance limitations of PQC algorithms like FALCON.
- Coarse-grain Parallelism Wins for Throughput: For FALCON, processing entire signatures in parallel across multiple threads (coarse-grain) yields significantly higher throughput than breaking down individual signature computations (fine-grain).
- FFT/iFFT Optimization is a Bottleneck Buster: Optimizing the FFT/iFFT module, a major computational component, provides substantial performance gains, demonstrating the importance of targeting critical sub-routines.
- Temporal Locality Matters for Cache Efficiency: By carefully reordering FFT/iFFT operations to improve temporal locality, the authors achieved better cache hit rates and reduced memory access latency.
- Security is Preserved: A key point is that GOLF optimizes the engineering implementation of FALCON without altering the core algorithm's mathematical structure, thus maintaining the original security guarantees.
Key Results
GOLF achieves remarkable performance improvements on an NVIDIA RTX 4090 GPU:
- Signature Generation:
- Throughput: 420.25 kops/s.
- This represents a 58.05x improvement over the reference FALCON implementation and a 7.17x improvement over the fastest known GPU implementation.
- Signature Verification:
- Throughput: 10,311.04 kops/s.
- This is a 73.14x improvement over the reference implementation and a 3.79x improvement over the fastest known GPU implementation.
- FFT/iFFT Optimization Impact: The FFT/iFFT optimization alone increased signature generation throughput by approximately 14.51%.
- Comparison to Related Works: GOLF's performance significantly surpasses previous CPU-based FALCON implementations and competitive GPU implementations of other PQC algorithms.
Limitations and Future Work
- Side-Channel Attacks: The paper briefly discusses side-channel attacks on GPU global memory, concluding that they are not currently a practical threat due to high costs and complexity, and thus not a primary focus for security strategies. However, this could be an area for future research.
- Hardware Specificity: While the RTX 4090 is a powerful GPU, performance may vary on different hardware architectures.
- Future Work: The authors implicitly suggest that further optimization of other components of FALCON or exploring different parallelization strategies for specific hardware could yield additional gains. The paper also highlights the ongoing need for efficient PQC implementations to secure future digital infrastructure.
Summary updated