有限域上d-th CDH问题的研究

发布时间：2017-08-09 11:08

  本文关键词：有限域上d-th CDH问题的研究

  更多相关文章： CDH问题 Partial-CDH问题 d-th CDH问题 喻示

【摘要】：1976年,Diffie-Hellman在密码学的新方向[6]中,提出DH问题(Diffie-Hellman Problem)。它分为两个部分：CDH问题(Computational-Diffie-Hellman problem)和DDH问题(Decisional Diffie-Hellman problem)。其中,密码学家研究较多的是CDH问题。2013年,FGPS在[3]中首先定义了Fp2上新的CDH问题-Partial-CDH问题,但是没有论证它的困难性。2015年,WZZ在[1]中定义了此问题的对偶形式-Dual-Partial-CDH问题,并证实了这两个问题的困难性与传统CDH问题的困难性等价。同时,WZZ还将Fp2上的Partial-CDH问题扩展到Fpt(t1)上,定义了d-th CDH问题,并对它的困难性给出了规约证明。其实早在2000年,Verheul在[2]中就给出了d-th CDH问题与传统CDH问题困难性等价的规约证明,得出：给定能计算Diffie-Hellman密钥某一项系数的喻示,则存在多项式时间的算法,可以高效解出Diffie-Hellman密钥。但是,Verheul算法没有分析喻示存在噪声的情况,并且该算法的复杂度随着素域Fp的扩张次数t的增长呈指数增长。因此,对参数p而言的,Verheul规约是多项式时间的；对变量t而言,Verheul是指数时间的,故要求t固定或是小常数。WZZ在[1]中使用不同的规约方法也证实了二者的等价性,得出的结论是：对于d={0,t-1},CDH敌手的攻击优势至少为对于其他的d(1≤d≤t-2),攻击优势至少为在完美喻示下,CDH敌手经过多项式次操作,就可以高效破解Diffie-Hellman密钥。相比之下,WZZ的规约更具有优势,算法的复杂度不随t指数增长,并且分析了有噪声喻示的情况。但是WZZ算法的规约过程非常繁琐,只证实了对于d={0,t-1},矩阵Mh,d可逆。然而事实上,对于所有的0≤d≤t-1,矩阵Mh,d都是以概率1可逆的。此外,WZZ对矩阵Mh,d的每一个输入没有给出明确的表达公式。与Verheul[2]规约算法相比,本文打破了其对扩张次数t的严格限制,将计算复杂度由指数阶降到多项式阶；与WZZ[1]规约算法相比,本文去除了繁琐的计算过程,提高了传统CDH问题向d-th CDH问题规约的效率。WZZ规约过程的矩阵表示为：Od*()=XM’,在计算攻击优势时分析了矩阵M’的可逆概率；而本文利用多项式基表示有限域,引入了以概率1可逆的d-th基乘积矩阵Md,得到的规约方程为Od*l()0≤l≤t-1=XMd(Yl)0≤l≤t-1,T计算过程更加简洁,形式表达更加清晰,在计算攻击优势时,只需分析随机矩阵(Yl)0≤l≤t-1T的可逆概率。改进算法对规约方程中d-th基乘积矩阵Md的每个元素给出了具体的计算公式,并利用其以概率1可逆的性质,得出：对所有的0≤d≤t-1,CDH敌手的攻击优势至少为改进的算法在完美喻示下,经过多项式次操作,可以高效计算出Diffie-Hellman密钥；在有概率损耗的情况下,相比WZZ的规约,敌手的攻击优势提高了除此之外,改进的方法在理论上证明了WZZ规约中矩阵Mh,d的可逆性,得到攻击优势的更大下界。
【关键词】：CDH问题 Partial-CDH问题 d-th CDH问题 喻示
【学位授予单位】：山东大学
【学位级别】：硕士
【学位授予年份】：2016
【分类号】：TN918.1;O153.4
【目录】：

• 中文摘要6-8
• 英文摘要8-10
• 符号说明10-11
• 第一章 预备知识11-15
• §1.1 子域与扩域11-12
• §1.2 有限域12-15
• 第二章 研究背景15-19
• 第三章 传统CDH问题与d-th CDH问题的规约证明19-37
• §3.1 Verheul的规约19-21
• §3.2 WZZ的规约21-29
• §3.3 改进的规约29-33
• §3.4 三种算法的比较33-37
• 第四章 总结37-39
• 附录39-41
• 参考文献41-43
• 致谢43-44
• 学位论文评阅及答辩情况表44

【相似文献】

中国硕士学位论文全文数据库 前1条

1 皮若男;有限域上d-th CDH问题的研究[D];山东大学;2016年

，

本文编号：644943