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

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

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

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

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

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

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