{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,25]],"date-time":"2026-04-25T02:32:12Z","timestamp":1777084332483,"version":"3.51.4"},"reference-count":80,"publisher":"Springer Science and Business Media LLC","issue":"2-3","license":[{"start":{"date-parts":[[2015,4,14]],"date-time":"2015-04-14T00:00:00Z","timestamp":1428969600000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Des. Codes Cryptogr."],"published-print":{"date-parts":[[2015,12]]},"DOI":"10.1007\/s10623-015-0067-5","type":"journal-article","created":{"date-parts":[[2015,4,13]],"date-time":"2015-04-13T05:50:02Z","timestamp":1428904202000},"page":"375-400","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":65,"title":["Finding shortest lattice vectors faster using quantum search"],"prefix":"10.1007","volume":"77","author":[{"given":"Thijs","family":"Laarhoven","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Michele","family":"Mosca","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Joop","family":"van de Pol","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2015,4,14]]},"reference":[{"key":"67_CR1","doi-asserted-by":"crossref","unstructured":"Aggarwal D., Dadush D., Regev O., Stephens-Davidowitz N.: Solving the shortest vector problem in $$2^n$$ 2 n time via discrete Gaussian sampling. In: STOC (2015).","DOI":"10.1145\/2746539.2746606"},{"key":"67_CR2","doi-asserted-by":"crossref","unstructured":"Ajtai M.: The shortest vector problem in $$L_2$$ L 2 is NP-hard for randomized reductions. In: STOC, pp. 10\u201319 (1998).","DOI":"10.1145\/276698.276705"},{"key":"67_CR3","doi-asserted-by":"crossref","unstructured":"Ajtai M., Kumar R., Sivakumar D.: A sieve algorithm for the shortest lattice vector problem. In: STOC, pp. 601\u2013610 (2001).","DOI":"10.1145\/380752.380857"},{"key":"67_CR4","doi-asserted-by":"crossref","unstructured":"Ambainis A.: Quantum walk algorithm for element distinctness. In: FOCS, pp. 22\u201331 (2003).","DOI":"10.1109\/FOCS.2004.54"},{"key":"67_CR5","doi-asserted-by":"crossref","unstructured":"Andoni A., Indyk P., Nguyen H.L., Razenshteyn I.: Beyond locality-sensitive hashing. In: SODA, pp. 1018\u20131028 (2014).","DOI":"10.1137\/1.9781611973402.76"},{"key":"67_CR6","doi-asserted-by":"crossref","unstructured":"Andoni A., Razenshteyn I.: Optimal data-dependent hashing for approximate near neighbors. In: STOC (2015).","DOI":"10.1145\/2746539.2746553"},{"key":"67_CR7","doi-asserted-by":"crossref","unstructured":"Antipa A., Brown D., Gallant R., Lambert R., Struik R., Vanstone S.: Accelerated verification of ECDSA signatures. In: SAC, pp. 307\u2013318 (2006).","DOI":"10.1007\/11693383_21"},{"key":"67_CR8","unstructured":"Aono Y., Naganuma K.: Heuristic improvements of BKZ 2.0. IEICE. Tech. Rep. 112(211), 15\u201322 (2012)."},{"key":"67_CR9","doi-asserted-by":"crossref","unstructured":"Becker A., Gama N., Joux A.: A sieve algorithm based on overlattices. In: ANTS, pp. 49\u201370 (2014).","DOI":"10.1112\/S1461157014000229"},{"key":"67_CR10","doi-asserted-by":"crossref","unstructured":"Bennett C.H., Bernstein E., Brassard G., Vazirani V.: Strengths and weaknesses of quantum computing. SIAM J. Comput. 26(5), 1510\u20131523 (1997).","DOI":"10.1137\/S0097539796300933"},{"key":"67_CR11","unstructured":"Bernstein D.J.: Cost analysis of hash collisions: will quantum computers make SHARCs obsolete? In: SHARCS (2009)."},{"key":"67_CR12","doi-asserted-by":"crossref","unstructured":"Bernstein D.J., Buchmann J., Dahmen E. (eds.): Post-quantum Cryptography. Springer, Heidelberg (2008).","DOI":"10.1007\/978-3-540-88702-7"},{"key":"67_CR13","doi-asserted-by":"crossref","unstructured":"Blake I.F., Fuji-Hara R., Mullin R.C., Vanstone S.A.: Computing logarithms in finite fields of characteristic two. SIAM J. Algebraic Discrete Methods 5(2), 276\u2013285 (1984).","DOI":"10.1137\/0605029"},{"key":"67_CR14","doi-asserted-by":"crossref","unstructured":"Boneh D., Venkatesan R.: Hardness of computing the most significant bits of secret keys in Diffie-Hellman and related schemes. In: CRYPTO, pp. 129\u2013142 (1996).","DOI":"10.1007\/3-540-68697-5_11"},{"key":"67_CR15","doi-asserted-by":"crossref","unstructured":"Boyer M., Brassard G., H\u00f8yer P., Tapp A.: Tight bounds on quantum searching. Fortschr. Phys. 46, 493\u2013505 (1998).","DOI":"10.1002\/(SICI)1521-3978(199806)46:4\/5<493::AID-PROP493>3.0.CO;2-P"},{"key":"67_CR16","doi-asserted-by":"crossref","unstructured":"Brakerski Z., Gentry C., Vaikuntanathan V.: Fully homomorphic encryption without bootstrapping. In: ITCS, pp. 309\u2013325 (2012).","DOI":"10.1145\/2090236.2090262"},{"key":"67_CR17","doi-asserted-by":"crossref","unstructured":"Brassard G., H\u00f8yer P., Tapp A.: Quantum cryptanalysis of hash and claw-free functions. In: LATIN, pp. 163\u2013169 (1998).","DOI":"10.1007\/BFb0054319"},{"key":"67_CR18","doi-asserted-by":"crossref","unstructured":"Brassard G., H\u00f8yer P., Mosca M., Tapp A.: Quantum amplitude amplification and estimation. In: AMS Contemporary Mathematics Series Millennium Volume Entitled Quantum Computation & Information, vol. 305 (2002).","DOI":"10.1090\/conm\/305\/05215"},{"key":"67_CR19","doi-asserted-by":"crossref","unstructured":"Buhrman B., D\u00fcrr C., Heiligman M., H\u00f8yer P., Magniez F., Santha M., de Wolf R.: Quantum algorithms for element distinctness. SIAM J. Comput. 34(6), 1324\u20131330 (2005).","DOI":"10.1137\/S0097539702402780"},{"key":"67_CR20","doi-asserted-by":"crossref","unstructured":"Charikar M.S.: Similarity estimation techniques from rounding algorithms. In: STOC, pp. 380\u2013388 (2002).","DOI":"10.1145\/509907.509965"},{"key":"67_CR21","doi-asserted-by":"crossref","unstructured":"Chen Y., Nguyen P.Q.: BKZ 2.0: better lattice security estimates. In: ASIACRYPT, pp. 1\u201320 (2011).","DOI":"10.1007\/978-3-642-25385-0_1"},{"key":"67_CR22","doi-asserted-by":"crossref","unstructured":"Childs A.M., Van Dam W.: Quantum algorithms for algebraic problems. Rev. Mod. Phys. 82, 1\u201352 (2010).","DOI":"10.1103\/RevModPhys.82.1"},{"key":"67_CR23","unstructured":"Childs A.M., Jao D., Soukharev V.: Constructing elliptic curve isogenies in quantum subexponential time. arXiv:1012.4019 (2010)."},{"key":"67_CR24","doi-asserted-by":"crossref","unstructured":"Coppersmith D.: Small solutions to polynomial equations, and low exponent RSA vulnerabilities. J. Cryptol. 10(4), 233\u2013260 (1997).","DOI":"10.1007\/s001459900030"},{"key":"67_CR25","doi-asserted-by":"crossref","unstructured":"Coster M.J., Joux A., LaMacchia B.A., Odlyzko A.M., Schnorr C.P., Stern J.: Improved low-density subset sum algorithms. Comput. Complex. 2(2), 111\u2013128 (1992).","DOI":"10.1007\/BF01201999"},{"key":"67_CR26","doi-asserted-by":"crossref","unstructured":"Ducas L., Durmus A., Lepoint T., Lyubashevsky V.: Lattice signatures and bimodal Gaussians. In: CRYPTO, pp. 40\u201356 (2013).","DOI":"10.1007\/978-3-642-40041-4_3"},{"key":"67_CR27","doi-asserted-by":"crossref","unstructured":"Fincke U., Pohst M.: Improved methods for calculating vectors of short length in a lattice, including a complexity analysis. Math. Comput. 44, 463\u2013471 (1985).","DOI":"10.1090\/S0025-5718-1985-0777278-8"},{"key":"67_CR28","doi-asserted-by":"crossref","unstructured":"Galbraith S.D., Scott M.: Exponentiation in pairing-friendly groups using homomorphisms. In: Pairing-Based Cryptography, pp. 211\u2013224. Springer, Berlin (2008).","DOI":"10.1007\/978-3-540-85538-5_15"},{"key":"67_CR29","doi-asserted-by":"crossref","unstructured":"Gallant R.P., Lambert R.J., Vanstone S.A.: Faster point multiplication on elliptic curves with efficient endomorphisms. In: CRYPTO, pp. 190\u2013200 (2001).","DOI":"10.1007\/3-540-44647-8_11"},{"key":"67_CR30","doi-asserted-by":"crossref","unstructured":"Gama N., Nguyen P.Q.: Predicting lattice reduction. In: EUROCRYPT, pp. 31\u201351 (2008).","DOI":"10.1007\/978-3-540-78967-3_3"},{"key":"67_CR31","doi-asserted-by":"crossref","unstructured":"Gama N., Nguyen P.Q., Regev O.: Lattice enumeration using extreme pruning. In: EUROCRYPT, pp. 257\u2013278 (2010).","DOI":"10.1007\/978-3-642-13190-5_13"},{"key":"67_CR32","doi-asserted-by":"crossref","unstructured":"Gentry C.: Fully homomorphic encryption using ideal lattices. In: STOC, pp. 169\u2013178 (2009).","DOI":"10.1145\/1536414.1536440"},{"key":"67_CR33","doi-asserted-by":"crossref","unstructured":"Gentry C., Peikert C., Vaikuntanathan V.: Trapdoors for hard lattices and new cryptographic constructions. In: STOC, pp. 197\u2013206 (2008).","DOI":"10.1145\/1374376.1374407"},{"key":"67_CR34","doi-asserted-by":"crossref","unstructured":"Giovannetti V., Lloyd S., Maccone L.: Quantum random access memory. Phys. Rev. Lett. 100, 160501 (2008).","DOI":"10.1103\/PhysRevLett.100.160501"},{"key":"67_CR35","doi-asserted-by":"crossref","unstructured":"Grover L.K.: A fast quantum mechanical algorithm for database search. In: STOC, pp. 212\u2013219 (1996).","DOI":"10.1145\/237814.237866"},{"key":"67_CR36","unstructured":"Grover L.K., Rudolph T.: How significant are the known collision and element distinctness quantum algorithms? Quantum Inf. Comput. 4(3), 201\u2013206 (2004)."},{"key":"67_CR37","doi-asserted-by":"crossref","unstructured":"Hallgren S.: Polynomial-time quantum algorithms for Pell\u2019s equation and the principal ideal problem. J. ACM 54(1), 653\u2013658 (2007).","DOI":"10.1145\/1206035.1206039"},{"key":"67_CR38","doi-asserted-by":"crossref","unstructured":"Hanrot G., Pujol X., Stehl\u00e9 D.: Algorithms for the shortest and closest lattice vector problems. In: IWCC, pp. 159\u2013190 (2011).","DOI":"10.1007\/978-3-642-20901-7_10"},{"key":"67_CR39","doi-asserted-by":"crossref","unstructured":"Hoffstein J., Pipher J., Silverman J.: NTRU: a ring-based public key cryptosystem. In: ANTS, pp. 267\u2013288 (1998).","DOI":"10.1007\/BFb0054868"},{"key":"67_CR40","doi-asserted-by":"crossref","unstructured":"Ishiguro T., Kiyomoto S., Miyake Y., Takagi T.: Parallel Gauss Sieve algorithm: solving the SVP challenge over a $$128$$ 128 -dimensional ideal lattice. In: PKC, pp. 411\u2013428 (2014).","DOI":"10.1007\/978-3-642-54631-0_24"},{"key":"67_CR41","unstructured":"Jeffery S.: Collision finding with many classical or quantum processors. Master\u2019s thesis, University of Waterloo (2011)."},{"key":"67_CR42","unstructured":"Kabatiansky G., Levenshtein V.I.: On bounds for packings on a sphere and in space. Problemy Peredachi Informacii 14(1), 3\u201325 (1978)."},{"key":"67_CR43","doi-asserted-by":"crossref","unstructured":"Kannan R.: Improved algorithms for integer programming and related lattice problems. In: STOC, pp. 193\u2013206 (1983).","DOI":"10.1145\/800061.808749"},{"key":"67_CR44","doi-asserted-by":"crossref","unstructured":"Khot S.: Hardness of approximating the shortest vector problem in lattices. J. ACM 52(5), 789\u2013808 (2005).","DOI":"10.1145\/1089023.1089027"},{"key":"67_CR45","doi-asserted-by":"crossref","unstructured":"Kuperberg G.: A subexponential-time quantum algorithm for the dihedral hidden subgroup problem. SIAM J. Comput. 35(1), 170\u2013188 (2005).","DOI":"10.1137\/S0097539703436345"},{"key":"67_CR46","unstructured":"Kuperberg G.: Another subexponential-time quantum algorithm for the dihedral hidden subgroup problem. arXiv, Report 1112\/3333, pp. 1\u201310 (2011)."},{"key":"67_CR47","doi-asserted-by":"crossref","unstructured":"Laarhoven T.: Sieving for shortest vectors in lattices using angular locality-sensitive hashing. Cryptology ePrint Archive, Report 2014\/744 (2014).","DOI":"10.1007\/978-3-662-47989-6_1"},{"key":"67_CR48","unstructured":"Laarhoven T., De Weger B.: Sieving for shortest lattice vectors in time $$2^{0.298n}$$ 2 0.298 n using spherical locality-sensitive hashing. Cryptology ePrint Archive, Report 2015\/211 (2015)."},{"key":"67_CR49","unstructured":"Laarhoven T., van de Pol J., de Weger B.: Solving hard lattice problems and the security of lattice-based cryptosystems. Cryptology ePrint Archive, Report 2012\/533 (2012)."},{"key":"67_CR50","doi-asserted-by":"crossref","unstructured":"Laarhoven T., Mosca M., van de Pol J.: Solving the shortest vector problem in lattices faster using quantum search. In: PQCrypto, pp. 83\u2013101 (2013).","DOI":"10.1007\/978-3-642-38616-9_6"},{"key":"67_CR51","doi-asserted-by":"crossref","unstructured":"Lagarias J.C., Odlyzko A.M.: Solving low-density subset sum problems. J. ACM 32(1), 229\u2013246 (1985).","DOI":"10.1145\/2455.2461"},{"key":"67_CR52","doi-asserted-by":"crossref","unstructured":"Lenstra A.K., Lenstra H., Lov\u00e1sz L.: Factoring polynomials with rational coefficients. Math. Ann. 261(4), 515\u2013534 (1982).","DOI":"10.1007\/BF01457454"},{"key":"67_CR53","unstructured":"Lindner R., R\u00fcckert M., Baumann P., Nobach L.: Lattice challenge. Online at http:\/\/www.latticechallenge.org\/ (2014)."},{"key":"67_CR54","unstructured":"Liu M., Wang X., Xu G., Zheng X.: Shortest lattice vectors in the presence of gaps. Cryptology ePrint Archive, Report 2011\/039 (2011)."},{"key":"67_CR55","doi-asserted-by":"crossref","unstructured":"Ludwig C.: A faster lattice reduction method using quantum search. In: ISAAC, pp. 199\u2013208 (2003).","DOI":"10.1007\/978-3-540-24587-2_22"},{"key":"67_CR56","doi-asserted-by":"crossref","unstructured":"Lyubashevsky V.: Lattice signatures without trapdoors. In: EUROCRYPT, pp. 738\u2013755 (2012).","DOI":"10.1007\/978-3-642-29011-4_43"},{"key":"67_CR57","doi-asserted-by":"crossref","unstructured":"Menezes A.J., van Oorschot P.C., Vanstone S.A.: Handbook of Applied Cryptography. CRC Press, Boca Raton (1996).","DOI":"10.1201\/9781439821916"},{"key":"67_CR58","doi-asserted-by":"crossref","unstructured":"Micciancio D., Voulgaris P.: A deterministic single exponential time algorithm for most lattice problems based on Voronoi cell computations. In: STOC, pp. 351\u2013358 (2010).","DOI":"10.1145\/1806689.1806739"},{"key":"67_CR59","doi-asserted-by":"crossref","unstructured":"Micciancio D., Voulgaris P.: Faster exponential time algorithms for the shortest vector problem. In: SODA, pp. 1468\u20131480 (2010).","DOI":"10.1137\/1.9781611973075.119"},{"key":"67_CR60","unstructured":"Micciancio D., Peikert C.: Trapdoors for lattices: simpler, tighter, faster, smaller. In: EUROCRYPT, pp. 700\u2013718 (2012)."},{"key":"67_CR61","doi-asserted-by":"crossref","unstructured":"Mosca M.: Quantum algorithms. In: Encyclopedia of Complexity and Systems Science, pp. 7088\u20137118. Springer, New York (2009).","DOI":"10.1007\/978-0-387-30440-3_423"},{"key":"67_CR62","doi-asserted-by":"crossref","unstructured":"Nguyen P.Q., Vidick T.: Sieve algorithms for the shortest vector problem are practical. J. Math. Cryptogr. 2(2), 181\u2013207 (2008).","DOI":"10.1515\/JMC.2008.009"},{"key":"67_CR63","unstructured":"Plantard T., Schneider M.: Ideal lattice challenge. Online at http:\/\/latticechallenge.org\/ideallattice-challenge\/ (2014)."},{"key":"67_CR64","doi-asserted-by":"crossref","unstructured":"Pohst M.: On the computation of lattice vectors of minimal length, successive minima and reduced bases with applications. ACM SIGSAM Bull. 15(1), 37\u201344 (1981).","DOI":"10.1145\/1089242.1089247"},{"key":"67_CR65","unstructured":"Pujol X., Stehl\u00e9 D.: Solving the shortest lattice vector problem in time $$2^{2.465n}$$ 2 2.465 n . Cryptology ePrint Archive, Report 2009\/605 (2009)."},{"key":"67_CR66","doi-asserted-by":"crossref","unstructured":"Qu M., Vanstone S.A.: The knapsack problem in cryptography. Finite Fields 168, 291\u2013308 (1994).","DOI":"10.1090\/conm\/168\/01708"},{"key":"67_CR67","unstructured":"Regev O.: Lattices in computer science. Lecture notes for a course at the Tel Aviv University (2004)."},{"key":"67_CR68","doi-asserted-by":"crossref","unstructured":"Regev O.: On lattices, learning with errors, random linear codes, and cryptography. In: STOC, pp. 84\u201393 (2005).","DOI":"10.1145\/1060590.1060603"},{"key":"67_CR69","doi-asserted-by":"crossref","unstructured":"Santha M.: Quantum walk based search algorithms. In: TAMC, pp. 31\u201346 (2008).","DOI":"10.1007\/978-3-540-79228-4_3"},{"key":"67_CR70","doi-asserted-by":"crossref","unstructured":"Schneider M.: Sieving for short vectors in ideal lattices. In: AFRICACRYPT, pp. 375\u2013391 (2013).","DOI":"10.1007\/978-3-642-38553-7_22"},{"key":"67_CR71","unstructured":"Schneider M., Gama N., Baumann P., Nobach L.: SVP challenge. Online at http:\/\/latticechallenge.org\/svp-challenge (2014)."},{"key":"67_CR72","doi-asserted-by":"crossref","unstructured":"Schnorr C.P.: A hierarchy of polynomial time lattice basis reduction algorithms. Theor. Comput. Sci. 53(2\u20133), 201\u2013224 (1987).","DOI":"10.1016\/0304-3975(87)90064-8"},{"key":"67_CR73","doi-asserted-by":"crossref","unstructured":"Schnorr C.P., Euchner M.: Lattice basis reduction: improved practical algorithms and solving subset sum problems. Math. Program. 66(2\u20133), 181\u2013199 (1994).","DOI":"10.1007\/BF01581144"},{"key":"67_CR74","doi-asserted-by":"crossref","unstructured":"Schnorr C.P.: Lattice reduction by random sampling and birthday methods. In: STACS, pp. 145\u2013156 (2003).","DOI":"10.1007\/3-540-36494-3_14"},{"key":"67_CR75","doi-asserted-by":"crossref","unstructured":"Shor P.W.: Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM J. Comput. 26(5), 1484\u20131509 (1997).","DOI":"10.1137\/S0097539795293172"},{"key":"67_CR76","doi-asserted-by":"crossref","unstructured":"Smith J., Mosca M.: Algorithms for quantum computers. In: Handbook of Natural Computing, pp. 1451\u20131492. Springer, Berlin (2012).","DOI":"10.1007\/978-3-540-92910-9_43"},{"key":"67_CR77","unstructured":"van de Pol J.: Lattice-based cryptography. Master\u2019s thesis, Eindhoven University of Technology (2011)."},{"key":"67_CR78","doi-asserted-by":"crossref","unstructured":"Vanstone S.A., Zuccherato R.J.: Short RSA keys and their generation. J. Cryptol. 8(2), 101\u2013114 (1995).","DOI":"10.1007\/BF00190758"},{"key":"67_CR79","doi-asserted-by":"crossref","unstructured":"Wang X., Liu M., Tian C., Bi J.: Improved Nguyen-Vidick heuristic sieve algorithm for shortest vector problem. In: ASIACCS, pp. 1\u20139 (2011).","DOI":"10.1145\/1966913.1966915"},{"key":"67_CR80","doi-asserted-by":"crossref","unstructured":"Zhang F., Pan Y., Hu G.: A three-level sieve algorithm for the shortest vector problem. In: SAC, pp. 29\u201347 (2013).","DOI":"10.1007\/978-3-662-43414-7_2"}],"container-title":["Designs, Codes and Cryptography"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10623-015-0067-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10623-015-0067-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10623-015-0067-5","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,22]],"date-time":"2025-05-22T11:46:07Z","timestamp":1747914367000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10623-015-0067-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,4,14]]},"references-count":80,"journal-issue":{"issue":"2-3","published-print":{"date-parts":[[2015,12]]}},"alternative-id":["67"],"URL":"https:\/\/doi.org\/10.1007\/s10623-015-0067-5","relation":{},"ISSN":["0925-1022","1573-7586"],"issn-type":[{"value":"0925-1022","type":"print"},{"value":"1573-7586","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,4,14]]}}}