tailieunhanh - DLP over polynomial rings with two cyclotomic cosets

In this paper, this DLP is studied in the case of polynomial rings with two cyclotomic cosets. By mathematical analysis and illustrations, this paper points out that decrete logarithm problem over polynomial rings with two cyclotomic cosets can be used efficiently in public-key cryptography. | Kỹ thuật điều khiển Điện tử DLP OVER POLYNOMIAL RINGS WITH TWO CYCLOTOMIC COSETS Nguyen Le Cuong1 Le Danh Cuong2 Nguyen Binh2 Abstract One of the classical problems in public key cryptography systems and public key exchange protocols is the Discrete Logarithm Problem DLP over a finite field Zp here p is a large prime. In this paper this DLP is studied in the case of polynomial rings with two cyclotomic cosets. By mathematical analysis and illustrations this paper points out that decrete logarithm problem over polynomial rings with two cyclotomic cosets can be used efficiently in public-key cryptography. Key words Discrete Logarithm Problem DLP Cryptography Polynomial rings Cyclotomic coset. 1. INTRODUCTION Nowadays most commonly used public key cryptography systems PKC and public key exchange protocols are based on number theory. The theoretical strength depends on the structure of Abelian groups. Their robustness is based on the difficulty of solving certain problems over finite commutative algebraic structures. One of these problems is the Integer Factorization Problem over the ring Zn here n is the product of two large prime numbers for example the well-known cryptosystem RSA 1 8 is based on this problem. The second classical problem is the Discrete Logarithm Problem DLP over a finite field Zp here p is a large prime the ElGamal protocol and all its variants are based on this problem 9 10 . The discrete logarithm problem DLP in a finite cyclic group G is an algorithmic question to find for any given pair of elements G a number ne N satisfying gn h. This problem is extremely important due to its relation to cryptography 11 . The main idea of this work is the using of polynomial rings with two cyclomic cosets for DLP in particular the rings of quasi-isomorphism to Zp where p is a prime number. This is what makes this ring very interesting for cryptographic applications. 2. PRELIMINARY . DLP in polynomial field PF Consider PF Z2 x f x with f x - irreducible