Analysis and Extension of Non-Commutative NTRU

Undergraduate

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[DN] (where DN is the dihedral group of order 2N) and uses a commutative subring R0 = {α R|Y α = αY } where Y is an element of order two for DN. This system was broken by Coppersmith in [1]. To do this he uses properties of the subset R1 = {α R | Y α = −αY }. He is able to create a ’fake’ private key using R1 and R0. This ’fake’ private key then allows him to create a map θ : 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 kth root of unity. We denote these subsets by R1,R2,...,Rk−1. One of the main results is to show that these Rj are principal R0 modules. This allows us to define a similar θ. Since a primitive kth 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[DN] (where DN is the dihedral group of order 2N) and uses a commutative subring R0 = {α R | Y α = αY } where Y is an element of order two for DN. This system was broken by Coppersmith in [1]. To do this he uses properties of the subset R1 = {α R | Y α = −αY }. He is able to create a ‘fake’ private key using R1 and R0. 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[DN] 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 R1,R2,...,Rk−1 of Z[G], where and zk

is a primitive kth root of unity. One of the main results is Theorem 2.3.10 which shows that these Ri are principal R0 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.