计算机科学 ›› 2014, Vol. 41 ›› Issue (8): 183-185.doi: 10.11896/j.issn.1002-137X.2014.08.040
金广龙,袁家斌
JIN Guang-long and YUAN Jia-bin
摘要： 基于最短向量问题的格公钥密码体制是典型的抗量子计算密码体制。格的唯一最短向量问题可转化为二面体群的隐含子群问题。有效地求解二面体群的隐含子群问题可攻破基于格的唯一最短向量问题的公钥密码体制。Kuperberg提出了二面体群隐含子群问题的半指数级量子算法。通过研究Kuperberg量子算法,利用概率量子克隆,文中提出了二面体群隐含子群问题的多项式时间量子算法。
| [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! |
|
||
首页