Lightweight Computational Complexity Stepping Up the NTRU Post-Quantum Algorithm Using Parallel Computing

Abstract

The Nth-degree Truncated polynomial Ring Unit (NTRU) is one of the famous post-quantum cryptographic algorithms. Researchers consider NTRU to be the most important parameterized family of lattice-based public key cryptosystems that has been established to the IEEE P1363 standards. Lattice-based protocols necessitate operations on large vectors, which makes parallel computing one of the appropriate solutions to speed it up. NTRUEncrypt operations contain a large amount of data that requires many repetitive arithmetic operations. These operations make it a strong candidate to take advantage of the high degree of parallelism. The main costly operation that is repeated in all NTRU algorithm steps is polynomial multiplication. In this work, a Parallel Post-Quantum NTRUEncrypt algorithm called PPQNTRUEncrypt is proposed. This algorithm exploits the capabilities of parallel computing to accelerate the NTRUEncrypt algorithm. Both analytical and Apache Spark simulation models are used. The proposed algorithm enhanced the NTRUEncrypt algorithm by approximately 49.5%, 74.5%, 87.6%, 92.5%, 93.4%, and 94.5%, assuming that the number of processing elements is 2, 4, 8, 12, 16, and 20 respectively.

Keywords

• post-quantum cryptography
• NTRU
• parallel computing
• Apache Spark