###### Analysis and Extension of Non-Commutative NTRU

###### Diploma

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*is the dihedral group of order 2

_{N }*N*) and uses a commutative subring

*R*

_{0 }= {

*α*∈

*R*|

*Y α*=

*αY*} where

*Y*is an element of order two for

*D*. This system was broken by Coppersmith in [1]. To do this he uses properties of the subset

_{N}*R*

_{1 }= {

*α*∈

*R*|

*Y α*= −

*α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

*θ*:

*R*→

*R*that is used to break the system.

*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*are principal

_{j }*R*

_{0 }modules. This allows us to define a similar

*θ*. 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

*θ*is created it maps into the original group ring, which allows us to break the system. Finally we give a few examples.

## Introduction

Public-key cryptography was introduced around forty years ago. It allows the users to communicate over non-secure channels without any prior communication. They do this by publishing one public key for encryption and using another private key for decryption. RSA[14] is probably the most famous public-key cryptosystem, but there are many others: ElGamal [3, 4], McEliece [11, 12], and commutative NTRU [8]. These are all commutative systems. There are also noncommutative systems such as a braid group system [10] and non-commutative NTRU [6, 1]. Our purpose is to further investigate non-commutative NTRU. We will analyze Coppersmith’s attack [1] on the original system. We will also show that its original implementation can be extended and broken.

For a public-key cryptosystem, assume that Alice wants to send a message to Bob. Bob first publishes a public key and has another private key. Alice uses this public key to encrypt a message and send it to Bob. Bob then uses his private key to decrypt the message. Note that not only Alice can use Bob’s public key, but also anyone who wants to send Bob a message can use his public key to do so. In general, Bob creates his public key from his private key and it is hard for someone to find the private key from the public key.

Non-commutative NTRU
is a ring based public-key cryptosystem. The original system is defined over
the group ring *R *= Z[*D _{N}*] (where

*D*is the dihedral group of order 2

_{N }*N*) and uses a commutative subring

*R*

_{0 }= {

*α*∈

*R*|

*Y α*=

*αY*} where

*Y*is an element of order two for

*D*. This system was broken by Coppersmith in [1]. To do this he uses properties of the subset

_{N}*R*

_{1 }= {

*α*∈

*R*|

*Y α*= −

*α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

*θ*:

*R*→

*R*that is used to break the

system.

In Sections 1.2 and
1.3 we analyze the original system and the attack on the system. Next in
subsection 1.3.1 we determine what groups the original system can be defined
over, and when Coppersmith’s attack will work. Then in Section 2.1 we extend
this system to other group rings. The groups still have two generators that do
not commute, but the generators 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 extend the attack to this generalization of
the system in Section 2.3. This is where the key difference arises.

Coppersmith’s attack only works for Z[*D _{N}*] and closely related group
rings. In Section 2.2 we develop the representation theory of these more
general groups that is necessary to break the system. Also to break the system
we need to look

at subsets *R*_{1}*,R*_{2}*,...,R _{k}*

_{−1 }

^{of }Z[

*G*], where and

*z*

_{k}is a primitive *k*^{th }root of unity. One of the main results is Theorem
2.3.10 which shows that these *R _{i }*are
principal

*R*

_{0 }modules. Finally in Sections 2.4, 2.5, and

2.6 we define a *θ *to
break the system. In Section 2.7 we give a few examples.

**Info!**For specific Project Format, Please upload the format at your dashboard after payment.