New Discrete Logarithm Problems Over Finite Fields

Public Key Cryptosystems mainly base on the Prime decomposition prob-lem of big integers, discrete logarithm problem(DLP) over finite fields and dis-crete logarithm problem over elliptic curves etc. This paper studies the discrete logarithm problem over finite fields. About this problem, researchers have done many studies and give a lot of methods to find the discrete logarithm. Such as, baby-step giant-step[1], Pollard’s Rho method[2], Kangaroo method[3], in-dex calculation method[4] and Pohlig-Hellman method[5] etc. However, so far, there is no polynomial time algorithm to compute the discrete logarithm over finite fields.Let p be a prime, t≥2,Fpt denote a finite field with pt elements. Let be a monic irreducible polynomial of degree t over Fp. It is well known that Fp[x]/<h(x)> is a field, and Fpt≌Fp[x]/(h(x)), where (h(x)) is a principle in the polynomial ring Fp[x]. Therefore, all the elements in Fpt can be written as polynomial over Fp, i.e. for any g∈Fpt, there are g0,..., gt-1∈Fp such that Addition and multiplication in Fpt are performed as polynomial operations modulo h(x). For simple, we denote with [g]i the coefficient of the degree-i term, i.e.[g]i=gi.In2013, N.Fazio et al.[6] gave a new Diffie-Hellman problem over Fp2 -Partial-CDH Problem:Let g denote a generator of the multiplicative group of Fp2. Given g,ga,gb∈E Fp2, Compute [gab]1∈Fp(i.e., the coefficient of the degree1term of gab). Under the assumption that the Partial-CDH Problem is hard, the authors proved that compute [gab]1and compute every bit of [gab]1is equivalent. N.Fazio et al. left two open problems in the end. The first is to entend the results on Fp2to the finite fields Fpt(t>2). The second is to study the hard-ness of the Partial-CDH Problem. About these two open problems, Mingqiang Wang[7] partially solved the first problem and completely solved the second problem.First of all,[7] extended the definition of Partial-CDH Problem given in [6] and gave new Diffie-Hellman problems over Fpt(t>1):(t,k)-P-CDH problem:Let Fpt be a finite field generated by g and k be an integer. Given g,ga,g b∈Fp2, compute-Dual (t,k)-P-CDH problem:Let Fp*be a finite field generated by g and k be an integer. Given g,ga,gb∈Fp2computeSecondly, the author studied the hardness of the above new Diffie-Hellman problems in detail and got the following results. He proved that the Partial-CDH problem and Dual Partial-CDH problem is equivalent to the original CDH problem over finite field Fp2. Under the assumption that the CDH prob-lem is hard, the author also proved the unpredictability of every bit of the coordinate of the secret value. Recently, Mingqiang Wang[?] got some new results about the (t,k)-P-CDH problem and Dual (t,k)-P-CDH problem over Fpt.This paper defines new Discrete Logarithm Problems(DLP) over finite field Fpt(t≥2), i.e.(t,k)-P-DLP and Dual (t,k)-P-DLP. -(t, k)-P-DLP:Let Fpt*=<g>,a∈Zpt-1. Given([ga]t-1,…,[ga]t-k), find one a’∈Zpt-1such that-Dual (t,k)-P-DLP:Let Fpt*=<g>, a∈Zpt-1. Given ([ga]0,…,[ga]k-1), find one a’∈Zpt-1such thatFor these two new DLP problems, the space complexity of the exhaustive method is negligible and the time complexity is O(pk) iterative operations. This is equal to the time complexity of the exhaustive method used to solve traditional DLP over Fpk. The space complexity of Pollard’s Rho method is O(d) and the time complexity is O(d+(?)), where1≤d≤pt-k. Therefore, we choose d=1. Then, the space complexity is negligible and the time complexity is O((?)).This is equal to the time complexity of Pollard’s Rho method used to solve traditional DLP over Fpt. This states that exhaustive method and Rho method can’t efficiently solve the new defined DLP problems.About the hardness of these two new DLP problems, we get the following results.-(t,k)-P-DLP and Dual (t,k)-P-DLP are no more hard than the traditional DLP over Fpt.-When k|t, the Dual (t,k)-P-DLP over Fpt can be reduced to the original DLP over Fpk.In (t,k)-P-DLP and Dual (t,k)-P-DLP, the known information is less than the original DLP. If we can prove the hardness of the new problems, then we can apply them in relevant cryptosystems or cryptographic protocols to im-prove their efficiency and maintain their security at the same time. About this, we consider (2,1)-P-DLP and apply it in EIGamal Public Key Cryptosystem to get a new EIGamal cryptosystem. If (2,1)-P-DLP is proven to be hard, then not only the security of the new EIGamal cryptosystem is not weaker than before, but also its efficiency has great improvements.