Optimized Software Implementations for NIST’s Post Quantum Cryptography Candidates Using NEON Based Instructions

Abstract

The development of quantum computers is a serious threat to traditional cryptography methods that use well-known algorithms like RSA and ECC. These algorithms are secure from classical computers, but they rely on mathematical problems like integer factorization and discrete logarithm problems, which quantum computers can solve effectively. To counter this new threat, cryptographers throughout the world are actively developing a set of quantum-resistant cryptographic protocols called Post-Quantum Cryptography (PQC). The computational effectiveness and performance of PQC algorithms on low-resource devices, however, pose a serious barrier to their widespread use. This research aims to optimize post-quantum cryptographic algorithms, specifically NTRU and Kyber, for ARM-based systems. The study focuses on implementing these algorithms on Android (Google Pixel 2) and Raspberry Pi while leveraging NEON SIMD optimizations to enhance efficiency. A key focus is optimizing polynomial multiplication, a core operation in lattice-based encryption, by evaluating various strategies and selecting the most effective for NEON acceleration. Performance improvements are systematically analyzed across different versions of Kyber and NTRU, with benchmarking against NIST PQC reference implementations to assess speedup and efficiency gains. This research presents the first NEON-optimized implementations of post-quantum cryptographic algorithms on Android, achieving significant performance gain of 2.6x in encryption and 3.1x in decryption of kyber on Android. Similarly in case of NTRU the performance gain is 2.6x in encryption and 5.5x in decryption when compared with the reference implementation. Additionally, a new multiplication design is also presented for kyber on Intel processors, which gives performance gain of 1.17x in encryption and 1.19x in decrypiton suggesting similar optimization techniques could enhance PQC performance on ARM architectures. A novel variant of the NTRU cryptosystem, called M-NTRU, is introduced. NTRU relies on polynomial arithmetic over Z[x] and the hardness of the closest and shortest vector problems, with security based on solving polynomial equations modulo unrelated moduli. In M-NTRU, the polynomial ring Z[x] is replaced with the matrix ring Zp[x]/⟨Xn+1⟩, operating in a non-commutative matrix ring within a Galois field. This enhances security by expanding the key space and mitigating lattice attacks due to highdimensional structures and non-commutativity. While maintaining the conventional NTRU framework, M-NTRU modifies polynomial representation, arithmetic operations, and key generation to strengthen resistance against cryptanalysis. These optimizations will benefit greatly in adoption of the PQC algorithms specially on the resource constrained ARM devices.