Yet Another Improvement of Plantard Arithmetic for Faster Kyber on Low-End 32-bit IoT Devices

Junhao Huang, Haosong Zhao, Jipeng Zhang, Wangchen Dai, Lu Zhou, Ray C. C. Cheung, Çetin Kaya Koç, Donglong Chen

TL;DR

This paper introduces a highly optimized implementation of CRYSTAL-Kyber, the new global standard for post-quantum cryptography, specifically for low-end 32-bit IoT devices (ARM Cortex-M3 and RISC-V). By refining "Plantard arithmetic" to support a 2.14× larger input range and introducing platform-specific assembly tweaks, the authors achieved record-breaking speeds and significantly reduced memory (stack) usage.

What Problem Does This Paper Address?

As quantum computers loom on the horizon, traditional encryption (like RSA and ECC) is becoming obsolete. The world is transitioning to Post-Quantum Cryptography (PQC), with CRYSTAL-Kyber selected by NIST as the primary standard for general encryption.

However, Kyber is computationally demanding. While high-end processors handle it easily, the billions of low-end 32-bit IoT devices (think smart home sensors or medical implants) struggle. These "tiny" chips often lack the powerful Single Instruction Multiple Data (SIMD) extensions found in slightly larger chips like the Cortex-M4. Previous optimizations relied heavily on those missing features, leaving a performance gap for the most resource-constrained devices.

Methods

The authors focus on optimizing the Number Theoretic Transform (NTT), the mathematical heart of Kyber, using three main strategies:

  1. Enlarged Plantard Arithmetic: Plantard arithmetic is a method for efficient modular multiplication by a constant. The authors mathematically proved that the "safe" input range for this algorithm is much larger than previously thought (at least 2.14× larger) without changing a single line of the core computation.
  2. Platform-Specific Assembly:
    • Cortex-M3: They utilized the "inline barrel shifter," which allows a shift and an addition to happen in a single clock cycle, effectively merging steps in the modular reduction process.
  3. RISC-V: They leveraged the mulh (multiply high) instruction and precomputed constants to minimize the instruction count for modular multiplication.
  4. Lazy Reduction: Because the "safe" input range of their Plantard implementation is wider, they can perform multiple additions/multiplications before needing to "reduce" the result back into a standard range. This "laziness" saves a significant number of clock cycles.
  5. Stack Optimization: They introduced "poly_half" and "polyvec_half" data structures to cache intermediate values more efficiently, reducing RAM (stack) usage by up to 28%.

Datasets

As this is an engineering and cryptography paper, "datasets" refers to the hardware platforms and software benchmarks used for evaluation:

  • ARM Cortex-M3: Evaluated on an Arduino Due (Atmel SAM3X8E).
  • RISC-V: Evaluated on a physical SiFive Freedom E310 board and the PQRISCV simulator (VexRiscv core).
  • Baseline: Compared against the state-of-the-art implementations in the PQM3 library and previous works by Denisa et al.

Key Insights and Ideas

  • The Power of Proofs: The most significant "aha moment" is that the math of Plantard arithmetic was already capable of more; it just needed a more rigorous proof to unlock a wider input range. This wider range is what directly enables "lazier" (and thus faster) NTT implementations.
  • SIMD isn't Everything: While the Cortex-M4 is faster due to SIMD, the authors show that by exploiting the specific quirks of the M3 (like the barrel shifter) and RISC-V, they can make these lower-end chips surprisingly competitive.
  • Memory-Speed Trade-offs: In the IoT world, RAM is often tighter than CPU cycles. The authors' strategy to halve the cache size for intermediate terms proves that you can achieve high speed without ballooning the memory footprint.

Key Results

The optimizations set new speed records for Kyber on these platforms:

  • NTT/INTT Speedups: Achieved speedups of 26% to 55% across Cortex-M3 and RISC-V platforms compared to previous state-of-the-art work.
  • Overall Kyber Performance: The "speed-version" of Kyber outperformed the standard PQM3 library by roughly 3.4% to 5.6% on Cortex-M3 and by up to 31% on RISC-V.
  • Memory Efficiency: Reduced stack usage by 23.5% to 28.3% for high-speed implementations, making Kyber feasible for devices with as little as 16KiB of RAM.

Limitations and Future Work

  • Kyber-90s: The "90s" variant of Kyber (which uses AES instead of SHAKE) remains slow on these platforms because they lack hardware AES acceleration.
  • Dilithium: The techniques used here for 16-bit modular arithmetic don't translate directly to CRYSTAL-Dilithium (a digital signature standard), which uses a 32-bit modulus. The authors suggest that 64-bit platforms would be needed to apply similar Plantard optimizations to Dilithium.
  • Side-Channel Attacks: While the implementation is constant-time (protecting against timing attacks), the authors note that further research is needed to protect against power analysis attacks on these specific low-end microcontrollers.

Summary updated

Abstract

In 2022, the National Institute of Standards and Technology (NIST) made an announcement regarding the standardization of Post-Quantum Cryptography (PQC) candidates. Out of all the Key Encapsulation Mechanism (KEM) schemes, the CRYSTAL-Kyber emerged as the sole winner. This paper presents another improved version of Plantard arithmetic that could speed up Kyber implementations on two low-end 32-bit IoT platforms (ARM Cortex-M3 and RISC-V) without SIMD extensions. Specifically, we further enlarge the input range of the Plantard arithmetic without modifying its computation steps. After tailoring the Plantard arithmetic for Kyber’s modulus, we show that the input range of the Plantard multiplication by a constant is at least ${2.14\times }$ larger than the original design in TCHES2022. Then, two optimization techniques for efficient Plantard arithmetic on Cortex-M3 and RISC-V are presented. We show that the Plantard arithmetic supersedes both Montgomery and Barrett arithmetic on low-end 32-bit platforms. With the enlarged input range and the efficient implementation of the Plantard arithmetic on these platforms, we propose various optimization strategies for NTT/INTT. We minimize or entirely eliminate the modular reduction of coefficients in NTT/INTT by taking advantage of the larger input range of the proposed Plantard arithmetic on low-end 32-bit platforms. Furthermore, we propose two memory optimization strategies that reduce 23.50%~28.31% stack usage for the speed-version Kyber implementation when compared to its counterpart on Cortex-M4. The proposed optimizations make the speed-version implementation more feasible on low-end IoT devices. Thanks to the aforementioned optimizations, our NTT/INTT implementation shows considerable speedups compared to the state-of-the-art work. Overall, we demonstrate the applicability of the speed-version Kyber implementation on memory-constrained IoT platforms and set new speed records for Kyber on these platforms.
BibTeX
@article{huang2024yet,
  author = {Junhao Huang and Haosong Zhao and Jipeng Zhang and Wangchen Dai and Lu Zhou and Ray C. C. Cheung and Çetin Kaya Koç and Donglong Chen},
  title = {{Yet Another Improvement of Plantard Arithmetic for Faster Kyber on Low-End 32-bit IoT Devices}},
  journal = {IEEE Trans. Inf. Forensics Secur.},
  year = {2024},
  url = {https://openreview.net/forum?id=iMnjFzrvQp},
}

Loading related content...

Figure