NTRU Modular Lattice Signature Scheme on CUDA GPUs

Wei Dai, John M. Schanck, Berk Sunar, William Whyte, Zhenfei Zhang

TL;DR

This paper presents a GPU-accelerated implementation of the NTRU-MLS lattice-based signature scheme, achieving significant speedups (up to 47x) by parallelizing the computationally intensive signature generation process. This work demonstrates the viability of using GPUs to enhance the performance of post-quantum cryptography, making it more practical for real-world applications.

What Problem Does This Paper Address?

The advent of quantum computers poses a significant threat to current public-key cryptography standards like RSA and ECC. Lattice-based cryptography is a leading candidate for post-quantum security, offering strong theoretical foundations. However, many lattice-based signature schemes, including NTRU-MLS, suffer from large signature sizes and, more critically, computationally expensive signature generation due to a "rejection sampling" technique. This technique is necessary to ensure transcript security by making signatures indistinguishable from a public distribution, but it can require generating many candidate signatures before a valid one is produced, leading to substantial performance slowdowns. This paper addresses this performance bottleneck by leveraging the parallel processing capabilities of Graphics Processing Units (GPUs) to accelerate NTRU-MLS signature generation.

Methods

The core of this work is the implementation of the NTRU-MLS signing algorithm on NVIDIA GPUs using the CUDA programming model. The authors identified that the repeated "attempts" to generate a valid signature, which involve polynomial operations and random number generation, are highly parallelizable.

Key methodological aspects include:

  • GPU Parallelization: The signing process (steps 2-7 of the NTRU-MLS algorithm) is offloaded to the GPU. A single CUDA kernel, GenSig, is designed to compute multiple signature attempts in parallel. Each CUDA block within the kernel performs an independent attempt.
  • CUDA Kernel Design: The GenSig kernel is optimized for performance by considering:
  • Data Types: Careful selection of data types (e.g., 8-bit signed integers for certain polynomials, 16-bit unsigned integers for ternary polynomials) to minimize memory consumption and optimize operations.
  • Memory Management: Strategic use of different GPU memory types (constant, shared, global) to minimize latency. For instance, frequently accessed polynomials like Fi and Gi are stored in constant memory, while intermediate results are placed in faster shared memory.
  • Polynomial Operations: Efficient implementation of generic polynomial multiplication and product-form polynomial multiplication, crucial for NTRU-MLS.
  • Random Number Generation: Adoption of the Salsa20 stream cipher for fast and secure random number generation on the GPU.
  • Rejection Sampling Mitigation: By generating multiple candidate signatures concurrently on the GPU, the performance penalty of rejection sampling is significantly reduced. If one attempt fails, others are still being processed in parallel.
  • CPU-GPU Workflow: A clear separation of tasks between the host (CPU) and the device (GPU). The host prepares data, launches the kernel, and retrieves the final valid signature, while the GPU performs the intensive parallel computation.

Datasets

Not discussed in the paper. The paper focuses on the implementation and performance of a cryptographic algorithm rather than training on a dataset.

Key Insights and Ideas

  • GPU Suitability for Lattice Cryptography: The paper strongly demonstrates that lattice-based cryptographic schemes, particularly those involving large vector operations and repetitive computations like NTRU-MLS, are excellent candidates for GPU acceleration.
  • Parallel Rejection Sampling: The key insight is that the inherent parallelism of GPUs can effectively mitigate the performance bottleneck caused by rejection sampling in lattice-based signatures. By performing many attempts simultaneously, the probability of finding a valid signature quickly increases.
  • Optimized Memory Hierarchy Usage: The performance gains are significantly influenced by the careful management of GPU memory. Leveraging shared and constant memory for frequently accessed data and intermediate results is crucial for achieving high throughput.
  • Trade-offs in Parameter Selection: The paper highlights how newer, more secure parameter sets for NTRU-MLS, while offering better security and smaller signatures, come with a much lower acceptance rate for rejection sampling. This makes GPU acceleration even more critical for maintaining practical signing speeds.

Key Results

The paper reports significant performance improvements for the NTRU-MLS signature generation on a NVIDIA GTX Titan X GPU:

  • Original Parameter Sets: A 2x speedup compared to a CPU implementation.
  • Revised Parameter Sets (with lower acceptance rates): Speedups ranging from 18x to 47x compared to a CPU implementation. This is particularly impressive given that these revised parameters require more aggressive rejection sampling.
  • The authors successfully tuned the CUDA implementation by adjusting grid sizes (number of blocks) to achieve optimal GPU utilization, especially for parameters with high rejection rates.

Limitations and Future Work

  • Signature Size: While the paper focuses on signing speed, it acknowledges that lattice-based schemes, including NTRU-MLS, inherently have larger signature sizes compared to RSA and ECC. This is a general characteristic of lattice-based cryptography, not a limitation of the GPU implementation itself.
  • Verification Performance: The paper primarily focuses on accelerating the signing process. The performance of signature verification is not explicitly detailed, though it is generally less computationally intensive.
  • Generalizability: While the work demonstrates success for NTRU-MLS, further research could explore GPU acceleration for other lattice-based signature schemes or cryptographic primitives.
  • Future Work: The authors suggest that further optimization of polynomial operations and memory access patterns could yield even greater performance gains. Exploring different GPU architectures and more advanced CUDA programming techniques could also be beneficial. The paper also notes that while the benefit of more compact signatures is not directly observed in their experiments, it should lead to noticeable network delay savings.

Summary updated

Abstract

In this work we show how to use Graphics Processing Units (GPUs) with Compute Unified Device Architecture (CUDA) to accelerate a lattice based signature scheme, namely, the NTRU modular lattice signature (NTRU-MLS) scheme. Lattice based schemes require operations on large vectors that are perfect candidates for GPU implementations. In addition, similar to most lattice based signature schemes, NTRU-MLS provides transcript security with a rejection sampling technique. With a GPU implementation, we are able to generate many candidates simultaneously, and hence mitigate the performance slowdown from rejection sampling. Our implementation results show that for the original NTRU-MLS parameter sets, we obtain a 2x improvement in the signing speed; for the revised parameter sets, where acceptance rate of rejection sampling is down to around 1%, our implementation can be as much as 47x faster than a CPU implementation.
BibTeX
@article{dai2016ntru,
  author = {Wei Dai and John M. Schanck and Berk Sunar and William Whyte and Zhenfei Zhang},
  title = {{NTRU Modular Lattice Signature Scheme on CUDA GPUs}},
  journal = {IACR Cryptol. ePrint Arch.},
  year = {2016},
}

Loading related content...

Figure