Cryptology ePrint Archive: Report 2022/300

Faster NTRU on ARM Cortex-M4 with TMVP-based multiplication

Irem Keskinkurt Paksoy and Murat Cenk

Abstract: The Number Theoretic Transform (NTT), Toom-Cook, and Karatsuba are the most commonly used algorithms for implementing lattice-based ?nalists of the NIST PQC competition. In this paper, we propose Toeplitz matrix-vector product (TMVP) based algorithms for multiplication for all parameter sets of NTRU. We implement the pro- posed algorithms on ARM Cortex-M4. The results show that TMVP- based multiplication algorithms using the four-way TMVP formula are more e?cient for NTRU. Our algorithms outperform the Toom-Cook method by up to 25.3%, and the NTT method by up to 19.8%. More- over, our algorithms require less stack space than the others in most cases. We also observe the impact of these improvements on the overall performance of NTRU. We speed up the encryption, decryption, en- capsulation, and decapsulation by up to 13.7%,17.5%,3.5%, and 14.1%, respectively, compared to state-of-the-art implementation.

Category / Keywords: applications / Lattice-based, Post-quantum, ARM Cortex-M4, NTRU, Toeplitz, TMVP

Date: received 4 Mar 2022

Contact author: iremkeskinkurt at gmail com

Available format(s): PDF | BibTeX Citation

Version: 20220307:124355 (All versions of this report)

Short URL: ia.cr/2022/300


[ Cryptology ePrint archive ]