Efficient ring-LWE encryption on 8-bit AVR processors

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Authors

  • Zhe Liu
  • Hwajeong Seo
  • Johann Großschädl
  • Howon Kim
  • Ingrid Verbauwhede

Colleges, School and Institutes

External organisations

  • Luxembourg University
  • Pusan National University
  • Catholic University of Leuven

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. 2M, 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.

Details

Original languageEnglish
Title of host publicationCryptographic Hardware and Embedded Systems - CHES 2015
Subtitle of host publication17th International Workshop, Saint-Malo, France, September 13-16, 2015, Proceedings
EditorsTim Güneysu, Helena Handschuh
Publication statusPublished - 1 Sep 2015
EventInternational Workshop on Cryptographic Hardware and Embedded Systems, CHES 2015 - Saint-Malo, France
Duration: 13 Sep 201516 Sep 2015

Publication series

NameLecture Notes in Computer Science
PublisherSpringer
Volume9293
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

ConferenceInternational Workshop on Cryptographic Hardware and Embedded Systems, CHES 2015
Country/TerritoryFrance
CitySaint-Malo
Period13/09/1516/09/15

Keywords

  • Discrete Gaussian sampling, Number-theoretic transform, Public-key encryption, Ring learning with errors (Ring-LWE)