2019 • In Laurent, Maryline; Giannetsos, Thanassis (Eds.) Information Security Theory and Practice, 13th IFIP WG 11.2 International Conference, WISTP 2019, Paris, France, December 11–12, 2019, Proceedings
[en] The dawning era of quantum computing has initiated various initiatives for the standardization of post-quantum cryptosystems with the goal of (eventually) replacing RSA and ECC. NTRU Prime is a variant of the classical NTRU cryptosystem that comes with a couple of tweaks to minimize the attack surface; most notably, it avoids rings with "worrisome" structure. This paper presents, to our knowledge, the first assembler-optimized implementation of Streamlined NTRU Prime for an 8-bit AVR microcontroller and shows that high-security lattice-based cryptography is feasible for small IoT devices. An encapsulation operation using parameters for 128-bit post-quantum security requires 8.2 million clock cycles when executed on an 8-bit ATmega1284 microcontroller. The decapsulation is approximately twice as costly and has an execution time of 15.6 million cycles. We achieved this performance through (i) new low-level software optimization techniques to accelerate Karatsuba-based polynomial multiplication on the 8-bit AVR platform and (ii) an efficient implementation of the coefficient modular reduction written in assembly language. The execution time of encapsulation and decapsulation is independent of secret data, which makes our software resistant against timing attacks. Finally, we assess the performance one could theoretically gain by using a so-called product-form polynomial as part of the secret key and discuss potential security implications.
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 > Interdisciplinary Centre for Security, Reliability and Trust (SNT) > Computer Science and Communications Research Unit (CSC)
Dinu, Dumitru-Daniel; Intel Corporation > Intel Product Assurance and Security (IPAS) Group
Groszschädl, Johann ; University of Luxembourg > Faculty of Science, Technology and Communication (FSTC) > Computer Science and Communications Research Unit (CSC)
Roenne, Peter ; University of Luxembourg > Interdisciplinary Centre for Security, Reliability and Trust (SNT)
Ryan, Peter ; University of Luxembourg > Faculty of Science, Technology and Communication (FSTC) > Computer Science and Communications Research Unit (CSC)
External co-authors :
yes
Language :
English
Title :
A Lightweight Implementation of NTRU Prime for the Post-Quantum Internet of Things
Publication date :
December 2019
Event name :
13th International Conference on Information Security Theory and Practice (WISTP 2019)
Event place :
Paris, France
Event date :
2019-12-11 to 2019-12-12
Audience :
International
Main work title :
Information Security Theory and Practice, 13th IFIP WG 11.2 International Conference, WISTP 2019, Paris, France, December 11–12, 2019, Proceedings
Alkim, E., Ducas, L., Pöppelmann, T., Schwabe, P.: Post-quantum key exchange-a new hope. In: Holz, T., Savage, S. (eds.) Proceedings of the 25th USENIX Security Symposium (USS 2016), pp. 327–343. USENIX Association (2016)
Bailey, D.V., Coffin, D., Elbirt, A., Silverman, J.H., Woodbury, A.D.: NTRU in constrained devices. In: Koç, Ç.K., Naccache, D., Paar, C. (eds.) CHES 2001. LNCS, vol. 2162, pp. 262–272. Springer, Heidelberg (2001).https://doi.org/10. 1007/3-540-44709-1 22
Cheng, H., Dinu, D., Großschädl, J.: Efficient implementation of the SHA-512 hash function for 8-Bit AVR microcontrollers. In: Lanet, J.-L., Toma, C. (eds.) SECITC 2018. LNCS, vol. 11359, pp. 273–287. Springer, Cham (2019). https://doi.org/10. 1007/978-3-030-12942-2 21
Cheng, H., Großschädl, J., Rønne, P.B., Ryan, P.Y.: A lightweight implementation of NTRUEncrypt for 8-bit AVR microcontrollers. In: Proceedings of the 2nd NIST PQC Standardization Conference (2019). http://csrc.nist.gov/Events/2019/second-pqc-standardization-conference
Düll, M., et al.: High-speed Curve25519 on 8-bit, 16-bit and 32-bit microcontrollers. Des. Codes Crypt. 77(2–3), 493–514 (2015)
GCC Team: AVR-GCC Wiki (2017). http://gcc.gnu.org/wiki/avr-gcc# Exceptions to the Calling Convention
Gura, N., Patel, A., Wander, A., Eberle, H., Shantz, S.C.: Comparing elliptic curve cryptography and RSA on 8-bit CPUs. In: Joye, M., Quisquater, J.-J. (eds.) CHES 2004. LNCS, vol. 3156, pp. 119–132. Springer, Heidelberg (2004). https://doi.org/10.1007/978-3-540-28632-5 9
Hankerson, D.R., Menezes, A.J., Vanstone, S.A.: Guide to Elliptic Curve Cryptography. Springer, New York (2004). https://doi.org/10.1007/b97644
Hoffstein, J., Pipher, J., Silverman, J.H.: NTRU: a ring-based public key cryptosys-tem. In: Buhler, J.P. (ed.) ANTS 1998. LNCS, vol. 1423, pp. 267–288. Springer, Heidelberg (1998). https://doi.org/10.1007/BFb0054868
Hoffstein, J., Silverman, J.H.: Optimizations for NTRU. In: Alster, K., Urbanowicz, J., Williams, H.C. (eds.) Public-Key Cryptography and Computational Number Theory, De Gruyter Proceedings in Mathematics, pp. 77–88. Walter de Gruyter (2001)
Hoffstein, J., Silverman, J.H.: Random small Hamming weight products with applications to cryptography. Discret. Appl. Math. 130(1), 37–49 (2003)
Kannwischer, M.J., Rijneveld, J., Schwabe, P.: Faster multiplication in Z2 m[x] on Cortex-M4 to speed up NIST PQC candidates. In: Deng, R.H., Gauthier-Umaña, V., Ochoa, M., Yung, M. (eds.) ACNS 2019. LNCS, vol. 11464, pp. 281–301. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-21568-2 14
Kannwischer, M.J., Rijneveld, J., Schwabe, P., Stoffelen, K.: pqm4: testing and benchmarking NIST PQC on ARM Cortex-M4. Cryptology ePrint Archive, Report 2019/844 (2019). http://eprint.iacr.org
Karatsuba, A.A., Ofman, Y.P.: Multiplication of multidigit numbers on automata. In: Soviet Physics-Doklady, vol. 7, no. 7, pp. 595–596 (1963)
Karmakar, A., Bermudo Mera, J.M., Roy, S.S., Verbauwhede, I.: Saber on ARM: CCA-secure module lattice-based key encapsulation on ARM. IACR Trans. Cryptogr. Hardw. Embed. Syst. 2018(3), 243–266 (2018)
Kaye, P.R., Laflamme, R., Mosca, M.: An Introduction to Quantum Computing. Oxford University Press, Oxford (2007)
Lyubashevsky, V., Peikert, C., Regev, O.: On ideal lattices and learning with errors over rings. Commun. ACM 60(6), 43:1–43:35 (2013)
Mariantoni, M.: Building a superconducting quantum computer. Invited presentation given at the 6th International Conference on Post-Quantum Cryptography (PQCrypto 2014), Waterloo, ON, Canada, October 2014. http://www.youtube. com/watch?v=wWHAs-HA1c
National Institute of Standards and Technology (NIST): NIST reveals 26 algorithms advancing to the post-quantum crypto ‘semifinals’. Press release (2019). http://www.nist.gov/news-events/news/2019/01/nist-reveals-26-algorithms-advancing-post-quantum-crypto-semifinals
Schanck, J.M.: Practical Lattice Cryptosystems: NTRUEncrypt and NTRUMLS. M.Sc. thesis, University of Waterloo, Waterloo, ON, Canada (2015)
Shor, P.W.: Algorithms for quantum computation: discrete logarithms and factoring. In: Proceedings of the 35th Annual Symposium on Foundations of Computer Science (FOCS 1994), pp. 124–134. IEEE Computer Society Press (1994)
Titzer, B.L., Lee, D.K., Palsberg, J.: Avrora: scalable sensor network simulation with precise timing. In: Proceedings of the 4th International Symposium on Information Processing in Sensor Networks (IPSN 2005), pp. 477–482. IEEE (2005)
Toom, A.L.: The complexity of a scheme of functional elements realizing the multiplication of integers. Soviet Math.-Doklady 4(3), 714–716 (1963)
