有限域上d-th CDH問題的研究.pdf

1、1976年，Diffie-Hellman在密碼學(xué)的新方向[6]中，提出DH問題(Diffie-Hellman Problem)。它分為兩個(gè)部分:CDH問題(Computational-Diffie-Hellmanproblem)和DDH問題(Decisional Diffie-Hellman problem)。其中，密碼學(xué)家研究較多的是CDH問題。
　　2013年，F(xiàn)GPS在[3]中首先定義了Fp22上新的CDH問題-Partia

2、l-CDH問題，但是沒有論證它的困難性。2015年，WZZ在[1]中定義了此問題的對(duì)偶形式-Dual-Partial-CDH問題，并證實(shí)了這兩個(gè)問題的困難性與傳統(tǒng)CDH問題的困難性等價(jià)。同時(shí)，WZZ還將Fp2上的Partial-CDH問題擴(kuò)展到Fpt(t＞1)上，定義了d-th CDH問題，并對(duì)它的困難性給出了規(guī)約證明。其實(shí)早在2000年，Verheul在[2]中就給出了d-th CDH問題與傳統(tǒng)CDH問題困難性等價(jià)的規(guī)約證明，得出:給

3、定能計(jì)算Diffie-Hellman密鑰某一項(xiàng)系數(shù)的喻示，則存在多項(xiàng)式時(shí)間的算法，可以高效解出Diffie-Hellman密鑰。但是，Verheul算法沒有分析喻示存在噪聲的情況，并且該算法的復(fù)雜度隨著素域Fp的擴(kuò)張次數(shù)t的增長呈指數(shù)增長。因此，對(duì)參數(shù)p而言的，Verheul規(guī)約是多項(xiàng)式時(shí)間的;對(duì)變量t而言，Verheul是指數(shù)時(shí)間的，故要求t固定或是小常數(shù)。WZZ在[1]中使用不同的規(guī)約方法也證實(shí)了二者的等價(jià)性，得出的結(jié)論是:對(duì)于d=

4、{0，t-1}，CDH敵手的攻擊優(yōu)勢(shì)至少為e-2/p-1*(AdvdcdhA,h,Fpt)t;對(duì)于其他的d(1≤d≤t-2)，攻擊優(yōu)勢(shì)至少為（1-1/p)t*e-2/p-1*(AdvdcdA,h,Fpt)t.在完美喻示下，CDH敵手經(jīng)過多項(xiàng)式次操作，就可以高效破解Diffie-Hellman密鑰。相比之下，WZZ的規(guī)約更具有優(yōu)勢(shì)，算法的復(fù)雜度不隨t指數(shù)增長，并且分析了有噪聲喻示的情況。但是WZZ算法的規(guī)約過程非常繁瑣，只證實(shí)了對(duì)于d={

5、0，t-1}，矩陣Mh,d可逆。然而事實(shí)上，對(duì)于所有的0≤d≤t-1，矩陣Mh,d都是以概率1可逆的。此外，WZZ對(duì)矩陣Mh,d的每一個(gè)輸入沒有給出明確的表達(dá)公式。
　　與Verheul[2]規(guī)約算法相比，本文打破了其對(duì)擴(kuò)張次數(shù)t的嚴(yán)格限制，將計(jì)算復(fù)雜度由指數(shù)階降到多項(xiàng)式階;與WZZ[1]規(guī)約算法相比，本文去除了繁瑣的計(jì)算過程，提高了傳統(tǒng)CDH問題向d-th CDH問題規(guī)約的效率。WZZ規(guī)約過程的矩陣表示為:O*d()=XM'，在

6、計(jì)算攻擊優(yōu)勢(shì)時(shí)分析了矩陣M'的可逆概率;而本文利用多項(xiàng)式基表示有限域，引入了以概率1可逆的d-th基乘積矩陣Md，得到的規(guī)約方程為O*ld()0≤l≤t-1=XMd(Yl)T0≤l≤t-1，計(jì)算過程更加簡(jiǎn)潔，形式表達(dá)更加清晰，在計(jì)算攻擊優(yōu)勢(shì)時(shí)，只需分析隨機(jī)矩陣(Yl)T0≤l≤t-1的可逆概率。改進(jìn)算法對(duì)規(guī)約方程中d-th基乘積矩陣Md的每個(gè)元素給出了具體的計(jì)算公式，并利用其以概率1可逆的性質(zhì)，得出:對(duì)所有的0≤d≤t-1，CDH敵手的