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

Abstract

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% to 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.

Introduction

As quantum computers loom on the horizon, traditional encryption methods like RSA and ECC are becoming obsolete. The global transition to Post-Quantum Cryptography (PQC) has identified CRYSTAL-Kyber as the primary standard for general encryption. However, Kyber is computationally demanding, particularly for the billions of low-end 32-bit IoT devices that lack Single Instruction Multiple Data (SIMD) extensions. This research addresses the performance gap on platforms like ARM Cortex-M3 and RISC-V by refining Plantard arithmetic to achieve record-breaking speeds and reduced memory footprints.

Methodology

The core of the optimization focuses on the Number Theoretic Transform (NTT), the mathematical heart of Kyber, through several innovative strategies:

Enlarged Plantard Arithmetic

Plantard arithmetic is an efficient method for modular multiplication by a constant. This work mathematically proves that the "safe" input range for this algorithm is at least 2.14× larger than previously thought without changing the core computation steps. This wider range directly enables "lazy reduction," where multiple operations occur before a result must be reduced back into a standard range, saving significant clock cycles.

Platform-Specific Assembly Optimizations

The implementation exploits unique architectural features of target microcontrollers:

  • ARM Cortex-M3: The authors utilized the "inline barrel shifter," allowing a shift and an addition to occur in a single clock cycle, effectively merging steps in the modular reduction process.
Efficient Plantard multiplication for Cortex-M3
  • RISC-V: The implementation leverages the mulh (multiply high) instruction and precomputed constants to minimize instruction counts for modular multiplication.
Optimized Plantard multiplication for RISC-V

Memory and Stack Optimization

To accommodate devices with limited RAM, the authors introduced "poly_half" and "polyvec_half" data structures. These structures cache intermediate values more efficiently, reducing stack usage by up to 28%.

Key Results

The proposed optimizations set new speed records for Kyber on low-end 32-bit platforms:

  • NTT/INTT Performance: Speedups of 26% to 55% were achieved across Cortex-M3 and RISC-V platforms compared to state-of-the-art implementations in the PQM3 library.
  • Overall Kyber Speed: The "speed-version" of Kyber outperformed standard libraries by up to 31% on RISC-V and roughly 5% on Cortex-M3.
  • Resource Efficiency: Stack usage was reduced by 23.5% to 28.3%, making high-speed Kyber feasible for devices with as little as 16KiB of RAM.

Conclusion and Future Work

This research demonstrates that SIMD extensions are not a prerequisite for high-performance PQC. By exploiting platform-specific quirks and providing more rigorous mathematical proofs for existing algorithms, low-end IoT devices can be secured against quantum threats. Future research will focus on accelerating the "90s" variant of Kyber and extending these 16-bit modular arithmetic optimizations to 32-bit modulus standards like CRYSTAL-Dilithium.

Summary updated

Abstract

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% to 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},
}
Figure