计算机科学 ›› 2014, Vol. 41 ›› Issue (8): 183-185,218.doi: 10.11896/j.issn.1002-137X.2014.08.040

• 信息安全 • 上一篇    下一篇

基于量子克隆的二面体群隐含子群问题量子算法的研究

金广龙,袁家斌   

  1. 南京航空航天大学计算机科学与技术学院 南京210016;南京航空航天大学计算机科学与技术学院 南京210016
  • 出版日期:2018-11-14 发布日期:2018-11-14
  • 基金资助:
    本文受面向大型客机全球化协同研制的信息安全体系(2009AA044601)资助

Quantum Cloning-based Quantum Algorithm for Dihedral Hidden Subgroup Problem

JIN Guang-long and YUAN Jia-bin   

  • Online:2018-11-14 Published:2018-11-14

摘要: 基于最短向量问题的格公钥密码体制是典型的抗量子计算密码体制。格的唯一最短向量问题可转化为二面体群的隐含子群问题。有效地求解二面体群的隐含子群问题可攻破基于格的唯一最短向量问题的公钥密码体制。Kuperberg提出了二面体群隐含子群问题的半指数级量子算法。通过研究Kuperberg量子算法,利用概率量子克隆,文中提出了二面体群隐含子群问题的多项式时间量子算法。

关键词: 隐含子群问题,二面体群,最短向量问题,量子克隆,线性多项式

Abstract: Kuperberg presented a quantum algorithm for the dihedral hidden subgroup problem,but with sub-exponential time and query complexity.We presented a quantum cloning-based quantum algorithm for dihedral hidden subgroup problem with polynomial time and query complexity.Dihedral hidden subgroup problem is related to poly(n)-unique shortest vector problem.If the dihedral hidden subgroup problem is solved efficiently,the lattice-based cryptography can be breaken,which is secure against quantum computers.

Key words: Hidden subgroup problem,Dihedral group,Shortest vector problem,Quantum cloning,Linear polynomial

[1] Shor P.Algorithms for Quantum Computation:Discrete Log andFactoring [C]∥Proceedings of the 35th Symposium on Foundations of Computer Science.1994:124-134
[2] Ettinger M,Hoyer P,Knill E.Hidden subgroup states are almost orthogonal [J/OL].arXiv:quant-ph/9901034,1999
[3] Murphy J.Analysing the Quantum Fourier Transform for finite groups through the Hidden Subgroup Problem [D].Montreal:McGill University,2001
[4] Kuperberg G.A subexponential-time quantum algorithm for the dihedral hidden subgroup problem [J/OL].arXiv:quant-ph/0302112
[5] Regev O.Quantum computation and lattice problems [C]∥Proceedings of the 43rd Annual IEEE Symposium on Foundations of Computer Science.2002:520-529
[6] Regev O.A subexponential time algorithm for the dihedral hidden subgroup problem with polynomial space [J/OL].arXiv:quant-ph/0406151
[7] Childs A M,Jao D,Soukharev V.Constructing elliptic curve isogenies in quantum subexponential time [J/OL].arXiv:1012:4019
[8] Kuperberg G.Another subexponential-time quantum algorithm for the dihedral hidden subgroup problem [J/OL].arXiv:1112.3333
[9] Wootters W K,Zurek W H.A single quantum cannot be cloned [J].Nature,1982,299:802-803
[10] Barnum H,Caves C M,Fuchs C A,et al.Non-commuting mixed states cannot be broadcast[J].Phys.Rev.Lett,1996,76:2818-2821
[11] Duan L M,Guo G C.Probabilistic cloning and identification of linearly independent quantum states [J].Phys.Rev.Lett,1998,80(22):4999-5002
[12] Pati A K.Quantum superposition of multiple clones and the novel cloning machine [J].Phys.Rev.Lett,1999(83):2849-2852

No related articles found!
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
[1] 雷丽晖,王静. 可能性测度下的LTL模型检测并行化研究[J]. 计算机科学, 2018, 45(4): 71 -75, 88 .
[2] 夏庆勋,庄毅. 一种基于局部性原理的远程验证机制[J]. 计算机科学, 2018, 45(4): 148 -151, 162 .
[3] 厉柏伸,李领治,孙涌,朱艳琴. 基于伪梯度提升决策树的内网防御算法[J]. 计算机科学, 2018, 45(4): 157 -162 .
[4] 王欢,张云峰,张艳. 一种基于CFDs规则的修复序列快速判定方法[J]. 计算机科学, 2018, 45(3): 311 -316 .
[5] 孙启,金燕,何琨,徐凌轩. 用于求解混合车辆路径问题的混合进化算法[J]. 计算机科学, 2018, 45(4): 76 -82 .
[6] 张佳男,肖鸣宇. 带权混合支配问题的近似算法研究[J]. 计算机科学, 2018, 45(4): 83 -88 .
[7] 伍建辉,黄中祥,李武,吴健辉,彭鑫,张生. 城市道路建设时序决策的鲁棒优化[J]. 计算机科学, 2018, 45(4): 89 -93 .
[8] 刘琴. 计算机取证过程中基于约束的数据质量问题研究[J]. 计算机科学, 2018, 45(4): 169 -172 .
[9] 钟菲,杨斌. 基于主成分分析网络的车牌检测方法[J]. 计算机科学, 2018, 45(3): 268 -273 .
[10] 史雯隽,武继刚,罗裕春. 针对移动云计算任务迁移的快速高效调度算法[J]. 计算机科学, 2018, 45(4): 94 -99, 116 .