有限域上新的離散對(duì)數(shù)問題.pdf

1、公鑰密碼體制基于的困難問題主要有:大整數(shù)的素分解問題、有限域上的離散對(duì)數(shù)問題(DLP)和橢圓曲線上的離散對(duì)數(shù)問題等。本文研究的是有限域上的離散對(duì)數(shù)問題。關(guān)于這個(gè)問題，人們已進(jìn)行了許多深入的研究，相繼提出了許多求離散對(duì)數(shù)的方法，如大步小步法[1]、Pollard'sRho方法[2]、Kangaroo方法[3]、指標(biāo)計(jì)算法[4]和Pohlig-Hellman算法[5]等。但到目前為止，還沒有找到一個(gè)多項(xiàng)式時(shí)間算法來(lái)計(jì)算有限域上的離散對(duì)數(shù)。<

2、br>　　設(shè)p為素?cái)?shù)，t≥2，F(xiàn)pt表示含有pt個(gè)元素的有限域。設(shè)h(x)=xt+ht-1xt-1+…+h1x+h0，hi∈Fp,0≤i≤t-1為Fp上的t次不可約多項(xiàng)式。則Fp[x]/為域，且Fpt≌Fp[x]/，其中，為Fp[x]中的一個(gè)主理想。因此，有限域Fpt中的所有元素都可以寫成Fp上的多項(xiàng)式。即對(duì)任意的g∈Fpt，都存在g0，…，gt-1∈Fp使得g=gt-1xt-1+gt-2xt-2+…

3、+g1x+g0.Fpt中元素之間的加法運(yùn)算和乘法運(yùn)算都是模h(x）的多項(xiàng)式運(yùn)算。為了方便，將g的i次項(xiàng)系數(shù)記為[g]i，即[g]i=gi.
　　在2013年，N.Fazio等[6]給出了有限域Fp2上的一類新的Diffie-Hellman問題:
　　-Partial-CDH問題:設(shè)g是Fp2的乘法群的一個(gè)生成元。給定g，ga，gb∈Fp2，計(jì)算[gab]1∈Fp（即gab的一次項(xiàng)系數(shù)）。
　　在假設(shè)Partial-CD

4、H問題是困難的前提下，作者證明了計(jì)算[gab]1與計(jì)算[gab]1的任意一位是等價(jià)的。在文章結(jié)尾，N.Fazio等留下了兩個(gè)公開問題:第一，是把有限域Fp2上的結(jié)果擴(kuò)展到有限域Fpt(t＞2)上;第二，是研究Partial-CDH問題的困難性。對(duì)這兩個(gè)問題，王明強(qiáng)[7]部分地解決了第一個(gè)問題，完全地解決了第二個(gè)問題。
　　首先，[7]對(duì)[6]中的Partial-CDH問題的定義進(jìn)行了擴(kuò)展，提出了有限域Fpt(t＞1)上新的Diff

5、ie-Hellman問題:
　　-(t，k)-P-CDH問題:設(shè)F*pt=，k≤t是正整數(shù)，給定g，ga，gb∈Fp2，計(jì)算（[gab]t-1，[gab]t-2，…，[gab]t-k）∈(Fp)k.
　　-對(duì)偶(t，k)-P-CDH問題:設(shè)F*pt=，k≤t是正整數(shù)，給定g，ga，gb∈Fp2，計(jì)算（[gab]0，[gab]1，…，[gab]k-1）∈(Fp)k.其次，[7]對(duì)上面新問題以及Partial-CDH

6、問題的困難性進(jìn)行了詳細(xì)的研究，得到:在有限域Fp2上，Partial-CDH問題及對(duì)偶Partial-CDH問題的困難性與原始CDH問題的困難性等價(jià)，并證明了在CDH問題假設(shè)下，gab的每個(gè)坐標(biāo)的每一位都是不可預(yù)測(cè)的。
　　本文在有限域Fpt(t≥2)上提出了新的離散對(duì)數(shù)問題，即(t，k)-P-DLP問題和對(duì)偶(t，k)-P-DLP問題:
　　-(t，k)-P-DLP問題:設(shè)F*pt=，a∈Zpt-1，給定（[ga]t

7、-1，…，[ga]t-k），求一個(gè)a'∈Zpt-1，使得（[ga']t-1，…，[ga']t-k）=（[ga]t-1，…，[ga]t-k）.
　　-對(duì)偶(t，k)-P-DLP問題:設(shè)F*pt=，a∈Zpt-1，給定（[ga]0，…，[ga]k-1），求一個(gè)a'∈Zpt-1，使得（[ga']0，…，[ga']k-1）=（[ga]0，…，[ga]k-1）.
　　利用窮舉法對(duì)這兩個(gè)問題求解的空間復(fù)雜度均可以忽略，時(shí)間復(fù)雜度均

8、為O(pk）次迭代運(yùn)算。這個(gè)復(fù)雜度和利用窮舉法求解Fpk上的原始離散對(duì)數(shù)問題的時(shí)間復(fù)雜度相等。利用Pollard'sRho方法對(duì)這兩個(gè)問題求解的空間復(fù)雜度均為O(d)，時(shí)間復(fù)雜度均為O（d+√(pt-1)d），其中1≤d≤pt-k.因此，取d=1.此時(shí)空間復(fù)雜度可以忽略，時(shí)間復(fù)雜度為O(√pt-1).這個(gè)復(fù)雜度與利用Pollard'sRho方法求解Fpt上的原始離散對(duì)數(shù)的時(shí)間復(fù)雜度相等。這說明，窮舉法和Rho方法并不能有效求解上述新的離

9、散對(duì)數(shù)問題。
　　關(guān)于新的離散對(duì)數(shù)問題的困難性，具體地，我們得到了:-(t，k)-P-DLP問題和對(duì)偶(t，k)-P-DLP問題不會(huì)比Fpt上的原始離散對(duì)數(shù)問題更困難。
　　-當(dāng)k|t時(shí)，F(xiàn)pt上的對(duì)偶(t，k)-P-DLP問題可以歸約到Fpk的DLP問題。
　　新的離散對(duì)數(shù)問題和原來(lái)的離散對(duì)數(shù)問題相比，給出的已知信息更少。如果可以保證新問題的困難性，則把它們應(yīng)用在基于離散對(duì)數(shù)問題的相關(guān)密碼體制或密碼協(xié)議中，將會(huì)大大提