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

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

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

• 中文摘要6-8
• 英文摘要8-10
• 符號(hào)說明10-11
• 第一章 預(yù)備知識(shí)11-15
• §1.1 子域與擴(kuò)域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 改進(jìn)的規(guī)約29-33
• §3.4 三種算法的比較33-37
• 第四章 總結(jié)37-39
• 附錄39-41
• 參考文獻(xiàn)41-43
• 致謝43-44
• 學(xué)位論文評(píng)閱及答辯情況表44

【相似文獻(xiàn)】

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

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

，

本文編號(hào)：644943