一种格上SVP问题求解的快速分块筛法

1

作者 宋蕙冰 顾纯祥 +1 位作者 郑永辉 孙泽栋 《信息工程大学学报》 2019年第3期359-365,共7页

针对现有筛法在通过向量约减构造短向量列表过程中消耗大量时间的问题,基于降维思想,提出一种新型的分块筛法。通过对原始格基分块对应生成多个低维子格,分别在子格上做筛法,获得子格短向量列表;将在子格中得到的短向量列表作为原始格... 针对现有筛法在通过向量约减构造短向量列表过程中消耗大量时间的问题,基于降维思想,提出一种新型的分块筛法。通过对原始格基分块对应生成多个低维子格,分别在子格上做筛法,获得子格短向量列表;将在子格中得到的短向量列表作为原始格上筛法的初始向量列表,能够较好地提高约化效率,从而更快找到原始格上的最短向量。分块筛技术在对新向量的约减速度与效果上优势更明显,实验数据表明分块筛在运行时间上可以达到平均7.1%的提高。 展开更多

关键词 格理论 最短向量问题 筛法 分块筛 格基约化算法

在线阅读 下载PDF 职称材料

求解格上最短向量问题的自适应遗传算法

2

作者 毕经国 苏磊 王林 《密码学报(中英文)》 北大核心 2025年第1期215-226,共12页

最短向量问题(shortest vector problem,SVP)是格密码中一个经典的困难问题.丁丹等于2015年提出了首个解决最短向量问题的遗传算法,该算法利用BKZ约化基的正交表示来搜索格点组成的空间,能够高效地找到格内最短向量.由于该算法采用固定... 最短向量问题(shortest vector problem,SVP)是格密码中一个经典的困难问题.丁丹等于2015年提出了首个解决最短向量问题的遗传算法,该算法利用BKZ约化基的正交表示来搜索格点组成的空间,能够高效地找到格内最短向量.由于该算法采用固定的交叉率和变异率,容易陷入局部最优解,且没有充分利用BKZ约化基正交表示下短向量的稀疏特征.本文从跳出局部最优解、提升算法收敛速度以及提高成功概率三个维度改进了该算法的SVP智能求解方案.首先,本文引入了动态计算交叉率和变异率的模块,主要基于个体质量与种群收敛程度两个维度来控制交叉率以及变异率,从而有效避免算法陷入局部最优解.其次,设计了一种自适应变异策略,从基因层面充分利用了BKZ约化基下短向量正交整数表示的稀疏性,显著加快了整个算法的收敛速度.最后,提出了基于多种群并行的遗传算法,进一步提高了概率算法的成功率.通过这些改进,本文的算法在求解SVP问题时表现出更高的效率和更强的鲁棒性. 展开更多

关键词 格理论 遗传算法 最短向量问题

在线阅读 下载PDF 职称材料

基于遗传策略的格基约化算法 被引量：5

3

作者 刘向辉 韩文报 权建校 《电子与信息学报》 EI CSCD 北大核心 2013年第8期1940-1945,共6页

格基约化算法是密码分析的重要工具。该文借鉴遗传算法的基本策略,通过对初始格基的调整变换,提出了一种新的格基约化算法,新算法总能得到给定格中长度更短的向量和质量更高的一组基。利用该算法,针对最短向量问题(SVP)挑战的部分数据... 格基约化算法是密码分析的重要工具。该文借鉴遗传算法的基本策略,通过对初始格基的调整变换,提出了一种新的格基约化算法,新算法总能得到给定格中长度更短的向量和质量更高的一组基。利用该算法,针对最短向量问题(SVP)挑战的部分数据进行了测试,新算法的输出结果达到或超过了挑战的公开记录,约化效果良好。 展开更多

关键词 密码学 格基约化 LLL算法 遗传算法 最短向量问题挑战

在线阅读 下载PDF 职称材料

一个新型的NTRU类数字签名方案 被引量：21

4

作者 胡予濮 《计算机学报》 EI CSCD 北大核心 2008年第9期1661-1666,共6页

NTRU类数字签名方案的一个共同缺陷是签名值会泄露私钥的一些信息.针对这个缺陷,当前已经有若干有效攻击.该文提出一个新型的NTRU类数字签名方案.新方案具有与R-NSS相似的结构,但有若干新颖的设计.文中给出新方案的3个结果:(1)由公钥恢... NTRU类数字签名方案的一个共同缺陷是签名值会泄露私钥的一些信息.针对这个缺陷,当前已经有若干有效攻击.该文提出一个新型的NTRU类数字签名方案.新方案具有与R-NSS相似的结构,但有若干新颖的设计.文中给出新方案的3个结果:(1)由公钥恢复出私钥的困难性基于若干格上的最小向量问题(SVP);(2)由公钥伪造签名的困难性等价于某个格上的最近向量问题(CVP);(3)每个签名值仍然会泄露私钥的一些信息,但无限制泄露的最终形式只是关于私钥的一组复杂的非线性方程. 展开更多

关键词 NTRU 数字签名 格上的最小向量问题(svp) 格上的最近向量问题(CVP)

在线阅读 下载PDF 职称材料

一种基于格的代理签名方案 被引量：4

5

作者 余磊 《计算机工程》 CAS CSCD 2013年第10期123-126,132,共5页

由格上基于盆景树原理构造的代理签名,其密钥长度会随代理人所使用格的维数不断变化。为此,提出一种签名长度可控的代理签名方案。根据代理签名长度与格维数的线性递增关系,使用固定维数的格基委托算法生成代理签名密钥,采用原像抽样函... 由格上基于盆景树原理构造的代理签名,其密钥长度会随代理人所使用格的维数不断变化。为此,提出一种签名长度可控的代理签名方案。根据代理签名长度与格维数的线性递增关系,使用固定维数的格基委托算法生成代理签名密钥,采用原像抽样函数构造代理签名方案,并利用格上小整数解问题和最短向量问题的困难性,对其进行安全性证明。结果表明,该方案在保持代理签名密钥长度不变的同时,可满足代理签名的不可伪造性。 展开更多

关键词 格 代理签名 盆景树原理 小整数解问题 最短路径问题 原像抽样函数

在线阅读 下载PDF 职称材料

非超递增序列背包加密算法的攻击方法

6

作者 于志敏 古春生 +2 位作者 景征骏 蔡秋茹 臧海娟 《计算机工程》 CAS CSCD 2013年第5期136-139,共4页

针对栗风永等人提出的非超递增序列背包加密算法(计算机工程与设计,2011年第2期),设计基于格攻击的2种攻击方法。方法 1构造维度为3的格,在其上应用LLL算法可直接恢复私钥,时间复杂度为O(n2)。方法 2采用低密度攻击,可以较大概率恢复明... 针对栗风永等人提出的非超递增序列背包加密算法(计算机工程与设计,2011年第2期),设计基于格攻击的2种攻击方法。方法 1构造维度为3的格,在其上应用LLL算法可直接恢复私钥,时间复杂度为O(n2)。方法 2采用低密度攻击,可以较大概率恢复明文,时间复杂度为O(n3lb(max(bi)))。实验结果表明,栗风永等人提出的算法是不安全的。 展开更多

关键词 背包 非超递增序列 格攻击 低密度攻击 最短向量问题 LLL算法

在线阅读 下载PDF 职称材料

格上筛法研究现状与发展趋势 被引量：1

7

作者 毕蕾 路献辉 王鲲鹏 《密码学报》 CSCD 2021年第5期735-757,共23页

最短向量问题(shortest vectorproblem,SVP)是格上的基础困难问题之一,是格密码方案安全性的基础假设,SVP求解算法是评估格密码算法具体安全性的关键技术.实用的SVP精确求解算法主要包括筛法和枚举两种类型,其中筛法的时间复杂性更低,... 最短向量问题(shortest vectorproblem,SVP)是格上的基础困难问题之一,是格密码方案安全性的基础假设,SVP求解算法是评估格密码算法具体安全性的关键技术.实用的SVP精确求解算法主要包括筛法和枚举两种类型,其中筛法的时间复杂性更低,是目前实用化格密码算法安全性评估主要使用的算法.筛法由Ajtai-Kumar-Sivakumar于2001年首次提出,其主要思想是将指数多个格向量通过一系列的筛取过程,互相约化,以得到一定数量的长度为O(λ1)的格向量,然后将这些向量两两相减以得到最短非零格向量,其中λ1表示格中最短非零向量长度.二十年来,研究者们不仅在理论上对筛法进行研究和改进,同时也给出了一系列在实际应用中更为高效的启发式算法.针对筛法中复杂度最高的部分,即约化时遍历指数多个格向量的过程,研究者们使用了多种技术对其进行改进,包括生日悖论、局部敏感技术、层次化、元组化、线性化等.本文按照技术发展及时间顺序介绍了格上筛法的发展历史、研究现状和将来的发展趋势. 展开更多

关键词 格 最短向量问题 筛法

在线阅读 下载PDF 职称材料

格基规约算法研究进展 被引量：1

8

作者 周世祥 刘梁华 《山东理工大学学报（自然科学版）》 CAS 2012年第1期11-18,共8页

格是一种线性结构,基于格的密码具有无可比拟的低能耗优势,故而在未来的智能终端上将有很好的应用前景.相比传统的RSA,ECC密码体制,格问题可证明的安全性在后量子密码时代已经显示了重要的作用.格算法的核心问题归结为格基规约问题,20... 格是一种线性结构,基于格的密码具有无可比拟的低能耗优势,故而在未来的智能终端上将有很好的应用前景.相比传统的RSA,ECC密码体制,格问题可证明的安全性在后量子密码时代已经显示了重要的作用.格算法的核心问题归结为格基规约问题,20多年来,在LLL格基规约算法启发下,出现了各种更强、更快的规约算法,有精确的也有近似的,对密码分析和密码设计产生了重要的推动作用.对各种规约概念和算法进行了全面的分析和总结. 展开更多

关键词 格 规约基 最短矢量问题 LLL算法 算法复杂度

在线阅读 下载PDF 职称材料

PBKZ算法及其在格挑战中的应用

9

作者 孙明豪 屈龙江 李超 《河南师范大学学报（自然科学版）》 CAS 北大核心 2020年第5期1-8,共8页

格是欧氏空间R^n中的离散加法子群,格上的许多计算问题被证明是NP-hard,常用来作为公钥密码体制的底层困难问题.目前基于量子计算机模型的量子算法也难以高效求解格上的困难问题,因此后量子时代下格密码学受到了越来越多的关注.最短向... 格是欧氏空间R^n中的离散加法子群,格上的许多计算问题被证明是NP-hard,常用来作为公钥密码体制的底层困难问题.目前基于量子计算机模型的量子算法也难以高效求解格上的困难问题,因此后量子时代下格密码学受到了越来越多的关注.最短向量问题(Shortest Vector Problem,SVP)是格上的计算困难问题,格基约化算法是求解SVP问题的一个有效算法,该算法可以找到格中的一些短向量.YOSHINORI等人在2016年欧洲密码年会上提出Progressive BKZ算法,是目前格基约化算法中最为高效的算法之一.详细介绍了PBKZ算法,分析了它的运行机理及其内在特点,然后在Linux系统下成功调试了PBKZ算法库,并针对Darmstadt格挑战展开了一系列实验,最终在600维和725维两种情形下取得了目前国际上最好结果. 展开更多

关键词 格 格基约化算法 svp问题 PBKZ算法 Darmstadt格挑战

在线阅读 下载PDF 职称材料

格基规约的快速实现：SDR算法

10

作者 洪浩 胡予濮 《电子科技》 2007年第12期1-3,共3页

格基规约是格理论研究的一个重要内容,也是密码设计和分析中的一个重要工具。在理论研究中,许多格上问题都可以通过规约来求解(或者近似求解)。在密码学应用中,对一些密码方案的分析最终都可以等价成一个格基规约问题。文章提出了一种... 格基规约是格理论研究的一个重要内容,也是密码设计和分析中的一个重要工具。在理论研究中,许多格上问题都可以通过规约来求解(或者近似求解)。在密码学应用中,对一些密码方案的分析最终都可以等价成一个格基规约问题。文章提出了一种新型格基规约算法:SDR算法,新算法将正交格理论融入Schnorr算法中,在相同的规约效果下,可将原有Schnorr算法中多项式时间因子HKZ(2k)降为HKZ(k)。 展开更多

关键词 SDR算法 格 格规约 svp问题 密码学

在线阅读 下载PDF 职称材料

Restricted parameter range promise set cover problems are easy

11

作者 Hao CHEN 《Frontiers of Mathematics in China》 SCIE CSCD 2014年第6期1253-1260,共8页

The restricted parameter range set cover problem is a weak form of the NP-hard set cover problem with the restricted range of parameters. We give a polynomial time algorithm for this problem by lattices.

关键词 Set cover problem LATTICE closest vector problem （CVP） shortestvector problem （svp）

原文传递