Inapproximability of the Shortest Vector Problem: Toward a Deterministic Reduction

by Daniele Micciancio

Theory of Computing, Volume 8(22), pp. 487-512, 2012

Bibliography with links to cited articles

[1]   Miklós Ajtai: The shortest vector problem in L2 is NP-hard for randomized reductions. In Proc. 30th STOC, pp. 10–19. ACM Press, 1998. ECCC. [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]   Sanjeev Arora, László Babai, Jacques Stern, and Elizabeth 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]

[4]   Per Austrin and Subhash Khot: A simple deterministic reduction for the gap minimum distance of code problem. In Proc. 38th Internat. Colloq. on Automata, Languages and Programming (ICALP’11), pp. 474–485. Springer, 2011. [doi:10.1007/978-3-642-22006-7_40]

[5]   Mihir Bellare, Shafi Goldwasser, Carsten Lund, and Alex Russell: Efficient probabilistically checkable proofs and applications to approximations. In Proc. 25th STOC, pp. 294–304. ACM Press, 1993. [doi:10.1145/167088.167174]

[6]    Elwyn R. Berlekamp, Robert J. McEliece, and Henk C. A. van Tilborg: On the inherent intractability of certain coding problems. IEEE Trans. Inform. Theory, 24(3):384–386, 1978. [doi:10.1109/TIT.1978.1055873]

[7]   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]

[8]   Qi Cheng and Daqing Wan: A deterministic reduction for the gap minimum distance problem. In Proc. 41st STOC, pp. 33–38. ACM Press, 2009. [doi:10.1145/1536414.1536421]

[9]   John H. Conway and Neil J. A. Sloane: Sphere Packings, Lattices and Groups. Springer, 3rd edition, 1998.

[10]   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]

[11]   Ilya Dumer, Daniele Micciancio, and Madhu Sudan: Hardness of approximating the minimum distance of a linear code. IEEE Trans. Inform. Theory, 49(1):22–37, 2003. Preliminary version in FOCS’99. [doi:10.1109/TIT.2002.806118]

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

[13]   David S. Johnson: A catalog of complexity classes. In Handbook of Theoretical Computer Science, volume A (Algorithms and Complexity), chapter 2, pp. 67–161. Elsevier, 1990.

[14]   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]

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

[16]   Yoshiyuki Kitaoka: Tensor products of positive definite quadratic forms. Proc. Japan Acad., 52(9):498–500, 1976. [doi:10.3792/pja/1195518215]

[17]   Jeffery C. Lagarias and Andrew M. Odlyzko: Solving low-density subset sum problems. J. ACM, 32(1):229–246, 1985. Preliminary version in FOCS’83. [doi:10.1145/2455.2461]

[18]   Vadim Lyubashevsky and Daniele Micciancio: On bounded distance decoding, unique shortest vectors, and the minimum distance problem. In 29th Ann. Internat. Cryptology Conf. (CRYPTO’09), pp. 577–594. Springer, 2009. [doi:10.1007/978-3-642-03356-8_34]

[19]   Daniele Micciancio: The hardness of the closest vector problem with preprocessing. IEEE Trans. Inform. Theory, 47(3):1212–1215, 2001. [doi:10.1109/18.915688]

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

[21]   Daniele Micciancio and Shafi Goldwasser: Complexity of Lattice Problems: a cryptographic perspective. Volume 671 of The Kluwer International Series in Engineering and Computer Science. Kluwer Academic Publishers, 2002.

[22]   Daniele Micciancio and Panagiotis Voulgaris: A deterministic single exponential time algorithm for most lattice problems based on Voronoi cell computations. In Proc. 42nd STOC, pp. 351–358. ACM Press, 2010. ECCC. [doi:10.1145/1806689.1806739]

[23]   Daniele Micciancio and Panagiotis Voulgaris: Faster exponential time algorithms for the shortest vector problem. In Proc. 21st Ann. ACM-SIAM Symp. on Discrete Algorithms (SODA’10), pp. 1468–1480. ACM Press, 2010. ECCC. [ACM:1873720]

[24]   Phong Q. Nguyen and Thomas Vidick: Sieve algorithms for the shortest vector problem are practical. J. Math. Cryptology, 2(2):181–207, 2008. [doi:10.1515/JMC.2008.009]

[25]   Vera S. Pless and William Cary Huffman, editors. Handbook of Coding Theory. North-Holland, 1998.

[26]   Xavier Pujol and Damien Stehlé: Solving the shortest lattice vector problem in time 22.465n. Report 2009/605, IACR ePrint archive, 2009. IACR.

[27]   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]

[28]   Norbert Sauer: On the density of families of sets. J. Combin. Theory Ser. A, 13(1):145–147, 1972. [doi:10.1016/0097-3165(72)90019-2]

[29]   Saharon Shelah: A combinatorial problem; stability and order for models and theories in infinitary languages. Pacific J. Math., 41(1):247–261, 1972. Project Euclid.

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

[31]   Vladimir N. Vapnik and Alexey Ya. Chervonenkis: On the uniform covergence of relative frequencies of events to their probabilities. Theory of Probability and Appl., XVI(2):264–280, 1971. Translation from the Russian.

[32]   Alexander Vardy: The intractability of computing the minimum distance of a code. IEEE Trans. Inform. Theory, 43(6):1757–1766, 1997. [doi:10.1109/18.641542]

[33]   Xiaoyun Wang, Mingjie Liu, Chengliang Tian, and Jingguo Bi: Improved Nguyen-Vidick heuristic sieve algorithm for shortest vector problem. In Proc. 6th ACM Symp. on Information, Computer and Communications Security (ASIACCS’11), pp. 1–9. ACM Press, 2011. [doi:10.1145/1966913.1966915]