本文關(guān)鍵詞：有限域上d-th CDH問題的研究

  更多相關(guān)文章： CDH問題 Partial-CDH問題 d-th CDH問題 喻示

【摘要】：1976年,Diffie-Hellman在密碼學(xué)的新方向[6]中,提出DH問題(Diffie-Hellman Problem)。它分為兩個部分：CDH問題(Computational-Diffie-Hellman problem)和DDH問題(Decisional Diffie-Hellman problem)。其中,密碼學(xué)家研究較多的是CDH問題。2013年,FGPS在[3]中首先定義了Fp2上新的CDH問題-Partial-CDH問題,但是沒有論證它的困難性。2015年,WZZ在[1]中定義了此問題的對偶形式-Dual-Partial-CDH問題,并證實了這兩個問題的困難性與傳統(tǒng)CDH問題的困難性等價。同時,WZZ還將Fp2上的Partial-CDH問題擴展到Fpt(t1)上,定義了d-th CDH問題,并對它的困難性給出了規(guī)約證明。其實早在2000年,Verheul在[2]中就給出了d-th CDH問題與傳統(tǒng)CDH問題困難性等價的規(guī)約證明,得出：給定能計算Diffie-Hellman密鑰某一項系數(shù)的喻示,則存在多項式時間的算法,可以高效解出Diffie-Hellman密鑰。但是,Verheul算法沒有分析喻示存在噪聲的情況,并且該算法的復(fù)雜度隨著素域Fp的擴張次數(shù)t的增長呈指數(shù)增長。因此,對參數(shù)p而言的,Verheul規(guī)約是多項式時間的；對變量t而言,Verheul是指數(shù)時間的,故要求t固定或是小常數(shù)。WZZ在[1]中使用不同的規(guī)約方法也證實了二者的等價性,得出的結(jié)論是：對于d={0,t-1},CDH敵手的攻擊優(yōu)勢至少為對于其他的d(1≤d≤t-2),攻擊優(yōu)勢至少為在完美喻示下,CDH敵手經(jīng)過多項式次操作,就可以高效破解Diffie-Hellman密鑰。相比之下,WZZ的規(guī)約更具有優(yōu)勢,算法的復(fù)雜度不隨t指數(shù)增長,并且分析了有噪聲喻示的情況。但是WZZ算法的規(guī)約過程非常繁瑣,只證實了對于d={0,t-1},矩陣Mh,d可逆。然而事實上,對于所有的0≤d≤t-1,矩陣Mh,d都是以概率1可逆的。此外,WZZ對矩陣Mh,d的每一個輸入沒有給出明確的表達公式。與Verheul[2]規(guī)約算法相比,本文打破了其對擴張次數(shù)t的嚴格限制,將計算復(fù)雜度由指數(shù)階降到多項式階；與WZZ[1]規(guī)約算法相比,本文去除了繁瑣的計算過程,提高了傳統(tǒng)CDH問題向d-th CDH問題規(guī)約的效率。WZZ規(guī)約過程的矩陣表示為：Od*()=XM’,在計算攻擊優(yōu)勢時分析了矩陣M’的可逆概率；而本文利用多項式基表示有限域,引入了以概率1可逆的d-th基乘積矩陣Md,得到的規(guī)約方程為Od*l()0≤l≤t-1=XMd(Yl)0≤l≤t-1,T計算過程更加簡潔,形式表達更加清晰,在計算攻擊優(yōu)勢時,只需分析隨機矩陣(Yl)0≤l≤t-1T的可逆概率。改進算法對規(guī)約方程中d-th基乘積矩陣Md的每個元素給出了具體的計算公式,并利用其以概率1可逆的性質(zhì),得出：對所有的0≤d≤t-1,CDH敵手的攻擊優(yōu)勢至少為改進的算法在完美喻示下,經(jīng)過多項式次操作,可以高效計算出Diffie-Hellman密鑰；在有概率損耗的情況下,相比WZZ的規(guī)約,敵手的攻擊優(yōu)勢提高了除此之外,改進的方法在理論上證明了WZZ規(guī)約中矩陣Mh,d的可逆性,得到攻擊優(yōu)勢的更大下界。
【關(guān)鍵詞】：CDH問題 Partial-CDH問題 d-th CDH問題 喻示
【學(xué)位授予單位】：山東大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2016
【分類號】：TN918.1;O153.4
【目錄】：

• 中文摘要6-8
• 英文摘要8-10
• 符號說明10-11
• 第一章 預(yù)備知識11-15
• §1.1 子域與擴域11-12
• §1.2 有限域12-15
• 第二章 研究背景15-19
• 第三章 傳統(tǒng)CDH問題與d-th CDH問題的規(guī)約證明19-37
• §3.1 Verheul的規(guī)約19-21
• §3.2 WZZ的規(guī)約21-29
• §3.3 改進的規(guī)約29-33
• §3.4 三種算法的比較33-37
• 第四章 總結(jié)37-39
• 附錄39-41
• 參考文獻41-43
• 致謝43-44
• 學(xué)位論文評閱及答辯情況表44

【相似文獻】

中國碩士學(xué)位論文全文數(shù)據(jù)庫 前1條

1 皮若男;有限域上d-th CDH問題的研究[D];山東大學(xué);2016年

，

本文編號：644943