Paper published in a book (Scientific congresses, symposiums and conference proceedings)
Efficient Ring-LWE Encryption on 8-bit AVR Processors
LIU, Zhe; Seo, Hwajeong; Roy, Sujoy Sinhaet al.
2015 • In Güneysu, Tim; Handschuh, Helena (Eds.) Cryptographic Hardware and Embedded Systems - CHES 2015, 17th International Workshop, Saint-Malo, France, September 13-16, 2015, Proceedings
Post-Quantum Cryptography; Public-Key Encryption; Ring Learning With Errors (Ring-LWE); Number-Theoretic Transform; Discrete Gaussian Sampling
Abstract :
[en] 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.
Disciplines :
Computer science
Author, co-author :
LIU, Zhe ; University of Luxembourg > Faculty of Science, Technology and Communication (FSTC) > Computer Science and Communications Research Unit (CSC)
Seo, Hwajeong; Pusan National University > School of Computer Science and Engineering
Roy, Sujoy Sinha; Katholieke Universiteit Leuven - KUL > Department of Electrical Engineering
GROSZSCHÄDL, Johann ; University of Luxembourg > Faculty of Science, Technology and Communication (FSTC) > Computer Science and Communications Research Unit (CSC)
Kim, Howon; Pusan National University > School of Computer Science and Engineering
Verbauwhede, Ingrid; Katholieke Universiteit Leuven - KUL > Department of Electrical Engineering
External co-authors :
yes
Language :
English
Title :
Efficient Ring-LWE Encryption on 8-bit AVR Processors
Publication date :
September 2015
Event name :
17th Workshop on Cryptographic Hardware and Embedded Systems (CHES 2015)
Event place :
Saint-Malo, France
Event date :
from 14-09-2015 to 16-09-2015
Audience :
International
Main work title :
Cryptographic Hardware and Embedded Systems - CHES 2015, 17th International Workshop, Saint-Malo, France, September 13-16, 2015, Proceedings