NewHope on ARM Cortex-M

6th International Conference on Security, Privacy, and Applied Cryptography Engineering, SPACE 2016 -- 14 December 2016 through 18 December 2016 -- 187579Recently, Alkim, Ducas, P¨oppelmann, and Schwabe proposed a Ring-LWE-based key exchange protocol called “NewHope” [2] and illustrated that this protocol is very efficient on large Intel processors. Their paper also claims that the parameter choice enables efficient implementation on small embedded processors. In this paper we show that these claims are actually correct and present NewHope software for the ARM Cortex-M family of 32-bit microcontrollers. More specifically, our software targets the low-end Cortex-M0 and the high-end Cortex- M4 processor from this family. Our software starts from the C reference implementation by the designers of NewHope and then carefully optimizes subroutines in assembly. In particular, compared to best results known so far, our NTT implementation achieves a speedup of almost a factor of 2 on the Cortex-M4. Our Cortex-M0 NTT software slightly outperforms previously best results on the Cortex-M4, a much more powerful processor. In total, the server side of the key exchange executes in only 1 467 101 cycles on the M0 and only 834524 cycles on the M4; the client side executes in 1 760 837 cycles on the M0 and 982 384 cycles on the M4. © Springer International Publishing AG 2016.Horizon 2020: ICT-645622 Nederlandse Organisatie voor Wetenschappelijk Onderzoek: 13114 European Commission Ege Üniversitesi: 2014-FEN-065 Behavioural Science institute, Radboud UniversityP. Schwabe?This work has been supported by T?BITAK under 2214-A Doctoral Research Program Grant and 2211-C PhD Scholarship, by Ege University under project 2014-FEN-065, by the European Commission through the Horizon 2020 program under project number ICT-645622 (PQCRYPTO), and by Netherlands Organization for Scientific Research (NWO) through Veni 2013 project 13114. Part of the work was done while Erdem Alkim was visiting Radboud University. Permanent ID of this document: c7a82d41d39c535fd09ca1b032ebca1b. Date: 2016-09-01. -