Efficient Ring-LWE Encryption on 8-bit AVR Processors

Zhe Liu, Hwajeong Seo, Sujoy Sinha Roy, Johann Großschädl, Howon Kim, Ingrid Verbauwhede

TL;DR

This paper presents a highly optimized implementation of the Ring-LWE encryption scheme for resource-constrained 8-bit AVR microcontrollers. By introducing novel techniques for polynomial multiplication, modular reduction, and Gaussian sampling, the authors achieve significant speedups, setting new performance records for post-quantum cryptography on this platform and outperforming traditional RSA and ECC implementations.

What Problem Does This Paper Address?

The advent of quantum computing poses a significant threat to current public-key cryptosystems, which rely on problems like integer factorization and discrete logarithms that quantum computers could solve efficiently. Lattice-based cryptography, particularly the Learning With Errors (LWE) problem and its ring variant (Ring-LWE), is a promising candidate for post-quantum security due to its presumed resistance to quantum attacks. However, implementing these schemes, especially on resource-constrained embedded systems like 8-bit AVR microcontrollers (common in the Internet of Things), presents a substantial challenge. These devices have limited processing power, memory, and energy, making it difficult to run complex cryptographic algorithms. This paper addresses the need for efficient Ring-LWE implementations on such platforms, aiming to enable secure communication in the growing landscape of IoT devices.

Methods

The authors introduce several key optimizations to the Ring-LWE encryption scheme for 8-bit AVR processors:

  • Number Theoretic Transform (NTT) Optimizations:
    • Move-and-Add (MA) Coefficient Multiplication: A novel technique to speed up coefficient multiplication by rescheduling byte multiplications and minimizing additions.
  • Shift-Add-Multiply-Subtract-Subtract (SAMS2) for Modular Reduction: An efficient method to perform modular reduction, reducing the number of expensive multiplication operations by utilizing shifts and additions.
  • Incomplete Modular Arithmetic: Exploiting "lazy" reduction by tolerating incompletely reduced intermediate results to minimize the number of reduction operations, leading to an average 6% saving.
  • Refined Coefficient Storage: A special method to store coefficients, reducing RAM footprint by up to 19% by efficiently packing bits.
  • Look-Up Table for Twiddle Factors: Pre-computing and storing twiddle factors in ROM (flash) to reduce on-the-fly computation and RAM usage.
  • Gaussian Sampler Optimization:
    • Byte-Wise Scanning Strategy: A technique to optimize the Knuth-Yao random walk algorithm for discrete Gaussian sampling by processing bits in byte chunks, reducing branches and improving speed.
  • Look-Up Table (LUT) in DDG Tree: Applying a LUT-based approach for faster sampling, especially for lower levels of the Gaussian distribution.
  • Pseudo-Random Number Generation (PRNG):
    • Utilizing the ATxmega's hardware AES accelerator for medium-term security, and software AES for long-term security.

The paper presents two variants for each security level: High-Speed (HS) and Memory-Efficient (ME), demonstrating trade-offs between speed and resource usage.

Datasets

Not discussed in the paper. The paper focuses on algorithmic optimizations and performance evaluation of a cryptographic scheme, rather than training on datasets.

Key Insights and Ideas

  • Post-Quantum Cryptography is Feasible on Embedded Systems: The paper demonstrates that advanced post-quantum cryptographic schemes like Ring-LWE can be implemented efficiently even on severely resource-constrained 8-bit microcontrollers, paving the way for secure IoT devices.
  • Modular Arithmetic is a Bottleneck: The research highlights that modular reduction and multiplication within the NTT are the most performance-critical operations, and significant gains can be achieved by optimizing these specific steps.
  • "Lazy" Computations Pay Off: The concept of incomplete modular arithmetic, where exact reductions are deferred, proves effective in reducing overhead and speeding up computations.
  • Memory Efficiency is Crucial: For 8-bit AVRs, RAM is a precious resource. Novel coefficient storage methods are essential to pack more data into less memory, enabling larger computations.
  • Hybrid Approaches are Effective: Combining hardware acceleration (AES) with optimized software algorithms (NTT, sampling) yields the best results for different security levels.

Key Results

The authors achieved significant performance improvements:

  • Medium-Term Security (256-bit):
    • High-Speed (HS-256): Key generation: 590k cycles, Encryption: 672k cycles, Decryption: 276k cycles.
  • Memory-Efficient (ME-256): Key generation: 1.3M cycles, Encryption: 1.5M cycles, Decryption: 673k cycles.
  • Long-Term Security (512-bit):
    • High-Speed (HS-512): Key generation: 2.2M cycles, Encryption: 2.6M cycles, Decryption: 686k cycles.

These results represent new speed records for Ring-LWE encryption on 8-bit AVR processors and are an order of magnitude faster than comparable RSA and ECC implementations on the same platform. The ME variants achieve significant RAM savings (19-21%) while maintaining competitive performance.

Limitations and Future Work

  • Limitations:
    • The paper focuses on specific parameter sets for Ring-LWE that are suitable for hardware implementations and efficient NTT computations (e.g., $q = 1 \pmod{2^n}$). More generic implementations might require different optimizations.
  • The AES accelerator on the ATxmega128A1 only supports 128-bit keys, necessitating the use of slower software AES for long-term security.
  • Future Work:
    • The authors suggest that the presented optimizations for NTT and Gaussian sampling can also be applied to speed up LWE-based signature schemes on AVR platforms.
  • Further exploration of hardware-software co-design for Ring-LWE on embedded systems.
  • Investigating the impact of these optimizations on other lattice-based cryptographic primitives.

Summary updated

Abstract

Public-key cryptography based on the “ring-variant” of the Learning with Errors (ring-LWE) problem is both efficient and believed to remain secure in a post-quantum world. In this paper, we introduce a carefully-optimized implementation of a ring-LWE encryption scheme for 8-bit AVR processors like the ATxmega128. Our research contributions include several optimizations for the Number Theoretic Transform (NTT) used for polynomial multiplication. More concretely, we describe the Move-and-Add (MA) and the Shift-Add-Multiply-Subtract-Subtract (SAMS2) technique to speed up the performance-critical multiplication and modular reduction of coefficients, respectively. We take advantage of incompletely-reduced intermediate results to minimize the total number of reduction operations and use a special coefficient-storage method to decrease the RAM footprint of NTT multiplications. In addition, we propose a byte-wise scanning strategy to improve the performance of a discrete Gaussian sampler based on the Knuth-Yao random walk algorithm. For medium-term security, our ring-LWE implementation needs 590 k, 672 k, and 276 k clock cycles for key-generation, encryption, and decryption, respectively. On the other hand, for long-term security, the execution time of key-generation, encryption, and decryption amount to 2.2 M, 2.6 M, and 686 k cycles, respectively. These results set new speed records for ring-LWE encryption on an 8-bit processor and outperform related RSA and ECC implementations by an order of magnitude.
BibTeX
@article{liu2015efficient,
  author = {Zhe Liu and Hwajeong Seo and Sujoy Sinha Roy and Johann Großschädl and Howon Kim and Ingrid Verbauwhede},
  title = {{Efficient Ring-LWE Encryption on 8-bit AVR Processors}},
  journal = {IACR Cryptol. ePrint Arch.},
  year = {2015},
}
Figure