Abstract
By applying Grover’s quantum search algorithm to the lattice algorithms of Micciancio and Voulgaris, Nguyen and Vidick, Wang et al., and Pujol and Stehlé, we obtain improved asymptotic quantum results for solving the shortest vector problem. With quantum computers we can provably find a shortest vector in time 21.799n + o(n), improving upon the classical time complexity of 22.465n + o(n) of Pujol and Stehlé and the 22n + o(n) of Micciancio and Voulgaris, while heuristically we expect to find a shortest vector in time 20.312n + o(n), improving upon the classical time complexity of 20.384n + o(n) of Wang et al. These quantum complexities will be an important guide for the selection of parameters for post-quantum cryptosystems based on the hardness of the shortest vector problem.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Aharonov, D., Regev, O.: A Lattice Problem in Quantum NP. In: 44th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 210–219. IEEE Press, New York (2003)
Ajtai, M.: The Shortest Vector Problem in L 2 is NP-hard for Randomized Reductions. In: 30th Annual ACM Symposium on Theory of Computing (STOC), pp. 10–19. ACM, New York (1998)
Ajtai, M., Kumar, R., Sivakumar, D.: A Sieve Algorithm for the Shortest Lattice Vector Problem. In: 33rd Annual ACM Symposium on Theory of Computing (STOC), pp. 601–610. ACM, New York (2001)
Ambainis, A.: Quantum Walk Algorithm for Element Distinctness. In: 45th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 22–31. IEEE Press, New York (2003)
Aono, Y., Naganuma, K.: Heuristic Improvements of BKZ 2.0. IEICE Tech. Rep. 112(211), 15–22 (2012)
Bennett, C.H., Bernstein, E., Brassard, G., Vazirani, V.: Strengths and Weaknesses of Quantum Computing. SIAM J. Comput. 26(5), 1510–1523 (1997)
Bernstein, D.J.: Cost analysis of hash collisions: Will quantum computers make SHARCs obsolete? In: SHARCS 2009: Special-purpose Hardware for Attacking Cryptographic Systems (2009)
Buchmann, J., Ding, J. (eds.): PQCrypto 2008. LNCS, vol. 5299. Springer, Heidelberg (2008)
Boyer, M., Brassard, G., Høyer, P., Tapp, A.: Tight Bounds on Quantum Searching. Fortschritte der Physik 46, 493–505 (1998)
Brakerski, Z., Gentry, C., Vaikuntanathan, V.: Fully homomorphic encryption without bootstrapping. In: Goldwasser, S. (ed.) Innovations in Theoretical Computer Science, ITCS 2012, pp. 309–325. ACM (2012)
Brassard, G., Høyer, P., Tapp, A.: Quantum cryptanalysis of hash and claw-free functions. In: Lucchesi, C.L., Moura, A.V. (eds.) LATIN 1998. LNCS, vol. 1380, pp. 163–169. Springer, Heidelberg (1998)
Brassard, G., Høyer, P., Mosca, M., Tapp, A.: Quantum Amplitude Amplification and Estimation. AMS Contemporary Mathematics Series Millennium Vol. entitled Quantum Computation & Information, vol. 305 (2002)
Buhrman, B., Dürr, C., Heiligman, M., Høyer, P., Magniez, F., Santha, M., de Wolf, R.: Quantum Algorithms for Element Distinctness. SIAM J. Comput. 34(6), 1324–1330 (2005)
Chen, Y., Nguyen, P.Q.: BKZ 2.0: Better Lattice Security Estimates. In: Lee, D.H., Wang, X. (eds.) ASIACRYPT 2011. LNCS, vol. 7073, pp. 1–20. Springer, Heidelberg (2011)
Childs, A., Van Dam, W.: Quantum algorithms for algebraic problems. Rev. Mod. Phys. 82, 1–52 (2010)
Childs, A.M., Jao, D., Soukharev, V.: Constructing elliptic curve isogenies in quantum subexponential time. arXiv:1012.4019 (2010)
Fincke, U., Pohst, M.: Improved methods for calculating vectors of short length in a lattice, including a complexity analysis. Math. Comp. 44, 463–471 (1985)
Gama, N., Nguyen, P.Q.: Predicting lattice reduction. In: Smart, N.P. (ed.) EUROCRYPT 2008. LNCS, vol. 4965, pp. 31–51. Springer, Heidelberg (2008)
Gama, N., Nguyen, P.Q., Regev, O.: Lattice Enumeration Using Extreme Pruning. In: Gilbert, H. (ed.) EUROCRYPT 2010. LNCS, vol. 6110, pp. 257–278. Springer, Heidelberg (2010)
Gentry, C., Peikert, C., Vaikuntanathan, V.: Trapdoors for hard lattices and new cryptographic constructions. In: Dwork, C. (ed.) STOC 2008, pp. 197–206. ACM (2008)
Gentry, C.: A fully homomorphic encryption scheme (Doctoral dissertation, Stanford University) (2009)
Giovannetti, V., Lloyd, S., Maccone, L.: Quantum Random Access Memory. Phys. Rev. Lett. 100, 160501 (2008)
Grover, L.K.: A Fast Quantum Mechanical Algorithm for Database Search. In: 28th Annual ACM Symposium on Theory of Computing (STOC), pp. 212–219. ACM, New York (1996)
Grover, L., Rudolph, T.: How significant are the known collision and element distinctness quantum algorithms? Quantum Info. Comput. 4(3), 201–206 (2004)
Hallgren, S.: Polynomial-time quantum algorithms for Pell’s equation and the principal ideal problem. J. ACM. 54(1), 653–658 (2007)
Hanrot, G., Pujol, X., Stehlé, D.: Algorithms for the Shortest and Closest Lattice Vector Problems. In: Chee, Y.M., Guo, Z., Ling, S., Shao, F., Tang, Y., Wang, H., Xing, C. (eds.) IWCC 2011. LNCS, vol. 6639, pp. 159–190. Springer, Heidelberg (2011)
Hoffstein, J., Pipher, J., Silverman, J.H.: NTRU: A ring-based public key cryptosystem. In: Buhler, J.P. (ed.) ANTS 1998. LNCS, vol. 1423, pp. 267–288. Springer, Heidelberg (1998)
Jeffery, S.: Collision Finding with Many Classical or Quantum Processors. Master’s thesis, University of Waterloo (2011)
Kabatiansky, G., Levenshtein, V.I.: On Bounds for Packings on a Sphere and in Space. Problemy Peredachi Informacii 14(1), 3–25 (1978)
Kannan, R.: Improved Algorithms for Integer Programming and Related Lattice Problems. In: 15th Annual ACM Symposium on Theory of Computing (STOC), pp. 193–206. ACM, New York (1983)
Khot, S.: Hardness of approximating the shortest vector problem in lattices. Journal of the ACM 52(5), 789–808 (2005)
Kuo, P.C., Schneider, M., Dagdelen, Ö., Reichelt, J., Buchmann, J., Cheng, C.M., Yang, B.Y.: Extreme Enumeration on GPU and in Clouds. In: Preneel, B., Takagi, T. (eds.) CHES 2011. LNCS, vol. 6917, pp. 176–191. Springer, Heidelberg (2011)
Kuperberg, G.: A Subexponential-Time Quantum Algorithm for the Dihedral Hidden Subgroup Problem. SIAM J. Comput. 35(1), 170–188 (2005)
Kuperberg, G.: Another Subexponential-Time Quantum Algorithm for the Dihedral Hidden Subgroup Problem. arXiv, Report 1112/3333, pp. 1–10 (2011)
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, pp. 1–43 (2012)
TU Darmstadt Lattice Challenge, http://www.latticechallenge.org/
Lenstra, A.K., Lenstra, H., Lovász, L.: Factoring Polynomials with Rational Coefficients. Math. Ann. 261(4), 515–534 (1982)
Ludwig, C.: A Faster Lattice Reduction Method Using Quantum Search. In: Ibaraki, T., Katoh, N., Ono, H. (eds.) ISAAC 2003. LNCS, vol. 2906, pp. 199–208. Springer, Heidelberg (2003)
Lyubashevsky, V.: Lattice signatures without trapdoors. In: Pointcheval, D., Johansson, T. (eds.) EUROCRYPT 2012. LNCS, vol. 7237, pp. 738–755. Springer, Heidelberg (2012)
Micciancio, D., Voulgaris, P.: A Deterministic Single Exponential Time Algorithm for Most Lattice Problems based on Voronoi Cell Computations. In: 42nd Annual ACM Symposium on Theory of Computing (STOC), pp. 351–358. ACM, New York (2010)
Micciancio, D., Voulgaris, P.: Faster Exponential Time Algorithms for the Shortest Vector Problem. In: 21st Annual ACM Symposium on Discrete Algorithms (SODA), pp. 1468–1480. ACM, New York (2010)
Mosca, M.: Quantum Algorithms. In: Meyers, R. (ed.) Encyclopedia of Complexity and Systems Science (2009)
Nguyen, P.Q., Vidick, T.: Sieve Algorithms for the Shortest Vector Problem are Practical. J. Math. Crypt. 2(2), 181–207 (2008)
Pohst, M.: On the computation of lattice vectors of minimal length, successive minima and reduced bases with applications. ACM SIGSAM Bulletin 15(1), 37–44 (1981)
van de Pol, J.: Lattice-based cryptography. Master’s thesis. Eindhoven University of Technology (2011)
Pujol, X., Stehlé, D.: Solving the Shortest Lattice Vector Problem in Time 22.465n. Cryptology ePrint Archive, Report 2009/605, pp. 1–7 (2009)
Regev, O.: A Subexponential Time Algorithm for the Dihedral Hidden Subgroup Problem with Polynomial Space. arXiv, Report 0405/151, pp. 1–7 (2004)
Regev, O.: Lattices in Computer Science. Lecture Notes for a Course at the Tel Aviv University (2004)
Regev, O.: Quantum Computation and Lattice Problems. SIAM J. Comput. 33(3), 738–760 (2004)
Regev, O.: On lattices, learning with errors, random linear codes, and cryptography. In: 37th Annual ACM Symposium on Theory of Computing (STOC), pp. 84–93 (2005)
Santha, M.: Quantum Walk Based Search Algorithms. In: Agrawal, M., Du, D.-Z., Duan, Z., Li, A. (eds.) TAMC 2008. LNCS, vol. 4978, pp. 31–46. Springer, Heidelberg (2008)
Schneider, M.: Analysis of Gauss-Sieve for Solving the Shortest Vector Problem in Lattices. In: Katoh, N., Kumar, A. (eds.) WALCOM 2011. LNCS, vol. 6552, pp. 89–97. Springer, Heidelberg (2011)
Schneider, M.: Sieving for Short Vectors in Ideal Lattices. Cryptology ePrint Archive, Report 2011/458, pp. 1–19 (2011)
Schnorr, C.P.: A Hierarchy of Polynomial Time Lattice Basis Reduction Algorithms. Theoretical Computer Science 53(2-3), 201–224 (1987)
Schnorr, C.P., Euchner, M.: Lattice Basis Reduction: Improved Practical Algorithms and Solving Subset Sum Problems. Mathematical Programming 66(2-3), 181–199 (1994)
Schnorr, C.P.: Lattice reduction by random sampling and birthday methods. In: Alt, H., Habib, M. (eds.) STACS 2003. LNCS, vol. 2607, pp. 145–156. Springer, Heidelberg (2003)
Shor, P.W.: Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer. SIAM J. Comput. 26(5), 1484–1509 (1997)
Smith, J.: Mosca. M.: Algorithms for Quantum Computers. In: Handbook of Natural Computing, pp. 1451–1492. Springer (2012)
SVP Challenge, http://latticechallenge.org/svp-challenge/
Wang, X., Liu, M., Tian, C., Bi, J.: Improved Nguyen-Vidick Heuristic Sieve Algorithm for Shortest Vector Problem. In: 6th ACM Symposium on Information, Computer and Communications Security (ASIACCS), pp. 1–9. ACM, New York (2011)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Laarhoven, T., Mosca, M., van de Pol, J. (2013). Solving the Shortest Vector Problem in Lattices Faster Using Quantum Search. In: Gaborit, P. (eds) Post-Quantum Cryptography. PQCrypto 2013. Lecture Notes in Computer Science, vol 7932. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-38616-9_6
Download citation
DOI: https://doi.org/10.1007/978-3-642-38616-9_6
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-38615-2
Online ISBN: 978-3-642-38616-9
eBook Packages: Computer ScienceComputer Science (R0)