×

zbMATH — the first resource for mathematics

Algorithms for the shortest and closest lattice vector problems. (English) Zbl 1272.68477
Chee, Yeow Meng (ed.) et al., Coding and cryptology. Third international workshop, IWCC 2011, Qingdao, China, May 30 – June 3, 2011. Proceedings. Berlin: Springer (ISBN 978-3-642-20900-0/pbk). Lecture Notes in Computer Science 6639, 159-190 (2011).
Summary: We present the state of the art solvers of the Shortest and Closest Lattice Vector Problems in the Euclidean norm. We recall the three main families of algorithms for these problems, namely the algorithm by D. Micciancio and P. Voulgaris based on the Voronoi cell [SIAM J. Comput. 42, No. 3, 1364–1391 (2013; Zbl 1275.68079)], the Monte-Carlo algorithms derived from the Ajtai, Kumar and Sivakumar algorithm [M. Ajtai, R. Kumar and D. Sivakumar, “A sieve algorithm for the shortest lattice vector problem”, in: Proceedings of the thirty-third annual ACM symposium on theory of computing, STOC ’01. New York: ACM. 601–610 (2001)] and the enumeration algorithms originally elaborated by R. Kannan [“Improved algorithms for integer programming and related lattice problems”, in: Proceedings of the fifteenth annual ACM symposium on theory of computing, STOC ’83. New York: ACM. 99–108 (1983)] and U. Fincke and M. Pohst [Lect. Notes Comput. Sci. 162, 194–202 (1983; Zbl 0541.12001)]. We concentrate on the theoretical worst-case complexity bounds, but also consider some practical facets of these algorithms.
For the entire collection see [Zbl 1214.94002].

MSC:
68W30 Symbolic computation and algebraic computation
11Y16 Number-theoretic algorithms; complexity
05B20 Combinatorial aspects of matrices (incidence, Hadamard, etc.)
Software:
fpLLL; Magma; NTL; NTRU
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Agrell, E., Eriksson, T., Vardy, A., Zeger, K.: Closest point search in lattices. IEEE Transactions on Information Theory 48(8), 2201–2214 (2002) · Zbl 1062.94035 · doi:10.1109/TIT.2002.800499
[2] Ajtai, M.: Generating hard instances of lattice problems (extended abstract). In: Proc. of STOC, pp. 99–108. ACM, New York (1996) · Zbl 0921.11071
[3] Ajtai, M.: The worst-case behavior of Schnorr’s algorithm approximating the shortest nonzero vector in a lattice. In: Proc. of STOC, pp. 396–406. ACM, New York (2003) · Zbl 1192.68336
[4] Ajtai, M., Dwork, C.: A public-key cryptosystem with worst-case/average-case equivalence. In: Proc. of STOC, pp. 284–293. ACM, New York (1997) · Zbl 0962.68055
[5] Ajtai, M., Kumar, R., Sivakumar, D.: A sieve algorithm for the shortest lattice vector problem. In: Proc. of STOC, pp. 601–610. ACM, New York (2001) · Zbl 1323.68561
[6] Ajtai, M., Kumar, R., Sivakumar, D.: Sampling short lattice vectors and the closest lattice vector problem. In: Proc. of CCC, pp. 53–57 (2002) · doi:10.1109/CCC.2002.1004339
[7] Babai, L.: On Lovász lattice reduction and the nearest lattice point problem. Combinatorica 6, 1–13 (1986) · Zbl 0593.68030 · doi:10.1007/BF02579403
[8] Banaszczyk, W.: New bounds in some transference theorems in the geometry of numbers. Math. Ann. 296, 625–635 (1993) · Zbl 0786.11035 · doi:10.1007/BF01445125
[9] Blömer, J., Naewe, S.: Sampling methods for shortest vectors, closest vectors and successive minima. Theor. Comput. Science 410(18), 1648–1665 (2009) · Zbl 1220.68057 · doi:10.1016/j.tcs.2008.12.045
[10] Bosma, W., Cannon, J., Playoust, C.: The Magma algebra system. I. The user language. Journal of Symbolic Computation 24(3-4), 235–265 (1997), http://magma.maths.usyd.edu.au/magma/ · Zbl 0898.68039 · doi:10.1006/jsco.1996.0125
[11] Buchmann, J.: Reducing Lattice Bases by Means of Approximations. In: Huang, M.-D.A., Adleman, L.M. (eds.) ANTS 1994. LNCS, vol. 877, pp. 160–168. Springer, Heidelberg (1994) · Zbl 0834.11065 · doi:10.1007/3-540-58691-1_54
[12] Cadé, D., Pujol, X., Stehlé, D.: fplll-3.1, a floating-point LLL implementation, http://perso.ens-lyon.fr/damien.stehle
[13] Cassels, J.W.S.: An Introduction to the Geometry of Numbers, 2nd edn. Springer, Heidelberg (1971) · Zbl 0209.34401
[14] Conway, J.H., Sloane, N.J.A.: Sphere Packings, Lattices and Groups, 3rd edn. Springer, Heidelberg (1998) · Zbl 0917.11027
[15] Dadush, D., Peikert, C., Vempala, S.: Enumerative algorithms for the shortest and closest lattice vector problems in any norm via M-ellipsoid coverings (submitted 2011) · Zbl 1292.68091
[16] Detrey, J., Hanrot, G., Pujol, X., Stehlé, D.: Accelerating lattice reduction with fPGAs. In: Abdalla, M., Barreto, P.S.L.M. (eds.) LATINCRYPT 2010. LNCS, vol. 6212, pp. 124–143. Springer, Heidelberg (2010) · Zbl 1285.94056 · doi:10.1007/978-3-642-14712-8_8
[17] Eisenbrand, F.: Integer Programming and Algorithmic Geometry of Numbers. In: 50 Years of Integer Programming 1958-2008, From the Early Years to the State-of-the-Art. Springer, Heidelberg (2009)
[18] Eisenbrand, F., Hähnle, N., Niemeier, M.: Covering cubes and the closest vector problem. To appear in the Proceedings of SoCG (2011) · Zbl 1283.68358 · doi:10.1145/1998196.1998264
[19] van Emde Boas, P.: Another NP-complete partition problem and the complexity of computing short vectors in a lattice. Technical report 81-04, Mathematisch Instituut, Universiteit van Amsterdam (1981)
[20] Fincke, U., Pohst, M.: A procedure for determining algebraic integers of given norm. In: van Hulzen, J.A. (ed.) ISSAC 1983 and EUROCAL 1983. LNCS, vol. 162, pp. 194–202. Springer, Heidelberg (1983) · Zbl 0541.12001 · doi:10.1007/3-540-12868-9_103
[21] Fincke, U., Pohst, M.: Improved methods for calculating vectors of short length in a lattice, including a complexity analysis. Math. Comp. 44(170), 463–471 (1985) · Zbl 0556.10022 · doi:10.1090/S0025-5718-1985-0777278-8
[22] Gama, N., Howgrave-Graham, N., Koy, H., Nguyên, P.Q.: Rankin’s constant and blockwise lattice reduction. In: Dwork, C. (ed.) CRYPTO 2006. LNCS, vol. 4117, pp. 112–130. Springer, Heidelberg (2006) · Zbl 1129.11058 · doi:10.1007/11818175_7
[23] Gama, N., Nguyen, P.Q.: Finding short lattice vectors within Mordell’s inequality. In: Proc. of STOC, pp. 207–216. ACM, New York (2008) · Zbl 1230.11153
[24] Gama, N., Nguyen, P.Q.: Predicting lattice reduction. In: Smart, N.P. (ed.) EUROCRYPT 2008. LNCS, vol. 4965, pp. 31–51. Springer, Heidelberg (2008) · Zbl 1149.94314 · doi:10.1007/978-3-540-78967-3_3
[25] 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) · Zbl 1280.94056 · doi:10.1007/978-3-642-13190-5_13
[26] Gama, N., Schneider, M.: The SVP challenge homepage, http://www.latticechallenge.org/svp-challenge/
[27] Goldreich, O., Goldwasser, S., Halevi, S.: Public-key cryptosystems from lattice reduction problems. In: Kaliski Jr., B.S. (ed.) CRYPTO 1997. LNCS, vol. 1294, pp. 112–131. Springer, Heidelberg (1997) · Zbl 0889.94011 · doi:10.1007/BFb0052231
[28] Goldreich, O., Micciancio, D., Safra, S., Seifert, J.-P.: Approximating shortest lattice vectors is not harder than approximating closest lattice vectors. Inf. Process. Lett. 71(2), 55–61 (1999) · Zbl 0999.68085 · doi:10.1016/S0020-0190(99)00083-6
[29] Goldstein, D., Mayer, A.: On the equidistribution of Hecke points. Forum Mathematicum 15, 165–189 (2003) · Zbl 1048.11057 · doi:10.1515/form.2003.009
[30] Gruber, M., Lekkerkerker, C.G.: Geometry of Numbers. North-Holland, Amsterdam (1987) · Zbl 0611.10017
[31] Guruswami, V., Micciancio, D., Regev, O.: The complexity of the covering radius problem. Computational Complexity 14(2), 90–121 (2005) · Zbl 1085.68063 · doi:10.1007/s00037-005-0193-y
[32] Hanrot, G., Stehlé, D.: Improved analysis of kannan’s shortest lattice vector algorithm (extended abstract). In: Menezes, A. (ed.) CRYPTO 2007. LNCS, vol. 4622, pp. 170–186. Springer, Heidelberg (2007) · Zbl 1215.94050 · doi:10.1007/978-3-540-74143-5_10
[33] Hanrot, G., Stehlé, D.: Worst-case Hermite-Korkine-Zolotarev reduced lattice bases. CoRR, abs/0801.3331 (2008)
[34] Hassibi, A., Boyd, S.: Integer parameter estimation in linear models with applications to GPS. IEEE Transactions on Signal Process 46(11), 2938–2952 (1998) · doi:10.1109/78.726808
[35] Haviv, I., Regev, O.: Tensor-based hardness of the shortest vector problem to within almost polynomial factors. In: Proc. of STOC, pp. 469–477. ACM, New York (2007) · Zbl 1232.68066
[36] Helfrich, B.: Algorithms to construct Minkowski reduced and Hermite reduced lattice bases. Theor. Comput. Science 41, 125–139 (1985) · Zbl 0601.68034 · doi:10.1016/0304-3975(85)90067-2
[37] Hermans, J., Schneider, M., Buchmann, J., Vercauteren, F., Preneel, B.: Parallel shortest lattice vector enumeration on graphics cards. In: Bernstein, D.J., Lange, T. (eds.) AFRICACRYPT 2010. LNCS, vol. 6055, pp. 52–68. Springer, Heidelberg (2010) · Zbl 1284.68638 · doi:10.1007/978-3-642-12678-9_4
[38] Hermite, C.: OEuvres. Gauthiers-Villars (1905)
[39] 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) · Zbl 1067.94538 · doi:10.1007/BFb0054868
[40] Horváth, Á.G.: On the Dirichlet-Voronoi cells of the unimodular lattices. Geometricæ Dedicata 63, 183–191 (1996) · Zbl 0864.11034
[41] Kabatyansky, G.A., Levenshtein, V.I.: Bounds for packings on a sphere and in space. Probl. Peredachi Inf. 14(1), 3–25 (1978)
[42] Kannan, R.: Improved algorithms for integer programming and related lattice problems. In: Proc. of STOC, pp. 99–108. ACM, New York (1983)
[43] Kannan, R.: Minkowski’s convex body theorem and integer programming. Math. Oper. Res. 12(3), 415–440 (1987) · Zbl 0639.90069 · doi:10.1287/moor.12.3.415
[44] Khot, S.: Inapproximability results for computational problems on lattices. Chapter of [64] · Zbl 1237.68101
[45] Klein, P.N.: Finding the closest lattice vector when it’s unusually close. In: Proc. of SODA, pp. 937–941. ACM, New York (2000) · Zbl 0953.65043
[46] Korkine, A., Zolotarev, G.: Sur les formes quadratiques. Math. Ann. 6, 336–389 (1873) · JFM 05.0109.01 · doi:10.1007/BF01442795
[47] Lenstra, A.K., Lenstra Jr., H.W., Lovász, L.: Factoring polynomials with rational coefficients. Math. Ann. 261, 515–534 (1982) · Zbl 0488.12001 · doi:10.1007/BF01457454
[48] Lenstra Jr., H.: Lattices. In: Buhler, J.P., Stevenhagen, P. (eds.) Algorithmic Number Theory, pp. 127–181. MSRI Publications, Cambridge University Press (2008)
[49] Lindner, R., Rückert, M.: The lattice challenge homepage, http://www.latticechallenge.org/
[50] Liu, Y.-K., Lyubashevsky, V., Micciancio, D.: On bounded distance decoding for general lattices. In: Díaz, J., Jansen, K., Rolim, J.D.P., Zwick, U. (eds.) APPROX 2006 and RANDOM 2006. LNCS, vol. 4110, pp. 450–461. Springer, Heidelberg (2006) · Zbl 1155.94409 · doi:10.1007/11830924_41
[51] Lyubashevsky, V., Micciancio, D.: On bounded distance decoding, unique shortest vectors, and the minimum distance problem. In: Halevi, S. (ed.) CRYPTO 2009. LNCS, vol. 5677, pp. 577–594. Springer, Heidelberg (2009) · Zbl 1252.94084 · doi:10.1007/978-3-642-03356-8_34
[52] Martinet, J.: Perfect Lattices in Euclidean Spaces. Springer, Heidelberg (2002) · Zbl 1017.11031
[53] Micciancio, D.: Efficient reductions among lattice problems. In: Proc. of SODA, pp. 84–93. SIAM, Philadelphia (2008) · Zbl 1192.68913
[54] Micciancio, D., Goldwasser, S.: Complexity of lattice problems : a cryptographic perspective. Kluwer Academic Press, Dordrecht (2002) · Zbl 1140.94010 · doi:10.1007/978-1-4615-0897-7
[55] Micciancio, D., Regev, O.: Lattice-based cryptography. In: Bernstein, D.J., Buchmann, J., Dahmen, E. (eds.) Post-Quantum Cryptography, pp. 147–191. Springer, Heidelberg (2009) · Zbl 1161.81324 · doi:10.1007/978-3-540-88702-7_5
[56] Micciancio, D., Voulgaris, P.: A deterministic single exponential time algorithm for most lattice problems based on Voronoi cell computations, Draft of the full version of [57] (December 8, 2010), http://cseweb.ucsd.edu/ pvoulgar/pub.html · Zbl 1293.68172
[57] Micciancio, D., Voulgaris, P.: A deterministic single exponential time algorithm for most lattice problems based on Voronoi cell computations. In: Proc. of STOC, pp. 351–358. ACM, New York (2010) · Zbl 1293.68172
[58] Micciancio, D., Voulgaris, P.: Faster exponential time algorithms for the shortest vector problem. In: Proc. of SODA, ACM, New York (2010) · Zbl 1288.94076
[59] Minkowski, H.: Geometrie der Zahlen. Teubner-Verlag, Stuttgart (1896) · Zbl 0050.04807
[60] Mow, W.H.: Maximum likelihood sequence estimation from the lattice viewpoint. IEEE Transactions on Information Theory 40, 1591–1600 (1994) · Zbl 0811.94015 · doi:10.1109/18.333872
[61] Mow, W.H.: Universal lattice decoding: Principle and recent advances. Wireless Communications and Mobile Computing, Special Issue on Coding and Its Applications in Wireless CDMA Systems 3(5), 553–569 (2003) · Zbl 05460782 · doi:10.1002/wcm.140
[62] P. Q. Nguyen. Hermite’s constant and lattice algorithms. Chapter of [64]. · Zbl 1230.11155
[63] Nguyên, P.Q., Stehlé, D.: LLL on the average. In: Hess, F., Pauli, S., Pohst, M. (eds.) ANTS 2006. LNCS, vol. 4076, pp. 238–256. Springer, Heidelberg (2006) · Zbl 1143.11357 · doi:10.1007/11792086_18
[64] Nguyen, P.Q., Vallée, B. (eds.): The LLL Algorithm: Survey and Applications. Information Security and Cryptography. Springer, Heidelberg (2009)
[65] Nguyen, P.Q., Vidick, T.: Sieve algorithms for the shortest vector problem are practical. Journal of Mathematical Cryptology 2(2) (2008) · Zbl 1193.11117 · doi:10.1515/JMC.2008.009
[66] Odlyzko, A.M.: The rise and fall of knapsack cryptosystems. In: Cryptology and Computational Number Theory. Proc. of Symposia in Applied Mathematics, vol. 42, pp. 75–88. A.M.S, Providence (1990)
[67] Pujol, X., Stehlé, D.: Rigorous and efficient short lattice vectors enumeration. In: Pieprzyk, J. (ed.) ASIACRYPT 2008. LNCS, vol. 5350, pp. 390–405. Springer, Heidelberg (2008) · Zbl 1206.94086 · doi:10.1007/978-3-540-89255-7_24
[68] Pujol, X., Stehlé, D.: Solving the shortest lattice vector problem in time 22.465n. Cryptology ePrint Archive (2009), http://eprint.iacr.org/2009/605
[69] Regev, O.: Lecture notes of lattices in computer science, taught at the Computer Science Tel Aviv University, http://www.cs.tau.il/ odedr
[70] O. Regev. On the complexity of lattice problems with polynomial approximation factors. Chapter of [64].
[71] Regev, O.: On lattices, learning with errors, random linear codes, and cryptography. In: Proc. of STOC, pp. 84–93. ACM, New York (2005) · Zbl 1192.94106
[72] Regev, O.: The learning with errors problem, Invited survey in CCC 2010 (2010), http://www.cs.tau.ac.il/ odedr/
[73] C. P. Schnorr. Progress on LLL and lattice reduction. Chapter of [64]. · Zbl 1215.11122
[74] Schnorr, C.P.: A hierarchy of polynomial lattice basis reduction algorithms. Theor. Comput. Science 53, 201–224 (1987) · Zbl 0642.10030 · doi:10.1016/0304-3975(87)90064-8
[75] Schnorr, C.P., Euchner, M.: Lattice basis reduction : improved practical algorithms and solving subset sum problems. Mathematics of Programming 66, 181–199 (1994) · Zbl 0829.90099 · doi:10.1007/BF01581144
[76] Schnorr, C.-P., Hörner, H.H.: Attacking the chor-rivest cryptosystem by improved lattice reduction. In: Guillou, L.C., Quisquater, J.-J. (eds.) EUROCRYPT 1995. LNCS, vol. 921, pp. 1–12. Springer, Heidelberg (1995) · Zbl 0973.94514 · doi:10.1007/3-540-49264-X_1
[77] Shoup, V.: NTL, Number Theory C++ Library, http://www.shoup.net/ntl/
[78] Siegel, C.L.: Lectures on the Geometry of Numbers. Springer, Heidelberg (1989) · Zbl 0691.10021 · doi:10.1007/978-3-662-08287-4
[79] Sommer, N., Feder, M., Shalvi, O.: Finding the closest lattice point by iterative slicing. SIAM J. Discrete Math. 23(2), 715–731 (2009) · Zbl 1193.94010 · doi:10.1137/060676362
[80] Stehlé, D., Watkins, M.: On the extremality of an 80-dimensional lattice. In: Hanrot, G., Morain, F., Thomé, E. (eds.) ANTS-IX. LNCS, vol. 6197, pp. 340–356. Springer, Heidelberg (2010) · Zbl 1260.11048 · doi:10.1007/978-3-642-14518-6_27
[81] Voronoi, G.: Nouvelles applications des paramètres continus à la théorie des formes quadratiques. Journal für die reine und angewandte Mathematik 134, 198–287 (1908)
[82] Voulgaris, P.: Personal communication
[83] Wang, X., Liu, M., Tian, C., Bi, J.: Improved Nguyen-Vidick heuristic sieve algorithm for shortest vector problem. Cryptology ePrint Archive (2010), http://eprint.iacr.org/2010/647
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.