几类新型密码体制困难问题求解算法的分析与应用

发布时间：2017-04-02 17:18

  本文关键词：几类新型密码体制困难问题求解算法的分析与应用，由笔耕文化传播整理发布。

【摘要】：密码学理论与技术是保障信息安全的核心。而密码体制的设计与分析离不开困难问题和求解困难问题的算法。传统的基于困难问题构造的密码体制一般考虑因子分解和离散对数难题。这些密码体制发展时间较长,也经过了一系列密码分析技术的考验和修正。但是近年来,随着人们对云计算和后量子时代信息安全的更多样化和高强度的需求,对新型密码体制,例如基于编码问题、格问题的密码体制的设计和研究正蓬勃兴起。这些密码体制带来了很多理论和应用上更好的性质,但是其安全性有待进一步考虑。因此,对这些新型密码体制困难问题求解算法的探讨是当前密码学领域的研究热点。本文的研究工作围绕对几类新型密码体制困难问题求解算法的分析及其应用展开,主要内容和创新点包括：1.本文给出了一个存储空间限制条件下的更有效的随机线性码解码算法。随机线性码的解码问题,是编码理论和算法复杂度理论中最基本的问题之一。作为一个NP-困难问题,其难解性也被用来构造密码体制,例如著名的McEliece公钥密码体制等。1994年,Shor证明分解因子和离散对数问题在量子计算机模型下是多项式时间可求解的,而安全性基于编码问题等NP-困难问题的密码体制被普遍认为具有抗量子攻击的特性。作为此类密码体制设计的基础,随机线性码的解码问题和求解算法再次引起研究者的兴趣。因而近年来,一系列算法被提出,使得求解这一问题所需的时间复杂度得到降低。而存储空间复杂度,这一衡量算法在实际攻击中效率的重要评估指标,目前的研究尚不充分。为此,我们考虑随机线性码的信息集解码(information set decoding,ISD)算法在存储空间有限制的条件下的效率。在Finiasz和Sendrier的ISD算法的理论体系结构下,我们利用Shamir等人在2012年美密会上给出的分割技术(dissection technique)的思想,给出了新的确定性解码算法,该算法在任一指定的存储空间界限内可达到更优的时间复杂度。同时,给出了新算法的更优性的严格证明。从实践的角度,由于在密码分析的背景中,求解困难问题的算法作为敌手破译能力的标准,更侧重算法在实际实现时的条件,故我们的算法可以作为一个更合理的评估基于编码的密码体制安全性的标准。从理论角度,这是对编码问题,这一理论计算机科学中的重要问题,进行的更深入的时间和存储空间复杂度平衡的讨论。2.本文给出了随机整数格交与并的若干性质及其在一类重要的前沿密码体制——GGH安全性分析中的应用。求解格困难问题的算法,作为一种经典的公钥密码体制分析工具,一直被广泛的研究。特别是近年来,基于格困难问题构造的密码体制由于具有后量子时代和云计算背景下的众多理论及实际中的良好性质而受到信息安全领域和密码学界的高度关注,更使得格问题及其求解算法成为研究一系列重要密码体制安全性的根本性手段。在本文中,我们的贡献可以分为两层次：首先我们分析了与密码体制安全性紧密相关的随机整数格的交与并的相关性质。利用格与对偶格的性质和整数矩阵标准型计算与整数环中随机元素互素概率的对应关系,我们得到：以很高的概率,随机整数格的交可以保持格的维数、扩大格的体积；并给出对扩大后体积的准确估计。对应到密码分析的背景中,该结论指出了构造一类可以被有效算法求解的格困难问题子问题的具体方法,且结论成立的条件相符于格密码体制在实际应用环境中的条件。其次,作为一个应用,我们进一步分析了Plantard等人于2009年给出的使用最短向量(SVP)求解算法对GGH密码体制的广播攻击,计算了攻击成功需要的实例个数,得出了攻击的效率。我们的结论从数学上严格的解释了攻击成功的原因,而Plantard等人仅用实验数据验证其攻击的有效性。同时,我们指出并修正了Plantard等人对其攻击算法描述的一个不完备之处。此外,我们给出了一种新的使用最近向量(CVP)求解算法和格的交技术的攻击,补充了Plantard等人原有攻击中无法给出分析和证明的部分。由于GGH的设计思想被用于全同态加密等密码学前沿课题,我们的方法和结论对此评估类前沿密码体制的安全性和实用性具有参考价值。3.本文对F2上最短线性程序问题及Paar算法的进行了理论分析。线性程序的概念源自符号计算。最短线性程序(Shortest Linear Program,SLP)问题是指给出一组域F上的线性表达式E,找到最短的线性程序来计算E。该问题于2012年被Boyar等人证明是NP-困难问题和MAX SNP-完全问题,故从算法复杂度理论角度,对该问题的多项式时问近似算法及其近似因子的上下界的研究具有重要性和普适性。当域F为二元域F2时,最短线性程序问题转化为能实现一组线性表达式的无消去电路中XOR门的最小个数问题。作为通讯和编码解码系统的设计与实现中最普遍的问题之一,该问题近年来被从新型密码体制安全有效实现的角度被广泛考虑。Paar算法是求解该问题最常见和有效的近似算法,但其有效性一直没有得到严格的数学证明。基于电路的组合结构,我们对Paar算法给出了在线性表达式的矩阵行重d=3,4情况下的理论分析,证明了这两种情况下算法的近似因子；并结合组合数学技巧给出了SLP电路最小尺寸的一个下界,进而得到Paar算法与平凡的实现算法的对比。由于d=3的实例对应证明困难性时使用的实例类型,d=4的实例对应实际工程中常用的常重码参数取法,我们的结论证明了Paaar算法有效性中重要的一部分,也是对Boyar等人于2012年提出的公开问题的部分解决。
【关键词】：随机线性码 存储空间限制 随机格的交 GGH密码体制 最短线性程序问题 Paar算法
【学位授予单位】：山东大学
【学位级别】：博士
【学位授予年份】：2015
【分类号】：TN918.1
【目录】：

• 摘要4-7
• Abstract7-12
• 主要符号对照表12-14
• 第1章 绪论14-21
• 1.1 国内外研究现状16-18
• 1.2 本文主要创新点18-19
• 1.3 文章结构19-21
• 第2章 预备知识21-38
• 2.1 线性码的基本概念21-25
• 2.2 格的基本概念25-29
• 2.3 Hermite标准型、Smith标准型29-35
• 2.4 最短线性程序问题35-38
• 第3章 存储空间限制条件下的信息集解码算法38-60
• 3.1 随机线性码的解码问题与存储空间限制条件38-40
• 3.2 FS-ISD算法概述40-46
• 3.3 新的信息集解码算法46-59
• 3.3.1 算法思想的来源46
• 3.3.2 新的算法46-48
• 3.3.3 复杂度分析48-55
• 3.3.4 算法对比55-59
• 3.4 小结59-60
• 第4章 随机整数格的交及其在格密码体制安全性分析中的应用60-82
• 4.1 随机整数格交与并的若干性质60-72
• 4.1.1 随机整数格的概念61
• 4.1.2 随机整数格交与并的维数61-65
• 4.1.3 随机整数格的并的体积65-67
• 4.1.4 随机整数格的交的体积67-72
• 4.2 对格密码体制GGH广播攻击的进一步分析72-81
• 4.2.1 GGH密码体制简介72-73
• 4.2.2 Plantard等人对GGH的广播攻击73-74
• 4.2.3 对使用SVP求解算法攻击方法的完善74-78
• 4.2.4 新的使用CVP(BDD)求解算法的攻击78-81
• 4.3 小结81-82
• 第5章 对F_2上最短线性程序问题及Paar算法的理论分析82-94
• 5.1 Paar算法概述82-86
• 5.2 SLP电路最小尺寸的下界估计86-89
• 5.3 Paar算法的近似因子89-93
• 5.3.1 行重参数d=3的情形90-92
• 5.3.2 行重参数d=4的情形92-93
• 5.4 小结93-94
• 第6章 结论和研究计划94-96
• 参考文献96-105
• 致谢105-108
• 个人简历、在学期间完成的学术论文与研究成果108-109
• 学位论文评阅及答辩情况表109

【共引文献】

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

1 孙艳华;王浩;张延华;;格缩减辅助MIMO检测的非线性量化[J];北京邮电大学学报;2010年01期

2 孙艳华;王浩;张延华;;复数域格缩减的MIMO检测算法研究[J];电子科技大学学报;2010年05期

3 曹海燕;李君;李光球;;基于可靠性累积概率的球形译码排序[J];电子学报;2012年07期

4 刘经南;于兴旺;张小红;;基于格论的GNSS模糊度解算[J];测绘学报;2012年05期

5 LIU Hongwei;CAO Wenming;;Public Proof of Cloud Storage from Lattice Assumption[J];Chinese Journal of Electronics;2014年01期

6 毛新宇;程宇新;项海格;;混合的深度优先及宽度优先球形译码算法[J];重庆邮电大学学报(自然科学版);2012年05期

7 张丽敏;;云环境下一种低成本的数据安全存储和处理框架[J];电信科学;2015年02期

8 杨孝鹏;马文平;张成丽;;一种新型基于环上带误差学习问题的认证密钥交换方案[J];电子与信息学报;2015年08期

9 毛新宇;范伟亮;王志军;;简化的固定复杂度球型译码算法[J];北京邮电大学学报;2015年04期

10 ;Probability method for cryptanalysis of general multivariate modular linear equation[J];Science in China(Series F:Information Sciences);2009年10期

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

1 ;A Computationally Efficient Exact ML Sphere Decoder[A];第九届全国青年通信学术会议论文集[C];2004年

2 ;A Computationally Efficient Exact ML Sphere Decoder[A];第九届全国青年通信学术会议论文集[C];2004年

3 刘海涛;程型清;李道本;;低复杂度复球译码检测算法[A];通信理论与信号处理新进展——2005年通信理论与信号处理年会论文集[C];2005年

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

1 杨玉庆;3GPP LTE下行接收系统的数字信号处理与VLSI实现研究[D];复旦大学;2011年

2 陈睿;OFDM和MIMO系统中的预编码技术研究[D];西安电子科技大学;2011年

3 于兴旺;多频GNSS精密定位理论与方法研究[D];武汉大学;2011年

4 伍前红;可信密码学计算的关键技术及其在电子商务中的应用[D];西安电子科技大学;2004年

5 余位驰;格基规约理论及其在密码设计中的应用[D];西南交通大学;2005年

6 王兴林;MIMO-OFDM系统中接收机及信道估计技术研究[D];北京邮电大学;2006年

7 梁鹏;VLST-OFDM无线通信系统中检测等问题的研究[D];北京邮电大学;2006年

8 王保仓;几类快速公钥密码的设计与分析[D];西安电子科技大学;2006年

9 刘陈;无线通信系统中的空时编码技术[D];东南大学;2005年

10 李颖;平衰落信道下多天线系统中的信号检测算法研究[D];国防科学技术大学;2006年

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

1 姜彤;LTE上行多用户MIMO系统检测算法研究[D];西安电子科技大学;2011年

2 刘龙;无线MIMO系统检测算法研究[D];西安电子科技大学;2011年

3 雷胜;MIMO系统中信号检测算法研究[D];北京邮电大学;2011年

4 于婧;基于LTE的MIMO实现方案及检测算法研究[D];南京邮电大学;2011年

5 于健鹏;MIMO无线通信系统中迭代检测技术研究[D];上海交通大学;2012年

6 鞠春晖;高性能软输出K-Best MIMO检测器的设计与实现[D];上海交通大学;2012年

7 沈小祥;MIMO-OFDM系统联合检测算法研究[D];南京邮电大学;2012年

8 杨祥;多用户STBC/SFBC码的性能研究[D];杭州电子科技大学;2012年

9 许f愑，

本文编号：282872