Lattice Sparsification and the Approximate Closest Vector Problem

by Daniel Dadush and Gábor Kun

Theory of Computing, Volume 12(2), pp. 1-34, 2016

Bibliography with links to cited articles

[1]   Miklós Ajtai: The shortest vector problem in L2 is NP-hard for randomized reductions (extended abstract). In Proc. 30th STOC, pp. 10–19. ACM Press, 1998. [doi:10.1145/276698.276705]

[2]   Miklós Ajtai, Ravi Kumar, and D. Sivakumar: A sieve algorithm for the shortest lattice vector problem. In Proc. 33rd STOC, pp. 601–610. ACM Press, 2001. [doi:10.1145/380752.380857]

[3]   Miklós Ajtai, Ravi Kumar, and D. Sivakumar: Sampling short lattice vectors and the closest lattice vector problem. In Proc. 17th IEEE Conf. on Computational Complexity (CCC’02), pp. 53–57. IEEE Comp. Soc. Press, 2002. [doi:10.1109/CCC.2002.1004339]

[4]   Sanjeev Arora, László Babai, Jacques Stern, and Z. Sweedyk: The hardness of approximate optima in lattices, codes, and systems of linear equations. J. Comput. System Sci., 54(2):317–331, 1997. Preliminary version in FOCS’93. [doi:10.1006/jcss.1997.1472]

[5]   Vikraman Arvind and Pushkar S. Joglekar: Some sieving algorithms for lattice problems. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS’08), volume 2 of LIPIcs, pp. 25–36. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2008. [doi:10.4230/LIPIcs.FSTTCS.2008.1738]

[6]   László Babai: On Lovász’ lattice reduction and the nearest lattice point problem. Combinatorica, 6(1):1–13, 1986. Preliminary version in STACS’85. [doi:10.1007/BF02579403]

[7]   Johannes Blömer and Stefanie Naewe: Sampling methods for shortest vectors, closest vectors and successive minima. Theoret. Comput. Sci., 410(18):1648–1665, 2009. Preliminary version in ICALP’07. [doi:10.1016/j.tcs.2008.12.045]

[8]   Nicolas Brisebarre and Sylvain Chevillard: Efficient polynomial L-approximations. In 18th IEEE Symposium on Computer Arithmetic (ARITH’07), pp. 169–176. IEEE Comp. Soc. Press, 2007. [doi:10.1109/ARITH.2007.17]

[9]   Jin-Yi Cai and Ajay Nerurkar: Approximating the SVP to within a factor (1+1/dimϵ) is NP-hard under randomized reductions. J. Comput. System Sci., 59(2):221–239, 1999. Preliminary version in CCC’98. [doi:10.1006/jcss.1999.1649]

[10]   Daniel Dadush: Integer Programming, Lattice Algorithms, and Deterministic Volume Estimation. Ph. D. thesis, Georgia Institute of Technology, 2012. Available at author’s webpage.

[11]   Daniel Dadush: A randomized sieving algorithm for approximate integer programming. Algorithmica, 70(2):208–244, 2014. Preliminary version in LATIN’12. [doi:10.1007/s00453-013-9834-8]

[12]   Daniel Dadush, Chris Peikert, and Santosh Vempala: Enumerative lattice algorithms in any norm via M-ellipsoid coverings. In Proc. 52rd FOCS, pp. 580–589. IEEE Comp. Soc. Press, 2011. [doi:10.1109/FOCS.2011.31, arXiv:abs/1011.5666]

[13]   Daniel Dadush and Santosh S. Vempala: Near-optimal deterministic algorithms for volume computation via M-ellipsoids. Proceedings of the National Academy of Sciences, 2013. [doi:10.1073/pnas.1203863110]

[14]   Irit Dinur: Approximating SVP to within almost-polynomial factors is NP-hard. Theoret. Comput. Sci., 285(1):55–71, 2002. Preliminary versions in CIAC’00 and ECCC. [doi:10.1016/S0304-3975(01)00290-0]

[15]   Irit Dinur, Guy Kindler, Ran Raz, and Shmuel Safra: Approximating CVP to within almost-polynomial factors is NP-hard. Combinatorica, 23(2):205–243, 2003. Preliminary version in FOCS’98. [doi:10.1007/s00493-003-0019-y]

[16]   Friedrich Eisenbrand, Nicolai Hähnle, and Martin Niemeier: Covering cubes and the closest vector problem. In Proc. 27th Symp. on Computational Geometry (SoCG’11), pp. 417–423. ACM Press, 2011. [doi:10.1145/1998196.1998264, arXiv:1012.2289]

[17]   Peter van Emde Boas: Another NP-complete partition problem and the complexity of computing short vectors in a lattice. Technical Report 81-04, University of Amsterdam, 1981. Available at author’s webpage.

[18]   András Frank and Éva Tardos: An application of simultaneous diophantine approximation in combinatorial optimization. Combinatorica, 7(1):49–65, 1987. [doi:10.1007/BF02579200]

[19]   Oded Goldreich, Daniele Micciancio, Shmuel Safra, and Jean-Pierre Seifert: Approximating shortest lattice vectors is not harder than approximating closest lattice vectors. Inform. Process. Lett., 71(2):55–61, 1999. [doi:10.1016/S0020-0190(99)00083-6]

[20]   Guillaume Hanrot, Xavier Pujol, and Damien Stehlé: Algorithms for the shortest and closest lattice vector problems. In IWCC 2011, volume 6639 of LNCS, pp. 159–190. Springer, 2011. [doi:10.1007/978-3-642-20901-7_10]

[21]   Guillaume Hanrot and Damien Stehlé: Improved analysis of Kannan’s Shortest Lattice Vector algorithm. In Advances in Cryptology (CRYPTO) 2007, 27th Internat. Cryptology Conf., volume 4622 of LNCS, pp. 170–186. Springer, 2007. [doi:10.1007/978-3-540-74143-5_10]

[22]   Ishay Haviv and Oded Regev: Tensor-based hardness of the shortest vector problem to within almost polynomial factors. Theory of Computing, 8(1):513–531, 2012. Preliminary version in STOC’07. [doi:10.4086/toc.2012.v008a023]

[23]   Bettina Helfrich: Algorithms to construct Minkowski reduced and Hermite reduced lattice bases. Theoret. Comput. Sci., 41:125–139, 1985. [doi:10.1016/0304-3975(85)90067-2]

[24]   Robert Hildebrand and Matthias Köppe: A new Lenstra-type algorithm for quasiconvex polynomial integer minimization with complexity 2O(n log n). Discrete Optimization, 10(1):69–84, 2013. [doi:10.1016/j.disopt.2012.11.003, arXiv:1006.4661]

[25]   Antoine Joux and Jacques Stern: Lattice reduction: A toolbox for the cryptanalyst. J. Cryptology, 11(3):161–185, 1998. [doi:10.1007/s001459900042]

[26]   Michael Kaib and Harald Ritter: Block reduction for arbitrary norms. Manuscript, 1995. Available at the Goethe-Universität webpage.

[27]   Ravi Kannan: Minkowski’s convex body theorem and integer programming. Math. Oper. Res., 12(3):415–440, 1987. [doi:10.1287/moor.12.3.415]

[28]   Ravi Kannan: Lattice translates of a polytope and the Frobenius problem. Combinatorica, 12(2):161–177, 1992. Preliminary version in FSTTCS’89. [doi:10.1007/BF01204720]

[29]   Subhash Khot: Hardness of approximating the shortest vector problem in lattices. J. ACM, 52(5):789–808, 2005. Preliminary version in FOCS’04. [doi:10.1145/1089023.1089027]

[30]   Subhash Khot: Hardness of approximating the shortest vector problem in high Lp norms. J. Comput. System Sci., 72(2):206–219, 2006. Preliminary version in FOCS’03. [doi:10.1016/j.jcss.2005.07.002]

[31]   Arjen K. Lenstra, Hendrik W. Lenstra, Jr., and László Lovász: Factoring polynomials with rational coefficients. Mathematische Annalen, 261(4):515–534, 1982. [doi:10.1007/BF01457454]

[32]   Hendrik W. Lenstra: Integer programming with a fixed number of variables. Math. Oper. Res., 8(4):538–548, 1983. [doi:10.1287/moor.8.4.538]

[33]   László Lovász and Herbert E. Scarf: The generalized basis reduction algorithm. Math. Oper. Res., 17(3):751–764, 1992. [doi:10.1287/moor.17.3.751]

[34]   Daniele Micciancio: The shortest vector in a lattice is hard to approximate to within some constant. SIAM J. Comput., 30(6):2008–2035, 2000. Preliminary version in FOCS’98. [doi:10.1137/S0097539700373039]

[35]   Daniele Micciancio: Inapproximability of the shortest vector problem: Toward a deterministic reduction. Theory of Computing, 8(22):487–512, 2012. Preliminary version in ECCC. [doi:10.4086/toc.2012.v008a022]

[36]   Daniele Micciancio and Shafi Goldwasser: Complexity of Lattice Problems: a cryptographic perspective. Volume 671 of The Kluwer Internat. Series in Engineering and Comput. Science. Kluwer, 2002. [doi:10.1007/978-1-4615-0897-7]

[37]   Daniele Micciancio and Panagiotis Voulgaris: A deterministic single exponential time algorithm for most lattice problems based on Voronoi cell computations. SIAM J. Comput., 42(3):1364–1391, 2013. Preliminary version in STOC’10. [doi:10.1137/100811970]

[38]   Daniele Micciancio and Michael Walter: Fast lattice point enumeration with minimal overhead. In Proc. 26th Ann. ACM-SIAM Symp. on Discrete Algorithms (SODA’15), pp. 276–294. ACM Press, 2015. [doi:10.1137/1.9781611973730.21]

[39]   Vitali D. Milman and Alain Pajor: Entropy and asymptotic geometry of non-symmetric convex bodies. Advances in Mathematics, 152(2):314–335, 2000. [doi:10.1006/aima.1999.1903]

[40]   Władysław Narkiewicz: The Development of Prime Number Theory, From Euclid to Hardy and Littlewood. Springer, 2000. [doi:10.1007/978-3-662-13157-2]

[41]   Phong Q. Nguyen and Jacques Stern: The two faces of lattices in cryptology. In Cryptography and Lattices (CaLC’01), volume 2146 of LNCS, pp. 146–180. Springer, 2001. [doi:10.1007/3-540-44670-2_12]

[42]   Andrew Michael Odlyzko: The rise and fall of knapsack cryptosystems. In Cryptology and Computational Number Theory, volume 42 of Proceedings of Symposia in Applied Mathematics, pp. 75–88, 1990. Available at author’s webpage.

[43]   Oded Regev and Ricky Rosen: Lattice problems and norm embeddings. In Proc. 38th STOC, pp. 447–456. ACM Press, 2006. [doi:10.1145/1132516.1132581]

[44]   John Barkley Rosser and Lowell Schoenfeld: Approximate formulas for some functions of prime numbers. Illinois J. Math., 6(1):64–94, 1962. Available at Project Euclid.

[45]   Claus-Peter Schnorr: A hierarchy of polynomial time lattice basis reduction algorithms. Theoret. Comput. Sci., 53(2-3):201–224, 1987. [doi:10.1016/0304-3975(87)90064-8]

[46]   Claus-Peter Schnorr: Factoring integers and computing discrete logarithms via diophantine approximation. In Advances in Cryptology (EUROCRYPT’91), volume 547 of LNCS, pp. 281–293. Springer, 1991. [doi:10.1007/3-540-46416-6_24]

[47]   Martin Seysen: Simultaneous reduction of a lattice basis and its reciprocal basis. Combinatorica, 13(3):363–376, 1993. [doi:10.1007/BF01202355]

[48]   Emanuele Viterbo and Joseph Boutros: A universal lattice code decoder for fading channels. IEEE Trans. Inform. Theory, 45(5):1639–1642, 1999. [doi:10.1109/18.771234]