Analysis and Extension of Non-Commutative NTRU

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….


1 Non-commutative NTRU
1.1 Introduction
1.2 Description of Non-commutative NTRU
1.3 Coppersmith’s Attack
1.3.1 Why this works only for DN
1.4 Commutative NTRU
2 Extensions of Non-commutative NTRU
2.1 Introduction and Extension to Other Group Rings
2.2 Preliminary Representation Theory
2.3 Extension of Coppersmith’s Attack
2.4 Breaking the System when zk exists
2.5 When zk does not exist modulo q
2.6 Invertibility of h
2.7 Examples

Author: Truman, Kathryn

Source: University of Maryland

Download URL 2: Visit Now

Leave a Comment