Introduction
The advent of quantum computing poses a significant threat to modern cryptographic standards. Current public-key infrastructures, primarily based on RSA and Elliptic Curve Cryptography (ECC), are vulnerable to Shor's algorithm. While the cryptographic community is actively standardizing Post-Quantum Cryptography (PQC), many leading candidates are optimized for high-performance servers or personal computers.
Internet of Things (IoT) devices, such as smart sensors and embedded controllers, present a unique challenge. These devices typically operate with extremely limited SRAM and processing power. The original "Lizard" scheme showed promise but relied on large matrices that exceeded the storage and computational capacities of many 32-bit microcontrollers. To address this, we propose RLizard, a ring-based evolution of the Lizard scheme designed specifically for resource-constrained IoT environments.
The RLizard Framework
RLizard shifts the mathematical foundation from standard Learning With Errors (LWE) to Ring Learning With Errors (RLWE) and Ring Learning With Rounding (RLWR). By utilizing polynomials over a power-of-two cyclotomic ring ($X^n + 1$), RLizard significantly reduces key sizes and computational overhead.
A key innovation in RLizard is the use of Learning With Rounding (LWR). Unlike LWE, which requires adding explicit Gaussian noise during encryption, LWR uses deterministic rounding. This eliminates the need for high-quality random number generation during the encapsulation phase, further reducing the computational burden on the IoT device.
The protocol follows a standard KEM structure, as shown in the figure above. To achieve IND-CCA security (security against chosen-ciphertext attacks), RLizard employs a variant of the Fujisaki-Okamoto transformation, making it suitable for robust authentication and secure communication.
Implementation and Optimization
To maximize performance on 32-bit ARM hardware, specifically the ARM Cortex-M3, several software-level optimizations were implemented:
- Delayed Reduction: In polynomial multiplication, modular reduction is a costly operation. RLizard implementations delay this reduction, performing it only once at the end of a loop rather than after every addition, saving thousands of clock cycles.
- Loop Unrolling: By manually expanding loops in the source code, the authors reduced the overhead associated with branch instructions and loop counters.
- 16-bit Word Exploitation: Coefficients are represented using the most significant bits of 16-bit words. This allows standard integer overflows in C to handle modular arithmetic implicitly, removing the need for explicit
mod qoperations. - Public Key Compression: To minimize bandwidth, RLizard transmits a 256-bit random seed instead of full polynomial coefficients. The receiver then uses this seed to regenerate the necessary polynomials.
Performance Evaluation
The proposed scheme was benchmarked against prominent NIST PQC candidates, including Kyber, NewHope, Frodo, Saber, and NTRU, on an Atmel SAM3X8E (ARM Cortex-M3) microcontroller.
The results demonstrate that RLizard is the fastest PQC candidate in this environment. Specifically, RLizard104 (providing approximately 104 bits of quantum security) required the fewest clock cycles for key generation, encapsulation, and decapsulation. When compared to Kyber, a top NIST finalist, RLizard achieved a 30.5% reduction in clock cycles for key generation and a 40.6% reduction for encapsulation.
Furthermore, RLizard proved to be highly energy-efficient. In a power consumption model where energy is proportional to clock cycles, RLizard outperformed "heavy" lattice-based schemes like Frodo by nearly an order of magnitude. The private key size is also remarkably compact at just 401 bytes, facilitating storage in limited non-volatile memory.
Conclusion
RLizard represents a significant step forward in securing the IoT ecosystem against quantum threats. By combining the mathematical efficiency of ring-based structures with aggressive software optimizations, it provides a high-performance KEM that fits within the tight constraints of 32-bit microcontrollers. While the aggressive loop unrolling results in a slightly larger code footprint (~18 KB), the gains in speed and energy efficiency make it an ideal candidate for battery-powered endpoint devices. Future research will focus on hardening these optimizations against side-channel attacks to ensure comprehensive security in physically accessible environments.
Summary updated