多变量公钥密码方案的设计与分析

发布时间：2017-07-05 07:18

  本文关键词：多变量公钥密码方案的设计与分析

  更多相关文章： 多变量公钥密码系统 MQ问题 同构多项式问题 极小秩问题

【摘要】：公钥密码系统是现代安全通信系统的一个重要组成部分.目前广泛使用的公钥密码系统是基于数论问题的公钥密码系统(如RSA、ECC等).然而Shor的算法和量子计算机的发展对这些基于数论问题的公钥密码系统构成了极大的威胁.因此,我们需要设计能够抵御量子计算攻击的公钥密码系统,即后量子密码系统.多变量公钥密码系统是主要的后量子密码系统.多变量公钥密码系统不但能够抵御量子计算攻击,而且运算速度快,可以应用到计算和存储能力有限的设备(如智能卡、无线传感器网络、RFID标签等)上.所以,我们有必要对多变量公钥密码系统进行深入的研究.本文对多变量公钥密码系统进行了研究,取得了以下进展：1.在过去的三十年中,密码学者试图利用有限域上的多变量多项式来构造公钥加密系统.然而,这些多变量公钥加密系统大多数是不安全的.它们的共同缺点是中心映射多项式对应的矩阵的秩很小,从而容易受到极小秩攻击.因此,一些密码学者认为多变量公钥密码系统只适用于签名和认证,而不适用于加密.设计一个安全、高效的多变量公钥加密方案是多变量公钥密码学领域的重要挑战.本文的第一个进展就是利用矩阵乘法,设计了一个安全、高效的多变量公钥加密方案.我们称这个公钥加密方案为简单矩阵加密方案.简单矩阵加密方案的中心映射多项式对应的矩阵没有低秩的特点,因此能够抵抗秩攻击.此外,我们还说明简单矩阵加密方案能够抵御其他主要的攻击方法,并给出了几组安全参数以供开发人员参考.2.在过去的三十年中,密码学者设计了许多多变量公钥签名方案.然而,除了基于UOV限门和HFE限门的签名方案外,其他的签名方案已经全部被破解.此外,在原始的UOV签名方案中,为了保证UOV签名方案的安全性,签名长度至少要比文档长度长3倍.因此,UOV签名方案的效率很低.在基于HFE限门的签名方案中,因为在签名生成的过程中,需要求大域上的高次单变量多项式方程的解,所以,目前基于HFE限门的签名方案的签名速度较慢.设计一个安全、高效的多变量公钥签名方案是多变量公钥密码学领域的另一个重要挑战.本文的第二个进展是提出了一种双层结构的签名方案.假设在相同的安全级别下,对同一份文档进行签名,那么我们的签名方案的签名长度比UOV签名方案的签名长度短很多,我们的签名方案的签名速度比其他基于HFE限门的签名方案的签名速度快很多.3.本文的第三个进展是利用嵌入曲面攻击方法攻破了基于丢番图方程的多变量公钥加密系统.设x=(x1,..,xn)和Y=(y1,...,ym)分别是该加密系统的明文和对应的密文,通过大量的计算机实验,我们发现X,Y满足以下形式的嵌入曲面方程：于是,可以利用这些嵌入曲面方程攻破该加密系统.4.本文第四个进展是提出了一个求小域上的多变量二次方程组的解的算法,我们称之为XLE算法.它是XL算法的一个变种算法.我们证明XLE算法的时间复杂度为其中m是方程的个数,n是变量的个数,q是有限域的元素的个数,r和D是给定的正整数,2.3766≤ω≤3.
【关键词】：多变量公钥密码系统 MQ问题 同构多项式问题 极小秩问题
【学位授予单位】：华南理工大学
【学位级别】：博士
【学位授予年份】：2015
【分类号】：TN918.4
【目录】：

• 摘要5-7
• Abstract7-12
• 第一章 绪论12-17
• 1.1 多变量公钥密码系统的历史背景12-13
• 1.2 多变量公钥密码系统的研究现状13-15
• 1.3 本文的主要创新点15-16
• 1.4 本文的组织结构16-17
• 第二章 多变量公钥密码17-42
• 2.1 基础知识17-21
• 2.1.1 基本记号17
• 2.1.2 线性变换和仿射变换17-18
• 2.1.3 多变量多项式18-19
• 2.1.4 二次多变量多项式的矩阵表示19-20
• 2.1.5 二次多变量多项式系统20
• 2.1.6 单变量多项式20-21
• 2.2 多变量公钥密码的结构21-22
• 2.2.1 加密和解密过程21-22
• 2.2.2 签名和认证过程22
• 2.3 多变量公钥密码的基本问题22-24
• 2.3.1 MQ问题22-23
• 2.3.2 IP问题23-24
• 2.3.3 极小秩问题24
• 2.4 多变量公钥密码的陷门函数的构造24-30
• 2.4.1 油醋结构25-26
• 2.4.2 三角结构26-28
• 2.4.3 F_q的扩域E上的单变量多项式结构28-29
• 2.4.4 基于IP问题的认证方案29-30
• 2.4.5 基于MQ问题的认证协议30
• 2.5 多变量密码学的基本攻击方法30-41
• 2.5.1 代数攻击31-37
• 2.5.2 秩攻击37-41
• 2.6 本章小结41-42
• 第三章 简单矩阵加密方案42-51
• 3.1 简单矩阵加密方案的设计42-44
• 3.2 简单矩阵加密方案示例44-46
• 3.3 解密失败的概率46
• 3.4 安全性分析46-49
• 3.4.1 高阶线性化方程攻击46-47
• 3.4.2 秩攻击47
• 3.4.3 代数攻击47-48
• 3.4.4 其他攻击方式48-49
• 3.5 参数选择49
• 3.6 公钥次数为3的简单矩阵加密方案49-50
• 3.7 本章小结50-51
• 第四章 双层结构签名方案51-68
• 4.1 双层结构签名方案的基本框架51-53
• 4.2 实例1：UOV&HFEv签名方案53-57
• 4.2.1 UOV&HFEv签名方案示例54-57
• 4.3 实例2：UOV&平方醋签名方案57-58
• 4.4 实例3：HFEv&HFEv签名方案58-63
• 4.4.1 HFEv&HFEv签名方案示例59-63
• 4.5 安全性分析63-65
• 4.5.1 极小秩攻击63-64
• 4.5.2 分离油醋攻击64
• 4.5.3 代数攻击64-65
• 4.6 层结构签名方案的参数选择65-67
• 4.6.1 UOV&HFEv签名方案的参数的选择65-66
• 4.6.2 UOV&平方醋签名方案的参数选择66
• 4.6.3 HFEv&HFEv签名方案的参数选择66-67
• 4.7 本章小结67-68
• 第五章 嵌入曲面攻击68-81
• 5.1 基于丢番图方程的多变量公钥加密方案68-73
• 5.1.1 公钥和私钥的生成69-72
• 5.1.2 加密和解密的过程72-73
• 5.1.3 基于丢番图的公钥加密方案的参数73
• 5.2 从解密过程中获得嵌入曲面方程73-76
• 5.2.1 攻击第一组参数的复杂度76
• 5.2.2 攻击其他两组参数的复杂度76
• 5.3 从中心映射中获得嵌入曲面方程76-80
• 5.3.1 攻击第一组参数的复杂度79-80
• 5.3.2 攻击第二组参数的复杂度80
• 5.3.3 实验结果80
• 5.4 本章小结80-81
• 第六章 一种求解MQ问题的新算法81-89
• 6.1 XLE算法81-85
• 6.1.1 XLE算法示例83-85
• 6.2 XLE算法的时间复杂度85-86
• 6.3 参数D和r的选择86-88
• 6.4 XLE算法与F4算法的比较88
• 6.5 本章小结88-89
• 总结和后续工作89-90
• 参考文献90-101
• 攻读博士学位期间取得的研究成果101-103
• 致谢103-104
• 附件104

【相似文献】

中国期刊全文数据库 前10条

1 王申;梁加红;;数字仿真中多变量函数插值线性外推算法[J];计算机仿真;1992年02期

2 吕剑虹;徐治皋;陈来九;;特征结构下的一种多变量预测控制方法[J];自动化学报;1992年05期

3 张庆武;吴刚;薛美盛;王嵩;何德峰;祁飞;;聚乙烯装置模块多变量在线操作指导[J];信息与控制;2007年01期

4 谭建荣,彭群生,梁友栋,皮明智;多变量非线性问题计算机图示的数学模型及其应用[J];计算机学报;1992年10期

5 王福利;郎世俊;;关于多变量自校正调节的一个新算法[J];控制与决策;1988年02期

6 王士杰;;最小二乘多变量函数寻优法及其在过程控制中的应用[J];中国纺织大学学报;1993年04期

7 吕剑虹，陈来九;一种多变量连续时间预测控制方法[J];自动化学报;1995年02期

8 姜复兴;吴广玉;;多变量闭环系统的辨识[J];自动化技术与应用;1986年02期

9 彭立信;孙德敏;张德颂;袁斌;杨健;;多变量最小方差自校正调节器在蓄电池厂铅粉机控制中的应用[J];自动化学报;1990年05期

10 周景振,韩曾晋;一种新型多变量模糊自适应控制系统的研究[J];自动化学报;1999年02期

中国重要会议论文全文数据库 前10条

1 贾利民;张锡第;谢肇桐;;多变量模糊系统的一个快速算法[A];1995年中国控制会议论文集（下）[C];1995年

2 徐敦忠;林岩;毛剑琴;;多变量变结构模型参考自适应控制[A];第二十届中国控制会议论文集（上）[C];2001年

3 李维;秦京华;;应用中的多变量自校正调节器[A];1998年中国控制会议论文集[C];1998年

4 张兴武;陈雪峰;何正嘉;;梁类结构的多变量小波有限元动力学分析[A];中国力学大会——2013论文摘要集[C];2013年

5 张维存;李清泉;;多变量组合自校正器[A];1991年控制理论及其应用年会论文集（上）[C];1991年

6 李清泉;张维存;;时延未知或时变的多变量组合自校正器的设计[A];1991年控制理论及其应用年会论文集（上）[C];1991年

7 李少远;王群仙;袁著祉;;一种改进的多变量模糊逻辑推理方法[A];1996年中国控制会议论文集[C];1996年

8 宋松柏;金菊良;康艳;;Copulas函数描述洪水多变量联合概率分布的几个问题探讨[A];中国水文科技新发展——2012中国水文学术讨论会论文集[C];2012年

9 张竟新;;一类确定性多变量非线性系统的自适应控制[A];1989年控制理论及其应用年会论文集（中）[C];1989年

10 冯丽辉;陈雯;史红梅;;活化炉的多变量解耦控制研究[A];首届全国有色金属自动化技术与应用学术年会论文集[C];2003年

中国重要报纸全文数据库 前1条

1 劳英坚;鱼ω-3脂肪酸和妇女中风危险[N];医药经济报;2001年

中国博士学位论文全文数据库 前5条

1 张志杰;面向复杂产品制造的多变量过程调整技术研究[D];天津大学;2013年

2 魏利胜;多变量网络控制系统建模、控制与调度初探[D];上海大学;2009年

3 陶成东;多变量公钥密码方案的设计与分析[D];华南理工大学;2015年

4 任耀庆;多变量模糊逻辑控制系统的设计及其应用[D];中南大学;2013年

5 黄道平;多变量非线性过程控制[D];华南理工大学;1998年

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

1 陈伟;多变量模型参考自适应控制进一步研究[D];曲阜师范大学;2008年

2 程志金;多变量系统辨识方法的研究及应用[D];北京化工大学;2012年

3 肖丹卉;结合优先级的多变量过程报警阈值优化方法[D];北京化工大学;2014年

4 王明明;多变量闭环辨识[D];北京化工大学;2008年

5 王检耀;三维接触碰撞动力学的多变量方法及接触模型研究[D];上海交通大学;2014年

6 谢敏;多变量极值分布在区域暴雨极值分析中的应用[D];南京信息工程大学;2011年

7 方芬;多变量混沌时间序列预测及其在股票市场中的应用[D];东南大学;2006年

8 于哲;保证鲁棒稳定的多变量干扰观测器设计及应用[D];上海交通大学;2014年

9 王勇;电热连续结晶机多变量预测控制算法研究[D];昆明理工大学;2011年

10 周志刚;多变量多时滞过程的建模与控制[D];江南大学;2014年

，

本文编号：521007