[en] Introduced in 1996, NTRUEncrypt is not only one of the earliest but also one of the most scrutinized lattice-based cryptosystems and expected to remain secure in the upcoming era of quantum computing. Furthermore, NTRUEncrypt offers some efficiency benefits over “pre-quantum” cryptosystems like RSA or ECC since the low-level arithmetic operations are less computation-intensive and, thus, more suitable for constrained devices. In this paper we present AVR N TRU, a highly-optimized implementation of NTRUEncrypt for 8-bit AVR microcontrollers that we developed from scratch to reach high performance and resistance to timing attacks. AVR N TRU complies with the EESS #1 v3.1 specification and supports product-form parameter sets such as ees443ep1, ees587ep1, and ees743ep1. An entire encryption (including mask generation and blinding-polynomial generation) using the ees443ep1 parameters requires 847973 clock cycles on an ATmega1281 microcontroller; the decryption is more costly and has an execution time of 1051871 cycles. We achieved these results with the help of a novel hybrid technique for multiplication in a truncated polynomial ring, whereby one of the operands is a sparse ternary polynomial in product form and the other an arbitrary element of the ring. A constant-time multiplication in the ring given by the ees443ep1 parameters takes only 192577 cycles, which sets a new speed record for the arithmetic part of a lattice-based cryptosystem on AVR.
Research center :
Interdisciplinary Centre for Security, Reliability and Trust (SnT) > Applied Security and Information Assurance Group (APSIA)
Disciplines :
Computer science
Author, co-author :
CHENG, Hao ; University of Luxembourg > Faculty of Science, Technology and Medicine (FSTM) > APSIA
GROSZSCHÄDL, Johann ; University of Luxembourg > Faculty of Science, Technology and Medicine (FSTM) > Department of Computer Science (DCS)
ROENNE, Peter ; University of Luxembourg > Interdisciplinary Centre for Security, Reliability and Trust (SNT) > APSIA
RYAN, Peter Y A ; University of Luxembourg > Faculty of Science, Technology and Medicine (FSTM) > Department of Computer Science (DCS)
External co-authors :
no
Language :
English
Title :
AVRNTRU: Lightweight NTRU-based Post-Quantum Cryptography for 8-bit AVR Microcontrollers
Publication date :
February 2021
Event name :
2021 Design, Automation and Test in Europe Conference and Exhibition (DATE 2021)
Event place :
Grenoble, France
Event date :
2021-02-01 to 2021-02-05
Audience :
International
Main work title :
2021 Design, Automation and Test in Europe Conference and Exhibition, DATE 2021, Grenoble, France, February 1-5, 2021, Proceedings
J. Hoffstein, J. Pipher, and J. H. Silverman, "NTRU: A ring-based public key cryptosystem, " in Algorithmic Number Theory Symposium-ANTS, 1998, pp. 267-288.
Consortium for Efficient Embedded Security, "Efficient embedded security standards (EESS)#1: Implementation aspects of NTRUEncrypt (Version 3.1), " Available at http://github.com/NTRUOpenSourceProject/ntru-crypto/blob/master/doc/EESS1-v3.1.pdf, 2015.
Z. Liu, T. Pöppelmann, T. Oder, H. Seo, S. Sinha Roy, T. Güneysu, J. Großschädl, H. Kim, and I. Verbauwhede, "High-performance ideal lattice-based cryptography on 8-bit avr microcontrollers, " ACM Trans. Embed. Comput. Syst., vol. 16, no. 4, p. 117, 2017.
T. Pöppelmann, T. Oder, and T. Güneysu, "High-performance ideal lattice-based cryptography on 8-bit ATxmega microcontrollers, " in Progress in Cryptology-LATINCRYPT, 2015, pp. 346-365.
N. Gura, A. Patel, A. S. Wander, H. Eberle, and S. Chang Shantz, "Comparing elliptic curve cryptography and RSA on 8-bit CPUs, " in Cryptographic Hardware and Embedded Systems-CHES, 2004, pp. 119-132.
J. Hoffstein and J. H. Silverman, "Optimizations for NTRU, " in Public-Key Cryptography and Computational Number Theory, 2001, pp. 77-88.
WolfSSL Inc., "Quantum-Safe wolfSSL, " Available at https://www.wolfssl.com/quantum-safe-wolfssl-2/, 2015.
J. Hoffstein, J. Pipher, J. M. Schanck, J. H. Silverman, W. Whyte, and Z. Zhang, "Choosing parameters for NTRUEncrypt, " Cryptology ePrint Archive, Report 2015/708, 2015, https://eprint.iacr.org/2015/708.
J. Hoffstein, N. Howgrave-Graham, J. Pipher, and W. Whyte, "Practical lattice-based cryptography: NTRUEncrypt and NTRUSign, " in The LLL Algorithm: Survey and Applications. Springer, 2010, pp. 349-390.
J. Hoffstein, J. Pipher, and J. H. Silverman, An Introduction to Mathematical Cryptography, 2nd ed., ser. Undergraduate Texts in Mathematics. Springer, 2014.
W. Dai, W. Whyte, and Z. Zhang, "Optimizing polynomial convolution for NTRUEncrypt, " IEEE Transactions on Computers, vol. 67, no. 11, pp. 1572-1583, 2018.
A. Hülsing, J. Rijneveld, J. M. Schanck, and P. Schwabe, "Highspeed key encapsulation from NTRU, " in Cryptographic Hardware and Embedded Systems-CHES, 2017, pp. 232-252.
D. V. Bailey, D. Coffin, A. J. Elbirt, J. H. Silverman, and A. D. Woodbury, "NTRU in constrained devices, " in Cryptographic Hardware and Embedded Systems-CHES, 2001, pp. 262-272.
H. Cheng, D. Dinu, and J. Großschädl, "Efficient implementation of the sha-512 hash function for 8-bit avr microcontrollers, " in Innovative Security Solutions for Information Technology and Communications, 2019, pp. 273-287.
A. Boorghany, S. Bayat Sarmadi, and R. Jalili, "On constrained implementation of lattice-based cryptographic primitives and schemes on smart cards, " ACM Trans. Embed. Comput. Syst., vol. 14, no. 3, p. 42, 2015.
O. M. Guillen, T. Pöppelmann, J. M. Bermudo Mera, E. Fuentes Bongenaar, G. Sigl, and M. J. Sepúlveda, "Towards post-quantum security for IoT endpoints with NTRU, " in Design, Automation and Test in Europe-DATE, 2017, pp. 698-703.
M. Düll, B. Haase, G. Hinterwälder, M. Hutter, C. Paar, A. H. Sánchez, and P. Schwabe, "High-speed Curve25519 on 8-bit, 16-bit and 32-bit microcontrollers, " Designs, Codes and Cryptography, vol. 77, no. 2-3, pp. 493-514, 2015.