Dimension Reduction Attack on Noncommutative Group Ring NTRU Over the Dihedral Group

NTRU cryptosystem is based on the commutative ring <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\mathbb{Z}[x]/(x^{N}-1)$</tex>, where the value of <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$N$</tex> defines the system's security. Gentry proved that for standard NTRU, <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$N$</tex> should be chosen as a prime number to avoid dimension reduction attacks. However, to boost the performance with fast multiplication methods, other NTRU-like schemes keep using <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$N$</tex> as a composite value (power of two) in the modified ring where the applicability of Gentry's attack seems not possible. Coppersmith and Shamir suggested that noncommutative algebra may help against their lattice attacks and avoid other algebraic attacks. Recently, many proposals have been introduced for NTRU-like constructions over dihedral group motivated by more resistance to some algebraic attacks. This work answers whether one can use composite values of <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$N$</tex> to boost performance with FFT-like multiplication methods in the newly proposed schemes. We prove that Gentry's dimension reduction attack can be extended to composite values of <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$N$</tex> in the setup of the noncommutative dihedral group ring. For even values of <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$N$</tex>, we modify Gentry's attack; moreover, we give an alternative approach to derive a potential decryption key. Using our reduction technique, we are able to find short vectors in exceptionally high 1024-dimensional lattices of a particular structure.