Design and Cryptanalysis of Noncommutative NTRU-like Post-Quantum Cryptosystems

Abstract

Public key cryptography currently relies on hard mathematical problems that are considered secure against the computational power of classical computers. However, advancements in quantum computing present a serious threat, as large-scale quantum computers have the potential to solve some of these problems nearly instantaneously—tasks that would take classical computers years to complete. In response to this challenge, lattice-based cryptography has emerged as a research area aimed at ensuring information security in the post-quantum era. NTRU is a post-quantum cryptosystem whose security is related to hard problems in lattices that are believed to be safe even against quantum attacks. The design flexibility of NTRU has resulted in many variants; some of them even progressed to the final round of the NIST post-quantum standardization process. Most of the NTRU variants are built over commutative rings. However, employing noncommutative algebras in the NTRU framework is also endorsed as a promising research direction. When Coppersmith and Shamir introduced their pioneering lattice attacks on NTRU, they suggested that using a noncommutative structure might effectively thwart their attack and other attacks that exploit the commutativity. Furthermore, recent studies show that a relaxed version of the NTRU problem that involves multiple keys with a common component can be attacked in polynomial time by solving a system of equations constructed using the commutativity of operations over the underlying ring.