期刊文献+
任意字段
题名或关键词
题名
关键词
文摘
作者
第一作者
机构
刊名
分类号
参考文献
作者简介
基金资助
栏目信息

基于DHSP的格上最短向量量子算法的研究

Research on Shortest Vector Problem of Quantum Algorithm Based on Dihedral Hidden Subgroup Problem
下载PDF
导出
摘要 SVP问题是格的公钥密码体制抗量子性的理论依据,论文运用量子计算分析SVP问题,对Kuperberg算法改进,提出了DH-SP多项式时间量子算法,并以此算法为模型框架,以Oded Regev算法理论为基础,提出近似因子为O(n3),时间复杂度是O(n4)的SVP量子算法,最后对其进行性能分析。论文算法的提出将对基于格的公钥密码体制的安全性带来重大威胁。 The shortest vector problem is the basis of the public key cryptosystem based on grid.With improvement on Kuperberg＇s algorithm,a DHSP algorithm is presented that runs in polynomial time.Based on the polynomial DHSP algorithm and Oded Regev＇s theory,a polynomial time quantum algorithm is proposed which solves the shortest vector problem.The algorithm runs in O（n4） with the factor of O（n3）.Finally,a brief performance analysis about the method is made.This algorithm will have an important influence on the public key cryptosystem based on grid.
作者 孙静 袁家斌 金广龙
机构地区 南京航空航天大学计算机科学与技术学院
出处 《计算机与数字工程》 2013年第2期158-162,共5页 Computer & Digital Engineering
基金 NUAA Research Funding(编号:NP2011050)资助
关键词 DHSP SVP Oded Regev DHSP SVP Oded Regev
分类号 TP309.02 [自动化与计算机技术—计算机系统结构]
  • 相关文献

参考文献18

  • 1A.K.Lenstra,H.W.Lenstra,L.Lovasz. Factoring polynomials with rational coefficients[J].Mathematische Annalen,1982.515-534.
  • 2C.P.Schnorr. A hierarchy of polynomial time basis reduction algorithms[J].Theoretical Computer Science,1987.201-224.
  • 3M.Ajtai,R.Kumar,D.Sivakumar. A sieve algorithm for the shortest lattice vector problem[A].2001.601-610.
  • 4P.Shor. Algorithms for Quantum Computation:Discrete Log and Factoring[A].1994.124-134.
  • 5E.Bernstein,U.Vazirani. Quantum complexity theory[A].1992.11-20.
  • 6D.Deutsch,R.Jozsa. Rapid solution of problems by quantum computation[J].Proceedings of the Royal Society of London,1992,(1907):553-558.
  • 7D.Deutsch. Quantum theory,the Church-Turing principle and the universal quantum computer[A].1985.97-117.
  • 8D.R.Simon. On the power of quantum computation[A].1994.116-123.
  • 9M.Mosca. Quantum computation algorithms[D].University of Oxford,1999.
  • 10吕欣,冯登国.密码体制的量子算法分析[J].计算机科学,2005,32(2):166-168. 被引量：3

二级参考文献12

  • 1Deutsch D. Quantum theory,the Church-Turing principle and the universal quantum computer. In: Proc. of the Royal Society, London,vol. A400,1985. 97～117.
  • 2Deutsch D. Quantum computational networks. In: Proc. Roy.Soc. Lond. A 425,1989. 73～90.
  • 3Yao A. Quantum circuit complexity. In: Proc. of the 34th Annual IEEE Symposium on Foundations of Computer Science, 1993. 352～361.
  • 4Simon D. On the power of quantum computation. In: Proc. of the 35th Annual IEEE Symposium on Foundations of Computer Science,1994. 116～123.
  • 5Shor P W. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM Journal on Computing, 1997,26(5): 1484～1509.
  • 6Grover L K. A fast quantum mechanical algorithm for database search. In:Proc. of 28th STOC,1996. 212～219.
  • 7Nielson M A,Chuang I L. Quantum computation and quantum Information, Cambridge university press, 2000.
  • 8Mosca M. The Hidden Subgroup Problem and Eigenvalue Estimation on a Quantum Computer. In: Proc. of the 1st NASA Intl.Conf. on Quantum Computing and Quantum Communication,LNCS 1509,Springer-Verlag, 1999.174～ 188.
  • 9Jozsa R. Quantum Algorithms and the Fourier Transform:[Technical Report]. arXive: quant-ph/9707033,1997.
  • 10Menezes A, van Oorschot P,Vanstone S. Handbook of Applied Cryptography,C R C Press, 1997.

共引文献2

计算机与数字工程
2013年 第2期

相关作者

内容加载中请稍等...

相关机构

内容加载中请稍等...

相关主题

内容加载中请稍等...

浏览历史

内容加载中请稍等...
;
使用帮助 返回顶部