A fast NTRU software implementation based on 5-way TMVP

Date

2024-03-01

Author

Yaman Gökce, Neslihan
Gökce, Anıl Burak
Cenk, Murat

Metadata

Show full item record

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

Item Usage Stats

139
views

0
downloads

Cite This

The fast and efficient operation of post-quantum cryptographic algorithms has become an important research topic, especially with the recent developments and the process of the PQC Standardization Project by NIST. Various algorithms based on lattices are chosen to be finalists in this project. Number Theoretic Transform (NTT), Toom–Cook, Karatsuba, and Toeplitz matrix–vector product (TMVP) are considered in order to efficiently perform multiplications in quotient polynomial rings required by the cryptographic schemes based on lattices. In this paper, we propose a 5-way split TMVP-based algorithm for multiplication in polynomial quotient rings and determine its computational complexity. The new algorithm is derived from a 5-term polynomial multiplication algorithm using 13 multiplications with coefficients of only 1 or -1 that provide efficiency. We also implement it for all parameter sets of NTRU. The results show that we have up to 34%, 35%, and 157% speed-up against Toom4-Karatsuba implementation in key generation, encapsulation, and decapsulation, respectively.

Subject Keywords

Lattice-based cryptography, NTRU, Polynomial multiplication, Post-quantum cryptography, TMVP, Toeplitz matrices

URI

https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85183340286&origin=inward
https://hdl.handle.net/11511/108671

Collections

Graduate School of Applied Mathematics, Article