Analysis and Extension of Non-Commutative NTRU

Abstract

We discuss the ring based public-key cryptosystem known as non-commutative NTRU. The original system is defined over the group ring R = Z[D_N] (where D_N is the dihedral group of order 2N) and uses a commutative subring R_0 = {a in R | Y a = a Y} where Y is an element of order two for D_N. This system was broken by Coppersmith. To do this he uses properties of the subset R_1 = { a in R | Y a = - a Y }. He is able to create a 'fake' private key using R_1 and R_0. This 'fake' private key then allows him to create a map d: R -> R that is used to break the system. The present discussion first analyzes the original system and the attack on the system. We also determine what groups the original system can be defined over, and therefore when Coppersmith's attack will work. Second we extend this system to other group rings. The groups have two generators that do not commute, but the generators will have prime orders larger than two. We still work with the ring Z[G] and the subring of elements that commute with Y, the generator with smaller order. We then extend the attack on the system. This is where the key difference arises. We develop the representation theory of these more general groups so that we can break the system. Also to break the system we need to look at subsets of Z[G] where conjugation by Y (of order k) multiplies the elements by a k^th root of unity. We denote these subsets by R_1, R_2, ..., R_{k-1}. One of the main results is to show that these R_j are principal R_0 modules. This allows us to define a similar map d: R -> R. Since a primitive k^th root of unity does not always exist modulo q it is necessary to work in an extension ring to break the system in some cases. But when d: R -> R is created it maps into the original group ring, which allows us to break the system. Finally we give a few examples.