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.
- RISC-V: The implementation leverages the
mulh(multiply high) instruction and precomputed constants to minimize instruction counts for modular multiplication.
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