背包类DiffieHellman问题的复杂性研究

《背包类DiffieHellman问题的复杂性研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、密级：中国科学院大学UniversityofChineseAcademyofSciences硕士学位论文背包类Diffie．Hellman问题的复杂性研究论文作者：指导教师：学位类别：学科专业：研究所：李伟吕克伟副研究员博士中国科学院信息工程研究所工学硕士信息安全中国科学院信息工程研究所2013年5月By、№iLiAThesisSubmittedtoTheUniversityofChineseAcademyofSciencesInpartialfulfillmentoftherequirementForthedegreeofM

2、asterofInformationSecurityInstituteofInformationEngineeringChineseAcademyofSciencesMay，2013Ⅲ8㈣5川&mⅢ1Ⅲ3Ⅲ4舢2洲Y中国科学院信息工程研究所研究生学位论文独创性声明本人声明所呈交的学位论文是本人在吕克伟导师指导下进行的研究工作及取得的研究成果。除了文中特别加以标注和致谢的内容外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得中国科学院信息工程研究所或其他教育机构的学位或证书而使用过的材料。与我共同工作的同志对本研究

3、所做的任何贡献均已在论文中做了明确的说明并表示谢意。论文与资料若有不实之处，本人承担一切相关责任。学位论文作者签名：签字日期：砂7弓年』胡虏学位论文版权使用授权说明本学位论文作者完全了解中国科学院信息工程研究所有关保留、使用学位论文的规定。特授权中国科学院信息工程研究所可以将学位论文的全部或部分内容编入有关数据库进行检索，并采用影印、缩印或扫描等复制手段保存、汇编，以供查阅和借阅。同意研究所向国家有关部门或机构送交论文的复印件和磁盘。(保密的论文在解密后应遵循此规定)学位论文作者签名：导师签名：，昆签字日期：加僻r月fy日签字

4、日期卯f3年厂月f归摘要现代密码学的基础是建立于一类单向函数上的。对于单向函数比特安全性的研究是密码学中一个较为重要的研究方向。利用比特安全性的研究，我们可以获取很多较好的结果，这些结果可以用来构建和改善很多密码学工具吗，如伪随机比特，安全协议，以及数字签名等等。特别地，数字签名应经广泛应用与通信，互联网以及金融等领域。本文主要对以下几个问题进行了研究，分别是基于一类特殊预言机下的背包类DH问题的比特安全性研究和基于背包DH问题的数字签名安全性进行了探讨和改进。具体的研究结果如下：1．背包DH问题的比特安全性：背包DH问题是基

5、于Diffie—Hellman／司题的变种，该问题已经被证明与背包问题在计算上是等价的。文章[13】中提出基于该问题的应用。针对这个问题，本文提出了一种新的预言机，并在这种预言机下，证明了该问题的每一个比特都是同样困难的。2．基于背包DH问题的数字签名方案的安全性问题：对一种基于背包DH问题的数字签名方案[13】进行研究，构造一种针对该系统的攻击，并成功伪造签名。于该攻击基础之上，提出一种能够有效抵抗这种攻击的数字签名方案。该签名方案是基于一个新的困难问题k—CAA’。我们证明了七一CAA’的困难性介于DLP和尼一wCDHP之

6、间。关键词：单向函数，比特安全，背包DH函数，双线性对，数字签名AbstractModerncryptographyisbasedonvarietyofone—wayfunctions．Bitseeuritvofone-wayfunctionisallimportantissueintheoreticalcryptographyfields．Withsomepropertyofbitsecurity，wegetsomesignificantresultsincryptography．Usingthoseresults，weca

7、nconstructandimprovemanytools，suchaspseudo—randomgenerators，protocolsanddigitalsignatures．Especially，digitalsignaturesarewidelyappliedintheInternet，financialandotherfields．Inthispaper，wewillshowsomeresearchontwoproblem：bitseeuritvofKnapsackDime-Hellmanproblemunderas

8、pecificoracleandthesecuritvofasignatureschemebasedonKnapsacksDiffie-Hellmanproblenl．1·BitsecurityofKnapsackDiffie—·Hellmanproblem：Knapsack