{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,13]],"date-time":"2026-07-13T10:07:28Z","timestamp":1783937248621,"version":"3.55.0"},"reference-count":81,"publisher":"Springer Science and Business Media LLC","issue":"6","license":[{"start":{"date-parts":[[2020,4,30]],"date-time":"2020-04-30T00:00:00Z","timestamp":1588204800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2020,4,30]],"date-time":"2020-04-30T00:00:00Z","timestamp":1588204800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/100014103","name":"Key Technology Research and Development Program of Shandong","doi-asserted-by":"publisher","award":["2018CXGC0701"],"award-info":[{"award-number":["2018CXGC0701"]}],"id":[{"id":"10.13039\/100014103","id-type":"DOI","asserted-by":"publisher"}]},{"name":"National Key Research and Development Program of China","award":["2018YFE0126000"],"award-info":[{"award-number":["2018YFE0126000"]}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["61972050"],"award-info":[{"award-number":["61972050"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Quantum Inf Process"],"published-print":{"date-parts":[[2020,6]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>In typical well-known cryptosystem, the hardness of classical problems plays a fundamental role in ensuring its security. While, with the booming of quantum computation, some classical hard problems tend to be vulnerable when confronted with the already-known quantum attacks, as a result, it is necessary to develop the post-quantum cryptosystem to resist the quantum attacks. With the purpose to bridge the two disciplines, it is significant to summarize known quantum algorithms and their threats toward these cryptographic intractable problems from a perspective of cryptanalysis. In this paper, we discussed the designing methodology, algorithm framework and latest progress of the mathematic hard problems on which the typical cryptosystems depend, including integer factorization problem, discrete logarithmic problem and its variants, lattice problem, dihedral hidden subgroup problems and extrapolated dihedral coset problem. It illustrated the reason why some cryptosystems such as RSA and ECC are not resistant to quantum attacks, yet some of them like lattice cryptosystems remain intact facing quantum attacks.<\/jats:p>","DOI":"10.1007\/s11128-020-02673-x","type":"journal-article","created":{"date-parts":[[2020,4,30]],"date-time":"2020-04-30T08:03:30Z","timestamp":1588233810000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":34,"title":["Quantum algorithms for typical hard problems: a perspective of cryptanalysis"],"prefix":"10.1007","volume":"19","author":[{"given":"Jingwen","family":"Suo","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Licheng","family":"Wang","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Sijia","family":"Yang","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Wenjie","family":"Zheng","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jiankang","family":"Zhang","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2020,4,30]]},"reference":[{"issue":"2","key":"2673_CR1","doi-asserted-by":"publisher","first-page":"120","DOI":"10.1145\/359340.359342","volume":"21","author":"RL Rivest","year":"1978","unstructured":"Rivest, R.L., Shamir, A., Adleman, L.: A method for obtaining digital signatures and public-key cryptosystems. Commun. ACM. 21(2), 120\u2013126 (1978)","journal-title":"Commun. ACM."},{"key":"2673_CR2","unstructured":"Miller, V.S.: Use of elliptic curves in cryptography. In: Advances in Cryptology-CRYPTO\u201985, Santa Barbara, California, USA, pp. 18\u201322 (1985)"},{"key":"2673_CR3","unstructured":"Shor, P.W.: Algorithms for quantum computation: Discrete logarithms and factoring. In: Proceedings 35th Annual Symposium on Foundations of Computer Science, pp. 124\u2013134 (1994)"},{"key":"2673_CR4","doi-asserted-by":"crossref","unstructured":"Grover, L.K.: A fast quantum mechanical algorithm for database search. arXiv:quant-ph\/9605043 (1996)","DOI":"10.1145\/237814.237866"},{"issue":"3","key":"2673_CR5","doi-asserted-by":"publisher","first-page":"738","DOI":"10.1137\/S0097539703440678","volume":"33","author":"O Regev","year":"2004","unstructured":"Regev, O.: Quantum computation and lattice problems. SIAM J. Comput. 33(3), 738\u2013760 (2004)","journal-title":"SIAM J. Comput."},{"key":"2673_CR6","unstructured":"Loceff, M.: A course in quantum computing (for the community college). Foothill College.https:\/\/scholar.google.com\/scholar?cluster=18303662284423939245&hl=zh-CN&as_sdt=2005&sciodt=0,5 (2015)"},{"key":"2673_CR7","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511976667","volume-title":"Quantum Computation and Quantum Information","author":"MA Nielsen","year":"2012","unstructured":"Nielsen, M.A., Chuang, I.: Quantum Computation and Quantum Information. Cambridge University Press, England (2012)"},{"issue":"3","key":"2673_CR8","doi-asserted-by":"publisher","first-page":"82","DOI":"10.1007\/s11128-017-1515-0","volume":"16","author":"S Zhou","year":"2017","unstructured":"Zhou, S., Loke, T., Izaac, J.A., Wang, J.B.: Quantum fourier transform in computational basis. Quantum Inf. Process. 16(3), 82 (2017)","journal-title":"Quantum Inf. Process."},{"key":"2673_CR9","unstructured":"Nam, Y., Su, Y., Maslov, D.: Approximate quantum fourier transform with O(nlogn) T-gates. arXiv:1803.04933 (2018)"},{"issue":"1","key":"2673_CR10","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1103\/RevModPhys.82.1","volume":"82","author":"AM Childs","year":"2010","unstructured":"Childs, A.M., Van Dam, W.: Quantum algorithms for algebraic problems. Rev. Mod. Phys. 82(1), 1 (2010)","journal-title":"Rev. Mod. Phys."},{"issue":"5","key":"2673_CR11","doi-asserted-by":"publisher","first-page":"1474","DOI":"10.1137\/S0097539796298637","volume":"26","author":"DR Simon","year":"1997","unstructured":"Simon, D.R.: On the power of quantum computation. SIAM J. Comput. 26(5), 1474\u20131483 (1997)","journal-title":"SIAM J. Comput."},{"issue":"10","key":"2673_CR12","doi-asserted-by":"publisher","first-page":"102501","DOI":"10.1007\/s11432-017-9468-y","volume":"61","author":"X Dong","year":"2018","unstructured":"Dong, X., Wang, X.: Quantum key-recovery attack on feistel structures. Sci. China Inf. Sci. 61(10), 102501 (2018)","journal-title":"Sci. China Inf. Sci."},{"key":"2673_CR13","doi-asserted-by":"publisher","first-page":"7088","DOI":"10.1007\/978-0-387-30440-3_423","volume-title":"Encyclopedia of Complexity and Systems Science","author":"Michele Mosca","year":"2009","unstructured":"Mosca, M.: Quantum algorithms. arXiv:0808.0369v1 (2009)"},{"key":"2673_CR14","volume-title":"The joy of factoring","author":"SS Wagstaff","year":"2013","unstructured":"Wagstaff, S.S.: The joy of factoring, vol. 68. American Mathematical Society, Providence (2013)"},{"key":"2673_CR15","doi-asserted-by":"crossref","unstructured":"Lenstra, A.K., Lenstra Jr., H.W., Manasse, M.S., Pollard, J.M.: The number field sieve. In: Proceedings of the Twenty-Second Annual ACM Symposium on Theory of Computing, pp. 564\u2013572 (1990)","DOI":"10.1145\/100216.100295"},{"issue":"1","key":"2673_CR16","doi-asserted-by":"publisher","first-page":"70311","DOI":"10.1007\/s11433-018-9277-4","volume":"62","author":"SJ Wei","year":"2019","unstructured":"Wei, S.J., Xin, T., Long, G.L.: Erratum to: Efficient universal quantum channel simulation in IBM\u2019s cloud quantum computer. Sci. China Phys. Mech. Astron. 62(1), 70311 (2019)","journal-title":"Sci. China Phys. Mech. Astron."},{"issue":"1","key":"2673_CR17","doi-asserted-by":"publisher","first-page":"120305","DOI":"10.1007\/s11467-016-0643-9","volume":"12","author":"HL Huang","year":"2017","unstructured":"Huang, H.L., Zhao, Y.W., Li, T., Li, F.G., Du, Y.T., Fu, X.Q., Zhang, S., Wang, X., Bao, W.S.: Homomorphic encryption experiments on IBMs cloud quantum computing platform. Front. Phys. 12(1), 120305 (2017)","journal-title":"Front. Phys."},{"issue":"13","key":"2673_CR18","doi-asserted-by":"publisher","first-page":"130501","DOI":"10.1103\/PhysRevLett.108.130501","volume":"108","author":"N Xu","year":"2012","unstructured":"Xu, N., Zhu, J., Lu, D., Zhou, X., Peng, X., Du, J.: Quantum factorization of 143 on a dipolar-coupling nuclear magnetic resonance system. Phys. Rev. Lett. 108(13), 130501 (2012)","journal-title":"Phys. Rev. Lett."},{"issue":"2","key":"2673_CR19","doi-asserted-by":"publisher","first-page":"303","DOI":"10.1137\/S0036144598347011","volume":"41","author":"PW Shor","year":"1999","unstructured":"Shor, P.W.: Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM Rev. 41(2), 303\u2013332 (1999)","journal-title":"SIAM Rev."},{"issue":"6866","key":"2673_CR20","doi-asserted-by":"publisher","first-page":"883","DOI":"10.1038\/414883a","volume":"414","author":"LM Vandersypen","year":"2001","unstructured":"Vandersypen, L.M., Steffen, M., Breyta, G., Yannoni, C.S., Sherwood, M.H., Chuang, I.L.: Experimental realization of Shor\u2019s quantum factoring algorithm using nuclear magnetic resonance. Nature. 414(6866), 883\u2013887 (2001)","journal-title":"Nature."},{"issue":"11","key":"2673_CR21","doi-asserted-by":"publisher","first-page":"773","DOI":"10.1038\/nphoton.2012.259","volume":"6","author":"E Martin-Lopez","year":"2012","unstructured":"Martin-Lopez, E., Laing, A., Lawson, T., Alvarez, R., Zhou, X.Q., O\u2019brien, J.L.: Experimental realization of Shor\u2019s quantum factoring algorithm using qubit recycling. Nat. Photonics 6(11), 773 (2012)","journal-title":"Nat. Photonics"},{"issue":"10","key":"2673_CR22","doi-asserted-by":"publisher","first-page":"3023","DOI":"10.1038\/srep03023","volume":"3","author":"MR Geller","year":"2013","unstructured":"Geller, M.R., Zhou, Z.: Factoring 51 and 85 with 8 qubits. Sci. Rep. 3(10), 3023 (2013)","journal-title":"Sci. Rep."},{"key":"2673_CR23","unstructured":"Gidney, C.: Factoring with n+2 clean qubits and n-1 dirty qubits. arXiv:1706.07884 (2017)"},{"issue":"2","key":"2673_CR24","doi-asserted-by":"publisher","first-page":"1034","DOI":"10.1103\/PhysRevA.54.1034","volume":"54","author":"D Beckman","year":"1996","unstructured":"Beckman, D., Chari, A.N., Devabhaktuni, S., Preskill, J.: Efficient networks for quantum factoring. Phys. Rev. A 54(2), 1034\u20131063 (1996)","journal-title":"Phys. Rev. A"},{"issue":"1","key":"2673_CR25","doi-asserted-by":"publisher","first-page":"147","DOI":"10.1103\/PhysRevA.54.147","volume":"54","author":"V Vedral","year":"1996","unstructured":"Vedral, V., Barenco, A., Ekert, A.: Quantum networks for elementary arithmetic operations. Phys. Rev. A 54(1), 147\u2013153 (1996)","journal-title":"Phys. Rev. A"},{"key":"2673_CR26","doi-asserted-by":"crossref","unstructured":"Beauregard, S.: Circuit for Shor\u2019s algorithm using 2n+3 qubits. arXiv:quant-ph\/0205095 (2002)","DOI":"10.26421\/QIC3.2-8"},{"issue":"2","key":"2673_CR27","first-page":"184","volume":"6","author":"Y Takahashi","year":"2006","unstructured":"Takahashi, Y., Kunihiro, N.: A quantum circuit for Shor\u2019s factoring algorithm using 2n+2 qubits. Quantum Inf. Comput. 6(2), 184\u2013192 (2006)","journal-title":"Quantum Inf. Comput."},{"key":"2673_CR28","doi-asserted-by":"crossref","unstructured":"H\u00e4ner, T., Roetteler, M., Svore, K. M.: Factoring using 2n+2 qubits with Toffoli based modular multiplication. arXiv:1611.07995 (2016)","DOI":"10.26421\/QIC17.7-8-7"},{"issue":"1","key":"2673_CR29","doi-asserted-by":"publisher","first-page":"015002","DOI":"10.1103\/RevModPhys.90.015002","volume":"90","author":"T Albash","year":"2016","unstructured":"Albash, T., Lidar, D.A.: Adiabatic quantum computing. Rev. Mod. Phys. 90(1), 015002 (2016)","journal-title":"Rev. Mod. Phys."},{"issue":"5516","key":"2673_CR30","doi-asserted-by":"publisher","first-page":"472","DOI":"10.1126\/science.1057726","volume":"292","author":"E Farhi","year":"2001","unstructured":"Farhi, E., Goldstone, J., Gutmann, S., Lapan, J., Lundgren, A., Preda, D.: A quantum adiabatic evolution algorithm applied to random instances of an NP-complete problem. Science 292(5516), 472\u2013476 (2001)","journal-title":"Science"},{"issue":"4","key":"2673_CR31","doi-asserted-by":"publisher","first-page":"047411","DOI":"10.1007\/s11433-017-9156-1","volume":"61","author":"T Wang","year":"2018","unstructured":"Wang, T., Zhang, Z., Xiang, L., Gong, Z., Wu, J., Yin, Y.: Simulating a topological transition in a superconducting phase qubit by fast adiabatic trajectories. Sci. China Phys. Mech. Astron. 61(4), 047411 (2018)","journal-title":"Sci. China Phys. Mech. Astron."},{"key":"2673_CR32","unstructured":"Burges, C.J.: Factoring as optimization. Microsoft Research MSR-TR-200 (2002)"},{"issue":"6","key":"2673_CR33","doi-asserted-by":"publisher","first-page":"60311","DOI":"10.1007\/s11433-018-9307-1","volume":"62","author":"W Peng","year":"2019","unstructured":"Peng, W., Wang, B., Hu, F., Wang, Y., Fang, X., Chen, X., Wang, C.: Factoring larger integers with fewer qubits via quantum annealing with optimized parameters. Sci. China Phys. Mech. Astron. 62(6), 60311 (2019)","journal-title":"Sci. China Phys. Mech. Astron."},{"issue":"2","key":"2673_CR34","doi-asserted-by":"publisher","first-page":"26","DOI":"10.1007\/s12043-018-1684-0","volume":"92","author":"S Pal","year":"2019","unstructured":"Pal, S., Moitra, S., Anjusha, V.S., Kumar, A., Mahesh, T.S.: Hybrid scheme for factorisation: factoring 551 using a 3-qubit NMR quantum adiabatic processor. Pramana 92(2), 26 (2019)","journal-title":"Pramana"},{"issue":"22","key":"2673_CR35","doi-asserted-by":"publisher","first-page":"220405","DOI":"10.1103\/PhysRevLett.101.220405","volume":"101","author":"X Peng","year":"2008","unstructured":"Peng, X., Liao, Z., Xu, N., Qin, G., Zhou, X., Suter, D., Du, J.: Quantum adiabatic algorithm for factorization and its experimental implementation. Phys. Rev. Lett. 101(22), 220405 (2008)","journal-title":"Phys. Rev. Lett."},{"key":"2673_CR36","doi-asserted-by":"publisher","first-page":"43048","DOI":"10.1038\/srep43048","volume":"7","author":"R Dridi","year":"2017","unstructured":"Dridi, R., Alghassi, H.: Prime factorization using quantum annealing and computational algebraic geometry. Sci. Rep. 7, 43048 (2017)","journal-title":"Sci. Rep."},{"issue":"3","key":"2673_CR37","doi-asserted-by":"publisher","first-page":"30003","DOI":"10.1209\/0295-5075\/118\/30003","volume":"118","author":"I Hen","year":"2017","unstructured":"Hen, I.: Realizable quantum adiabatic search. EPL (Europhys. Lett.) 118(3), 30003 (2017)","journal-title":"EPL (Europhys. Lett.)"},{"issue":"8","key":"2673_CR38","doi-asserted-by":"publisher","first-page":"80311","DOI":"10.1007\/s11433-017-9058-7","volume":"60","author":"H Li","year":"2017","unstructured":"Li, H., Liu, Y., Long, G.: Experimental realization of single-shot nonadiabatic holonomic gates in nuclear spins. Sci. China Phys. Mech. Astron. 60(8), 80311 (2017)","journal-title":"Sci. China Phys. Mech. Astron."},{"key":"2673_CR39","first-page":"31","volume":"2","author":"C Wang","year":"2012","unstructured":"Wang, C., Zhang, H.: Impact of commercial quantum computer on cryptography. Inf. Secur. Commun. Priv. 2, 31 (2012)","journal-title":"Inf. Secur. Commun. Priv."},{"key":"2673_CR40","unstructured":"Li, Z., Dattani, N.S., Chen, X., Liu, X., Wang, H., Tanburn, R., Du, J.: High-fidelity adiabatic quantum computation using the intrinsic Hamiltonian of a spin system: application to the experimental factorization of 291311. arXiv:1706.08061 (2017)"},{"key":"2673_CR41","doi-asserted-by":"publisher","first-page":"17667","DOI":"10.1038\/s41598-018-36058-z","volume":"8","author":"S Jiang","year":"2018","unstructured":"Jiang, S., Britt, K.A., McCaskey, A.J., Humble, T.S., Kais, S.: Quantum annealing for prime factorization. Sci. Rep. 8, 17667 (2018)","journal-title":"Sci. Rep."},{"issue":"4","key":"2673_CR42","first-page":"317","volume":"3","author":"J Proos","year":"2003","unstructured":"Proos, J., Zalka, C.: Shor\u2019s discrete logarithm quantum algorithm for elliptic curves. Quantum Inf. Comput. 3(4), 317\u2013344 (2003)","journal-title":"Quantum Inf. Comput."},{"key":"2673_CR43","volume-title":"Advances in Cryptology-CRYPTO\u201989: Proceedings","year":"1995","unstructured":"Brassard, G. (ed.): Advances in Cryptology-CRYPTO\u201989: Proceedings, vol. 435. Springer, Berlin (1995)"},{"issue":"7","key":"2673_CR44","first-page":"610","volume":"9","author":"D Maslov","year":"2009","unstructured":"Maslov, D., Mathew, J., Cheung, D., Pradhan, D.K.: An $$O(m^2)$$-depth quantum algorithm for the elliptic curve discrete logarithm problem over $${\\rm GF}(2^m)^a$$. Quantum Inf. Comput. 9(7), 610\u2013621 (2009)","journal-title":"Quantum Inf. Comput."},{"issue":"1","key":"2673_CR45","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1515\/gcc-2014-0003","volume":"6","author":"AD Myasnikov","year":"2014","unstructured":"Myasnikov, A.D., Ushakov, A.: Quantum algorithm for discrete logarithm problem for matrices over finite group rings. Groups Complex. Cryptol. 6(1), 31\u201336 (2014)","journal-title":"Groups Complex. Cryptol."},{"issue":"4","key":"2673_CR46","doi-asserted-by":"publisher","first-page":"405","DOI":"10.1515\/jmc-2013-0038","volume":"8","author":"AM Childs","year":"2014","unstructured":"Childs, A.M., Ivanyos, G.: Quantum computation of discrete logarithms in semigroups. J. Math. Cryptol. 8(4), 405\u2013416 (2014)","journal-title":"J. Math. Cryptol."},{"issue":"1","key":"2673_CR47","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1007\/s10623-015-0130-2","volume":"81","author":"M Banin","year":"2016","unstructured":"Banin, M., Tsaban, B.: A reduction of semigroup DLP to classic DLP. Des. Codes Cryptogr. 81(1), 75\u201382 (2016)","journal-title":"Des. Codes Cryptogr."},{"key":"2673_CR48","doi-asserted-by":"crossref","unstructured":"Ekera, M.: On post-processing in the quantum algorithm for computing short discrete logarithms. IACR Cryptology ePrint Archive, p. 1122 (2017)","DOI":"10.1007\/978-3-319-59879-6_20"},{"key":"2673_CR49","unstructured":"Ekera, M.: Revisiting shor\u2019s quantum algorithm for computing general discrete logarithms. arXiv:1905.09084 (2019)"},{"issue":"3","key":"2673_CR50","first-page":"301","volume":"26","author":"AA Moldovyan","year":"2018","unstructured":"Moldovyan, A.A., Moldovyan, N.A.: Post-quantum signature algorithms based on the hidden discrete logarithm problem. Comput. Sci. J. Mold. 26(3), 301\u2013313 (2018)","journal-title":"Comput. Sci. J. Mold."},{"key":"2673_CR51","unstructured":"Wang, F.: The hidden subgroup problem. arXiv:1008.0010 (2010)"},{"key":"2673_CR52","unstructured":"Kitaev, A.Y.: Quantum measurements and the Abelian stabilizer problem. arXiv:quant-ph\/9511026 (1995)"},{"key":"2673_CR53","doi-asserted-by":"crossref","unstructured":"Boneh, D., Lipton, R.J.: Quantum cryptanalysis of hidden linear functions. In: Annual International Cryptology Conference, pp. 424\u2013437 (1995)","DOI":"10.1007\/3-540-44750-4_34"},{"key":"2673_CR54","unstructured":"Brassard, G., Hoyer, P.: An exact quantum polynomial-time algorithm for Simon\u2019s problem. In: Proceedings of the Fifth Israeli Symposium on Theory of Computing and Systems, pp. 12\u201323 (1997)"},{"issue":"1969","key":"2673_CR55","doi-asserted-by":"publisher","first-page":"323","DOI":"10.1098\/rspa.1998.0163","volume":"454","author":"R Jozsa","year":"1998","unstructured":"Jozsa, R.: Quantum algorithms and the Fourier transform. Proc. R. Soc. Lond. Ser. A Math. Phys. Eng. Sci. 454(1969), 323\u2013337 (1998)","journal-title":"Proc. R. Soc. Lond. Ser. A Math. Phys. Eng. Sci."},{"key":"2673_CR56","doi-asserted-by":"publisher","first-page":"174","DOI":"10.1007\/3-540-49208-9_15","volume-title":"Quantum Computing and Quantum Communications","author":"Michele Mosca","year":"1999","unstructured":"Mosca, M., Ekert, A.: The hidden subgroup problem and eigenvalue estimation on a quantum computer. In: NASA International Conference on Quantum Computing and Quantum Communications, pp. 174\u2013188 (1998)"},{"key":"2673_CR57","unstructured":"Mosca, M.: Quantum computer algorithms. PhD thesis, University of Oxford (1999)"},{"issue":"2","key":"2673_CR58","doi-asserted-by":"publisher","first-page":"34","DOI":"10.1109\/5992.909000","volume":"3","author":"R Jozsa","year":"2001","unstructured":"Jozsa, R.: Quantum factoring, discrete logarithms, and the hidden subgroup problem. Comput. Sci. Eng. 3(2), 34 (2001)","journal-title":"Comput. Sci. Eng."},{"key":"2673_CR59","doi-asserted-by":"crossref","unstructured":"Cheung, K. K., Mosca, M.: Decomposing finite abelian groups. arXiv:cs\/0101004 (2001)","DOI":"10.26421\/QIC1.3-2"},{"key":"2673_CR60","unstructured":"Damg\u00e5rd, I.: QIP note: on the quantum Fourier transform and applications. Published on https:\/\/users-cs.au.dk\/~ivan\/fourier.pdf (2004). Accessed 26 June 2019"},{"key":"2673_CR61","unstructured":"Van Dam, W., Hallgren, S., Ip, L.: Quantum algorithms for some hidden shift problems. In: Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, Baltimore, Maryland, USA, pp. 489\u2013498 (2003)"},{"issue":"3","key":"2673_CR62","doi-asserted-by":"publisher","first-page":"763","DOI":"10.1137\/S009753970343141X","volume":"36","author":"W Van Dam","year":"2006","unstructured":"Van Dam, W., Hallgren, S., Ip, L.: Quantum algorithms for some hidden shift problems. SIAM J. Comput. 36(3), 763\u2013778 (2006)","journal-title":"SIAM J. Comput."},{"issue":"4","key":"2673_CR63","doi-asserted-by":"publisher","first-page":"413","DOI":"10.1007\/s00453-002-0975-4","volume":"34","author":"W Van Dam","year":"2002","unstructured":"Van Dam, W.: Quantum algorithms for weighing matrices and quadratic residues. Algorithmica. 34(4), 413\u2013428 (2002)","journal-title":"Algorithmica."},{"key":"2673_CR64","unstructured":"Van Dam, W., Hallgren, S.: Efficient quantum algorithms for shifted quadratic character problems. arXiv:quant-ph\/0011067 (2000)"},{"key":"2673_CR65","doi-asserted-by":"crossref","unstructured":"Childs, A.M., Schulman, L.J., Vazirani, U.V.: Quantum algorithms for hidden nonlinear structures. In: 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS\u201907), pp. 395\u2013404 (2007)","DOI":"10.1109\/FOCS.2007.18"},{"key":"2673_CR66","doi-asserted-by":"crossref","unstructured":"R\u00f6tteler, M.: Quantum algorithms for highly non-linear boolean functions. In: Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2010, Austin, Texas, USA, pp. 448\u2013457 (2010)","DOI":"10.1137\/1.9781611973075.37"},{"key":"2673_CR67","first-page":"158","volume-title":"Lecture Notes in Computer Science","author":"Dmitry Gavinsky","year":"2011","unstructured":"Gavinsky, D., Roetteler, M., Roland, J.: Quantum algorithm for the Boolean hidden shift problem. In: International Computing and Combinatorics Conference, pp. 158\u2013167. Springer, Berlin (2011)"},{"issue":"3","key":"2673_CR68","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/2493252.2493256","volume":"5","author":"M Ozols","year":"2013","unstructured":"Ozols, M., Roetteler, M., Roland, J.: Quantum rejection sampling. ACM Trans. Comput. Theory (TOCT) 5(3), 1\u201333 (2013)","journal-title":"ACM Trans. Comput. Theory (TOCT)"},{"issue":"3","key":"2673_CR69","doi-asserted-by":"publisher","first-page":"239","DOI":"10.1006\/aama.2000.0699","volume":"25","author":"M Ettinger","year":"2000","unstructured":"Ettinger, M., H\u00f8yer, P.: On quantum algorithms for non-commutative hidden subgroups. Adv. Appl. Math. 25(3), 239\u2013251 (2000)","journal-title":"Adv. Appl. Math."},{"key":"2673_CR70","unstructured":"Kuperberg, G.: Another subexponential-time quantum algorithm for the dihedral hidden subgroup problem. arXiv:1112.3333 (2011)"},{"key":"2673_CR71","unstructured":"Roetteler, M.: Quantum algorithms for abelian difference sets and applications to dihedral hidden subgroups. arXiv:1608.02005 (2016)"},{"key":"2673_CR72","doi-asserted-by":"crossref","unstructured":"Gentry, C., Peikert, C., Vaikuntanathan, V.: Trapdoors for hard lattices and new cryptographic constructions. In: Proceedings of the Fortieth Annual ACM Symposium on Theory of Computing, pp. 197\u2013206 (2008)","DOI":"10.1145\/1374376.1374407"},{"issue":"6","key":"2673_CR73","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/1568318.1568324","volume":"56","author":"Oded Regev","year":"2009","unstructured":"Regev, O.: On lattices, learning with errors, random linear codes, and cryptography. J. ACM (JACM). 56(6), 34 (2009)","journal-title":"Journal of the ACM"},{"key":"2673_CR74","doi-asserted-by":"publisher","first-page":"151","DOI":"10.1007\/11496137_11","volume-title":"Applied Cryptography and Network Security","author":"Vladimir Shpilrain","year":"2005","unstructured":"Shpilrain, V., Ushakov, A.: Thompsons group and public key cryptography. In: International Conference on Applied Cryptography and Network Security, pp. 151\u2013163 (2005)"},{"key":"2673_CR75","doi-asserted-by":"crossref","unstructured":"Regev, O.: On lattices, learning with errors, random linear codes, and cryptography. In: Proceedings of the 37th Annual ACM Symposium on Theory of Computing, Baltimore, MD, USA, pp. 84\u201393 (2005)","DOI":"10.1145\/1060590.1060603"},{"issue":"1","key":"2673_CR76","doi-asserted-by":"publisher","first-page":"170","DOI":"10.1137\/S0097539703436345","volume":"35","author":"G Kuperberg","year":"2005","unstructured":"Kuperberg, G.: A subexponential-time quantum algorithm for the dihedral hidden subgroup problem. SIAM J. Comput. 35(1), 170\u2013188 (2005)","journal-title":"SIAM J. Comput."},{"key":"2673_CR77","unstructured":"Li, F., Bao, W., Fu, X., Zhang, Y., Li, T.: A reduction from LWE problem to dihedral coset problem. arXiv:1305.3769 (2013)"},{"key":"2673_CR78","unstructured":"Eldar, L., Shor, P.W.: An efficient quantum algorithm for a variant of the closest lattice-vector problem. arXiv:1611.06999 (2016)"},{"key":"2673_CR79","unstructured":"Eldar, L., Shor, P. W.: A discrete Fourier transform on lattices with quantum applications. arXiv:1703.02515 (2017)"},{"key":"2673_CR80","doi-asserted-by":"publisher","first-page":"702","DOI":"10.1007\/978-3-319-76581-5_24","volume-title":"Public-Key Cryptography \u2013 PKC 2018","author":"Zvika Brakerski","year":"2018","unstructured":"Brakerski, Z., Kirshanova, E., Stehl\u00e9, D., Wen, W.: Learning with errors and extrapolated dihedral cosets. In: IACR International Workshop on Public Key Cryptography, pp. 702\u2013727 (2018)"},{"key":"2673_CR81","unstructured":"Grover, L., Rudolph, T.: Creating superpositions that correspond to efficiently integrable probability distributions. arXiv: quant-ph\/0208112 (2002)"}],"container-title":["Quantum Information Processing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11128-020-02673-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s11128-020-02673-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11128-020-02673-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,10,22]],"date-time":"2022-10-22T17:24:04Z","timestamp":1666459444000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s11128-020-02673-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,4,30]]},"references-count":81,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2020,6]]}},"alternative-id":["2673"],"URL":"https:\/\/doi.org\/10.1007\/s11128-020-02673-x","relation":{},"ISSN":["1570-0755","1573-1332"],"issn-type":[{"value":"1570-0755","type":"print"},{"value":"1573-1332","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,4,30]]},"assertion":[{"value":"27 January 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"7 April 2020","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"30 April 2020","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"178"}}