Cryptanalysis of Group Ring NTRU: The Case of the Dihedral Group

ABSTRACT The NTRU cryptosystem is one of the earliest proposed schemes for post‐quantum cryptography. With a long history of cryptanalysis and efficient memory and time requirements, NTRU has been standardized by IEEE for public key cryptographic techniques based on hard problems over lattices, and a few NTRU‐style cryptosystems progressed to the third round of the NIST standardization process. The design flexibility of NTRU has resulted in many variants. Group ring NTRU (GR‐NTRU) offers a general framework for designing various NTRU‐like schemes using different groups. Although most schemes in the literature are built over cyclic groups, non‐abelian groups can also be used. Non‐commutativity has been endorsed as a direction to build NTRU variants that are more resistant to some algebraic attacks. Lattice attacks on the public key of NTRU‐like cryptosystems try to retrieve the private key by solving the shortest vector problem (SVP) or its approximation in a lattice of a particular dimension, assuming the knowledge of the public key only. In this work, we analyze the lattice security of GR‐NTRU built over the group ring of the dihedral group of order . We theoretically and experimentally show that dihedral groups do not guarantee better security against this class of attacks than the standard NTRU over the group ring of the cyclic group of order . We prove that retrieving the private key is possible by solving the SVP in two lattices with half the dimension of the original lattice generated for GR‐NTRU based on dihedral groups, that is, the dimension of the lattices to be attacked can be reduced from to and consequently the problem of finding short vectors becomes much easier. We utilize matrix algebra to provide an explicit dimension reduction of the associated lattices without any structure theorem from the representation theory for finite groups, which makes our technique easier to follow and implement. Additionally, experimental results indicate that the naive method of lattice attacks can successfully retrieve a decryption key for only , while our technique can retrieve a decryption key up to , highlighting the effectiveness of our method.