TL;DR
This paper presents "Saber+", a memory-optimized version of the Saber post-quantum cryptography (PQC) scheme, specifically designed for resource-constrained RISC-V microcontrollers. By introducing novel generation strategies for public matrices and secret vectors, and carefully optimizing the Number Theoretic Transform (NTT) implementation, they achieve significant speedups and drastically reduced memory footprints, making PQC feasible on devices with as little as 16KB of RAM.
What Problem Does This Paper Address?
The NIST Post-Quantum Cryptography (PQC) standardization process is nearing completion, leading to a growing need to deploy these advanced cryptographic schemes on the vast array of Internet of Things (IoT) devices. However, many IoT devices, particularly those in Wireless Sensor Networks (WSNs), are severely limited in resources, possessing only a few kilobytes of RAM and operating at low frequencies. The Saber PQC scheme, while a finalist in the NIST process, is computationally intensive and requires significant memory for its matrix and vector operations, posing a major challenge for these constrained environments. Existing optimizations for Saber often focus on speed at the expense of memory, or vice-versa, leading to suboptimal solutions for memory-limited platforms. This paper aims to bridge this gap by developing an efficient Saber implementation tailored for memory-constrained RISC-V microcontrollers, exploring the critical time-memory trade-offs involved.
Methods
The authors introduce "Saber+", a modified Saber protocol, with several key innovations:
- Optimized NTT Implementation: Saber's original polynomial multiplication used Toom-Cook-Karatsuba, which is memory-intensive. The paper leverages the Number Theoretic Transform (NTT) for faster polynomial multiplication. Crucially, they explore and compare various "incomplete-NTTs" (e.g., 7-layer, 6-layer, 5-layer) against the complete NTT, finding that the 6-layer NTT offers the best performance on their target platform due to efficient layer merging and register utilization.
- On-the-fly Generation Strategies:
- On-the-fly GenS: This technique allows the secret vector
sto be generated only when needed, significantly reducing memory requirements by storing only one polynomial at a time instead of the entire vector.
- On-the-fly GenS: This technique allows the secret vector
- On-the-fly GenA & Out-of-order GenA: Building on prior work, they simplify the generation of the public matrix
Aby optimizing how leftover random data is handled. They also introduce an "out-of-order GenA" which allows for more flexible matrix generation, enabling better time-memory trade-offs when combined with on-the-fly GenS. - Three Memory-Optimized Strategies: Based on the above techniques, they propose three distinct strategies for computing matrix-vector multiplication, each offering a different balance between speed and memory usage, catering to the specific needs of different Saber variants (LightSaber+, Saber+, FireSaber+).
- Platform-Specific Optimizations: The implementation is tailored for the SiFive Freedom E310 RISC-V core, a real-world memory-constrained microcontroller. This includes careful register allocation, instruction selection, and leveraging features like the Instruction Tightly Integrated Memory (ITIM).
Datasets
Not discussed in the paper. The paper focuses on algorithm implementation and performance evaluation on a specific hardware platform and simulated environments.
Key Insights and Ideas
- Incomplete-NTTs are Key: The paper demonstrates that for specific moduli and polynomial degrees, incomplete NTTs can outperform the complete NTT, especially when considering the overhead of base multiplication. This is a crucial insight for optimizing NTT-based cryptography on constrained devices.
- Layer Merging Matters: The efficiency of NTT is not just about the transform itself but how layers are merged. The authors show that 3-layer merging in the 6-layer NTT is more efficient on their RISC-V platform than 4-layer merging in the 8-layer complete NTT due to better register utilization.
- On-the-fly Generation is Crucial for Memory: The "on-the-fly" generation of both the public matrix and secret vector is essential for drastically reducing memory footprints, enabling Saber to fit within the tight constraints of IoT devices.
- RISC-V is a Viable Platform for PQC: The paper highlights that with careful optimization, PQC schemes like Saber can be efficiently implemented on resource-constrained RISC-V architectures, paving the way for their widespread adoption.
- Time-Memory Trade-offs are Granular: The authors present three distinct strategies, showing that there isn't a single "best" solution, but rather a spectrum of options that can be chosen based on the specific memory and performance requirements of the target application.
Key Results
- Significant Speedup: The optimized Saber+ implementation on the SiFive E310 RISC-V platform achieves a 48% performance improvement compared to the best known memory-optimized implementation of the original Saber.
- Drastic Memory Reduction: The implementation consumes at most 4.8KB of stack, fitting within the 16KB RAM constraint of the target microcontroller.
- Efficient Key Operations: Key generation, encapsulation, and decapsulation take 3,809K, 3,594K, and 3,193K clock cycles, respectively.
- Competitive Performance on Other Platforms: The implementation also shows significant speedups and reduced stack usage compared to previous works on simulated RISC-V (PQRISCV) and Cortex-M4 platforms. For instance, on Cortex-M4, their implementation is 1.48-1.72 times faster than a highly optimized NTT-based Saber implementation from prior work, while using significantly less stack.
Limitations and Future Work
- Compatibility with Original Saber: The proposed "Saber+" modifications, particularly the generation strategies, are not directly compatible with the known-answer-tests (KAT) vectors of the original Saber submission. While this doesn't affect security, it means direct comparison with original Saber KATs is not possible.
- Hardware Random Number Generator: The SiFive E310 platform lacks a hardware random number generator, requiring the use of AES_CTR for seed generation. The authors note that removing AES_CTR can further improve performance on this platform.
- Future Work: The authors suggest that their modular implementation allows users to apply the proposed strategies to different variants of Saber+ to achieve desired time-memory trade-offs. They also imply that further exploration of hardware/software co-design for PQC on RISC-V could yield even greater benefits.
Summary updated