-
题名格上唯一最短向量问题的细粒度复杂性
- 1
-
-
作者
金保隆
薛锐
-
机构
中国科学院信息工程研究所网络空间安全防御重点实验室
中国科学院大学网络空间安全学院
-
出处
《中国科学:信息科学》
CSCD
北大核心
2024年第12期2727-2742,共16页
-
基金
国家自然科学基金(批准号:62172405)资助项目。
-
文摘
唯一最短向量问题(unique shortest vector problem,uSVP)的困难性是一些流行的格密码方案的安全基础,对其在不同参数下的复杂性的研究也是格密码体系的重要组成部分,然而这方面的研究进展十分缓慢,同时对uSVP的细粒度复杂性的研究也十分欠缺.本文改进了一个从最短向量问题(shortest vector problem,SVP)到uSVP的归约算法,提高了其成功概率,调整了参数限制,从而允许建立不同参数条件下从SVP到uSVP的细粒度归约.利用这个归约,得以证明以下结果:(1)在超多项式时间下,得到了一个参数更大的从SVP到uSVP的归约;(2)在强指数时间假设(gap strong exponential time hypothesis,GapSETH)下,构建了从常数参数的SVP到常数参数的uSVP的亚指数时间归约,从而证明了uSVP在GapSETH下的困难性;(3)以上结果都可以转化成有界距离译码(bounded distance decoding,BDD)的相应结论:在对应条件下求解参数小于1的BDD也是困难的;(4)结合稳定格中的格点个数上界,得到了参数远超常数的从SVP到uSVP的归约.
-
关键词
最短向量问题
唯一最短向量问题
计算复杂性
细粒度复杂性
复杂性归约
-
Keywords
shortest vector problem
unique shortest vector problem
computational complexity
fine-grained complexity
complexity reduction
-
分类号
G63
[文化科学—教育学]
-
-
题名隐含子群问题的研究现状
- 2
-
-
作者
戴文静
袁家斌
-
机构
南京航空航天大学计算机科学与技术学院
-
出处
《计算机科学》
CSCD
北大核心
2018年第6期1-8,共8页
-
基金
基于GPU集群的大规模量子线路仿真理论与方法研究(61571226)
国家自然科学基金青年基金(61701229)
江苏省自然科学基金青年基金(BK20170802)资助
-
文摘
在Shor发现大整数因子分解问题的有效量子算法之后,量子计算迫使我们重新审视现有的密码系统。隐含子群问题是量子计算在群结构上的推广,它暗示通过考虑不同的群和函数来解决更困难的问题,以期找到新的指数倍快于其经典对应物的量子算法。有限交换群隐含子群问题的研究已有相对固定的研究框架和方法,而非交换群隐含子群问题的研究一直很活跃。研究表明,二面体群隐含子群问题的有效解决可能攻破基于格的唯一最短向量问题的密码体制,图同构问题可以转化为对称群隐含子群问题。文中对隐含子群问题的研究现状进行综述,希望能够吸引更多研究者对隐含子群问题的注意。最后为隐含子群问题未来的研究方向提出参考意见。
-
关键词
量子计算
隐含子群问题
交换群
二面体群
唯一最短向量问题
对称群
-
Keywords
Quantum computation
Hidden subgroup problem,Abelian group
Dihedral group
Unique shortest vector problem
Symmetric group
-
分类号
TP309.2
[自动化与计算机技术—计算机系统结构]
-
