Paper 2015/410

Efficient Ring-LWE Encryption on 8-bit AVR Processors

Zhe Liu, Hwajeong Seo, Sujoy Sinha Roy, Johann Großschädl, 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.

Metadata
Available format(s)
PDF
Publication info
Published by the IACR in CHES 2015
Keywords
Implementation - Quantum cryptography
Contact author(s)
zhe liu @ uni lu
History
2015-09-20: last of 3 revisions
2015-05-01: received
See all versions
Short URL
https://ia.cr/2015/410
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2015/410,
      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},
      howpublished = {Cryptology ePrint Archive, Paper 2015/410},
      year = {2015},
      note = {\url{https://eprint.iacr.org/2015/410}},
      url = {https://eprint.iacr.org/2015/410}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.