格上近似最短向量问题求解研究

来源 :战略支援部队信息工程大学 | 被引量 : 0次 | 上传用户:ssqjwz
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
随着量子计算的不断发展,针对大数分解难题和离散对数等困难数学问题,均出现了多项式时间的量子求解算法,因此,基于这些数学问题的公钥密码算法,如如RSA、ECC和DSA等标准算法,其安全风险日益增加,信息保密传输和网络通信安全受到极大挑战。为了研究和制定抗量子密码算法标准以应对量子计算带来的挑战,抗量子计算的困难数学问题,逐步成为密码学和计算代数的研究热点。由于格上的困难问题普遍被认为具有抗量子计算的性质,不存在多项式时间的量子求解算法,而且基于格上困难问题设计的密码算法往往还具有安全规约强、加解密高效等优势,因此,格上困难问题受到了广泛关注。作为格密码中最基本、最重要的计算问题之一,格上近似最短向量问题(Approximate Shortest Vector Problem,简称近似SVP)对分析和评估格密码体制的安全性具有非常重要的意义。一方面,格上最短向量问题具有较高的理论价值,大部分格上密码体制的安全性证明依赖于格上最短向量问题;另一方面,求解近似最短向量问题也具有较强的实践价值,近似最短向量问题的实际求解效率被用作格密码算法参数安全的评判标准。本文在研究分析近似SVP问题求解算法的理论和实践基础上,针对随机采样算法、离散剪枝算法和智能算法在近似SVP求解中的应用,进行了研究、改进和探索,主要工作包括以下三个部分:1.改进了一类随机采样约化算法,提出了有效可行的采样策略。随机采样约化算法近年来在SVP挑战中成绩很好,但还存在着理论基础不足、采样策略可行性较差的问题。本文利用格向量的“自然数表示”这一工具,结合启发式假设,证明了在特定的采样集合中自然数向量对应的格向量长度呈正态分布,并使用该定理在低维格上的近似结论提出了一种可行的类枚举的采样算法和其对应的参数选择策略,通过实验验证了该采样模型的准确度。在实际求解SVP挑战的实验中,通过对比不同采样策略,证明了本文提出的采样策略能够有效提高随机采样约化算法的求解效率,可行性较强;进一步,通过对比不同约化策略对算法求解效率的影响,说明了更强的格基约化算法能够提升随机采样约化算法求解近似SVP问题的效率。2.改进了用于求解近似SVP问题的离散剪枝枚举算法,并在实践中超过目前经典枚举算法的最优剪枝策略。格上带剪枝的枚举算法需要在不同格基上重复多次计算,经典枚举中的一般做法是简单地对格基进行重随机化并做LLL约化,策略简单,缺少优化。而对于离散剪枝枚举,其成功率和格基质量有着较大关联,因此本文针对离散剪枝枚举的重随机化过程,提出了三个改进策略:在由标签向量恢复格向量时,有技巧地修改标签的解码算法,保留一部分较短向量用于优化格基,同时将计算开销降低到最小;用格基的G-S平方和衡量格基约化质量,通过控制重随机化的过程以保证G-S平方和单调不增;引入One-tour BKZ算法对格基进行约化,充分平衡格基约化质量和约化效率。该算法相比经典枚举算法的各种剪枝策略有大幅的效率提升,并且超过了经典枚举算法中效率最优的剪枝策略——极值剪枝,而极值剪枝正是目前用于分析密码体制安全性的重要工具——BKZ2.0算法的子算法。3.探索了遗传算法在求解近似SVP问题中的应用,实现了一种用于求解近似SVP问题的遗传算法。遗传算法等智能算法在SVP求解中的探索应用较少,且结合方式平凡,因此效率不高。本文提出了基于自然数表示向量的染色体编码算法,将格向量编码成染色体,并定义了染色体交叉、变异等基本的基因操作;在算法的进化机制设计中,一方面,结合格上SVP求解需要利用正交基信息进行大量浮点计算这一特质,适当地简化了自然选择中的浮点计算过程,采用了基于排序选择的精英策略;另一方面,为了防止算法陷入局部最优,引入了遗传算法中的重启机制,即对格基进行重随机化。实验说明引入重启机制的遗传算法相比经典遗传算法的策略,能够更有效地提升近似SVP问题求解效率,且算法效率远高于经典枚举算法和线性剪枝枚举算法,并且与目前已知公开的最优枚举算法——极值剪枝枚举算法效率相近。本文研究工作紧扣当前密码学界研究热点,丰富了求解近似SVP问题的理论和实践成果,相关成果可以为格上密码体制设计、参数选取和安全评估等提供技术支撑,具有重要的学术理论意义和现实应用价值。
其他文献
大规模多输入多输出(MIMO,Multiple-Input Multiple-Output)作为5G的关键技术,利用空间增益使得接收端的性能得到了极大的提升。但随着天线数的增加,系统的成本和功耗也迅速增长。近年来,智能可重构反射表面(RIS,Reconfigurable Intelligent Surface)通过在平面阵列上集成大量低无源反射单元,实现了低成本智能重构无线信号传播环境而成为了一种
振动台试验是研究结构抗震性能最重要和最直接的手段,而结构模型位移响应是振动台试验结果中重要的物理量。目前,振动台试验中所采用的位移传感器已基本能满足模型的位移测量需求,但仍存在一些限制和不足。视觉测量方法作为一种非接触测量方法,相较于传统位移传感器有很多优势,可以有效解决或者弥补传统位移传感器所受到的限制。为此,本文编写了单向振动台模型位移视觉测量程序,同时对现存位移测量方法的精度进行了全面分析。
近年来,β-Ga2O3作为新一代的半导体材料而备受关注,其具有4.5~4.9 e V的极宽带隙,击穿场强高达8 MV/cm,并有高耐压,高熔点等优点。在高功率器件、日盲紫外探测器件以及X射线光电探测等领域有着广阔的应用前景。非故意掺杂β-Ga2O3是弱n型导电,为提高材料的载流子浓度,其n型掺杂一直是研究的重点,也是器件发展的需要。目前,报道的n型掺杂多为Sn4+、Si4+掺杂。而Ta元素作为V族
天然地震或爆破引起的应力波在介质中传播时,即使不考虑波阵面的扩散效应,振幅也会随着传播距离的增加而显著衰减。造成这种衰减的原因主要有:1.介质非均匀造成的散射衰减,这类衰减通常用散射品质因子来表示;2.介质吸收造成的固有衰减(本征衰减),这类衰减通常用固有品质因子来表示。此外,由于散射衰减与固有衰减的分离存在困难,一般测量方法得到的品质因子同时反映了这两种衰减,通常用视品质因子表示。关于动态品质因
南丹县地层分布以沉积岩为主,泥石流占全县地质灾害总数约9.58%,其中坡面泥石流占比64%,坡面泥石流的识别难于一般的沟谷型泥石流,坡面泥石流的发生常常伴有崩塌、滑坡等不良地质作用,因此在灾害发生的初期,常有被误判、漏判的现象,造成灾害治理措施不合理、不彻底,造成更严重的二次灾害。本文通过从形成、堆积、分布以及规模特征等方面对沉积岩区泥石流的发育特征进行分析,并与一般坡面流石流的发育特征进行了对比
随着增强现实技术的发展,自然直观的人机交互是当前增强现实技术研究的重点。在增强现实的三维空间中,良好的的视觉指示或反馈信息,可以有效减少用户误解交互意图和手势输入误操作。合理、高效和令人满意的自然手势操作是增强现实中自然人机交互中重要研究内容。首先,采用用户启发法研究手势语义符号,以用户为中心理念设计增强现实下移动、旋转和缩放等交互操作的常用手势,运用专家量表评价手段确定手势集合,并将其应用于三维
由脑卒中引发的肢体瘫痪及运动功能障碍极大地降低了卒中患者的生活质量,研究卒中后下肢运动功能重建具有重大的社会意义。功能性电刺激(Functional electrical stimulation,FES)是改善下肢运动功能的重要方式。但现有下肢FES系统存在的不足为:大多数系统的控制方式无法反映肌肉自主发力状况,且现存去伪迹技术无法有效去除动态刺激伪迹。为了实现瘫痪肢体的运动功能重建,课题组提出了
20世纪中期以来,随着世界范围内经济结构的转型升级,文化经济不断冲击着传统的经济形态,文化在综合国力中的地位日益凸显。文化产业作为新兴的朝阳产业,正逐渐成为提高区域和国家经济发展质量,提高国家文化软实力、增强我国国际地位和国际影响力的重要因素。随着文化产业的不断增长,科技创新在促进文化产业持续健康稳定发展方面起着不可替代的作用,文化科技融合成为当前我国文化产业发展的必然选择。因此,研究文化科技融合
研究目的:本文通过检测心力衰竭患者组和正常对照组人血浆中环状RNA—cGmcl1的表达水平,以及cGmc11在不同中医证型、不同心功能分级的心力衰竭患者血浆中的变化,确定cGmcl1在心力衰竭的诊断、预后及中医辨证中的价值,希望为心力衰竭提供微观领域指标,增加临床新的生物标志物。研究方法:选取35例急性心力衰竭患者及25例正常对照组体检者。纳入病例均来源于2015年7月至2016年3月北京市海淀医
随着我国建筑工业化发展,装配式结构的发展需求日益提高,预应力装配式混凝土框架结构作为一种常见的装配式结构,有着较好的位移延性,且规避了传统现浇混凝土框架震后残余位移大、修复困难的缺点。在预应力装配式混凝土框架中,预制的混凝土梁和柱通过后张无粘结钢绞线进行拼装,梁柱之间不再使用传统现浇混凝土连接,梁柱间的剪力主要通过预应力产生的摩擦力来抵抗。在水平力作用下框架梁柱节点可以发生张开,结构的塑性变形主要