Cryptology ePrint Archive: Report 2015/410

Efficient Ring-LWE Encryption on 8-bit AVR Processors

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

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 590k, 672k, and 276k 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.2M, 2.6M, and 686k 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.

Category / Keywords: Implementation - Quantum cryptography

Original Publication (in the same form): IACR-CHES-2015

Date: received 30 Apr 2015, last revised 20 Sep 2015

Contact author: zhe liu at uni lu

Available format(s): PDF | BibTeX Citation

Version: 20150920:164135 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]