{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,27]],"date-time":"2025-03-27T07:51:07Z","timestamp":1743061867916,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":44,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642022944"},{"type":"electronic","value":"9783642022951"}],"license":[{"start":{"date-parts":[[2009,1,1]],"date-time":"2009-01-01T00:00:00Z","timestamp":1230768000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2009,1,1]],"date-time":"2009-01-01T00:00:00Z","timestamp":1230768000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2009]]},"DOI":"10.1007\/978-3-642-02295-1_14","type":"book-chapter","created":{"date-parts":[[2009,11,18]],"date-time":"2009-11-18T18:20:09Z","timestamp":1258568409000},"page":"453-473","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Inapproximability Results for Computational Problems on Lattices"],"prefix":"10.1007","author":[{"given":"Subhash","family":"Khot","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2009,10,7]]},"reference":[{"doi-asserted-by":"crossref","unstructured":"D. Micciancio, S. Goldwasser. Complexity of lattice problems, A cryptographic perspective. Kluwer Academic Publishers, 2002","key":"14_CR1_14","DOI":"10.1007\/978-1-4615-0897-7"},{"doi-asserted-by":"crossref","unstructured":"R. Kumar, D. Sivakumar. Complexity of SVP \u2013 A reader\u2019s digest. SIGACT News, 32(3), Complexity Theory Column (ed. L. Hemaspaandra), 2001, pp 40\u201352","key":"14_CR2_14","DOI":"10.1145\/500559.500560"},{"unstructured":"O. Regev. On the Complexity of Lattice Problems with polynomial Approximation Factors. In Proc. of the LLL+25 Conference, Caen, France, June 29-July 1, 2007","key":"14_CR3_14"},{"doi-asserted-by":"crossref","unstructured":"C.F. Gauss. Disquisitiones arithmeticae. (leipzig 1801), art. 171. Yale University. Press, 1966. English translation by A.A. Clarke","key":"14_CR4_14","DOI":"10.5479\/sil.324926.39088000932822"},{"key":"14_CR5_14","volume-title":"Geometrie der zahlen","author":"H Minkowski","year":"1910","unstructured":"H. Minkowski. Geometrie der zahlen. Leizpig, Tuebner, 1910"},{"key":"14_CR6_14","first-page":"513","volume":"261","author":"AK Lenstra","year":"1982","unstructured":"A.K. Lenstra, H.W. Lenstra, L. Lov\u00e1sz. Factoring polynomials with rational coefficients. Mathematische Ann., 261, 1982, pp 513\u2013534","journal-title":"Mathematische Ann."},{"issue":"1","key":"14_CR7_14","doi-asserted-by":"publisher","first-page":"229","DOI":"10.1145\/2455.2461","volume":"32","author":"JC Lagarias","year":"1985","unstructured":"J.C. Lagarias, A.M. Odlyzko. Solving low-density subset sum problems. Journal of the ACM, 32(1), 1985, pp 229\u2013246","journal-title":"Journal of the ACM"},{"issue":"2","key":"14_CR8_14","doi-asserted-by":"publisher","first-page":"179","DOI":"10.1016\/0022-0000(85)90013-3","volume":"30","author":"S Landau","year":"1985","unstructured":"S. Landau, G.L. Miller. Solvability of radicals is in polynomial time. Journal of Computer and Systems Sciences, 30(2), 1985, pp 179\u2013208","journal-title":"Journal of Computer and Systems Sciences"},{"unstructured":"H.W. Lenstra. Integer programming with a fixed number of variables. Tech. Report 81\u201303, Univ. of Amsterdam, Amstredam, 1981","key":"14_CR9_14"},{"doi-asserted-by":"crossref","unstructured":"R. Kannan. Improved algorithms for integer programming and related lattice problems. In Proc. of the 15th Annual ACM Symposium on Theory of Computing, 1983, pp 193\u2013206","key":"14_CR10_14","DOI":"10.1145\/800061.808749"},{"unstructured":"C.P. Schnorr. A hierarchy of polynomial-time basis reduction algorithms. In Proc. of Conference on Algorithms, P $$\\acute{\\mathrm{e}}$$ ecs (Hungary), 1985, pp 375\u2013386","key":"14_CR11_14"},{"key":"14_CR12_14","doi-asserted-by":"publisher","first-page":"415","DOI":"10.1287\/moor.12.3.415","volume":"12","author":"R Kannan","year":"1987","unstructured":"R. Kannan. Minkowski\u2019s convex body theorem and integer programming. Mathematics of Operations Research, 12:415\u2013440, 1987","journal-title":"Mathematics of Operations Research"},{"doi-asserted-by":"crossref","unstructured":"M. Ajtai, R. Kumar, D. Sivakumar. A sieve algorithm for the shortest lattice vector problem. In Proc. of the 33rd Annual ACM Symposium on the Theory of Computing, 2001, pp 601\u2013610","key":"14_CR13_14","DOI":"10.1145\/380752.380857"},{"unstructured":"P. van Emde Boas. Another NP-complete problem and the complexity of computing short vectors in a lattice. Tech. Report 81-04, Mathematische Instiut, University of Amsterdam, 1981","key":"14_CR14_14"},{"doi-asserted-by":"crossref","unstructured":"M. Ajtai. The shortest vector problem in L 2 is NP-hard for randomized reductions. In Proc. of the 30th Annual ACM Symposium on the Theory of Computing, 1998, pp 10\u201319","key":"14_CR15_14","DOI":"10.1145\/276698.276705"},{"unstructured":"J.Y. Cai, A. Nerurkar. Approximating the SVP to within a factor $$(1 + 1\/{\\mathrm{dim}}^{\\varepsilon })$$ is NP-hard under randomized reductions. In Proc. of the 13th Annual IEEE Conference on Computational Complexity, 1998, pp 151\u2013158","key":"14_CR16_14"},{"unstructured":"D. Micciancio. The shortest vector problem is NP-hard to approximate to within some constant. In Proc. of the 39th IEEE Symposium on Foundations of Computer Science, 1998","key":"14_CR17_14"},{"issue":"5","key":"14_CR18_14","doi-asserted-by":"publisher","first-page":"789","DOI":"10.1145\/1089023.1089027","volume":"52","author":"S Khot","year":"2005","unstructured":"S. Khot. Hardness of approximating the shortest vector problem in lattices. Journal of the ACM, 52(5), 2005, pp 789\u2013808","journal-title":"Journal of the ACM"},{"doi-asserted-by":"crossref","unstructured":"I. Haviv, O. Regev. Tensor-based hardness of the Shortest Vector Problem to within almost polynomial factors. To appear in Proc. of the 39th Annual ACM Symposium on the Theory of Computing, 2007","key":"14_CR19_14","DOI":"10.1145\/1250790.1250859"},{"doi-asserted-by":"crossref","unstructured":"M. Ajtai. Generating hard instances of lattice problems. In Proc. of the 28th Annual ACM Symposium on the Theory of Computing, 1996, pp 99\u2013108","key":"14_CR20_14","DOI":"10.1145\/237814.237838"},{"doi-asserted-by":"crossref","unstructured":"M. Ajtai, C. Dwork. A public-key cryptosystem with worst-case\/average-case equivalence. In Proc. of the 29th Annual ACM Symposium on the Theory of Computing, 1997, pp 284\u2013293","key":"14_CR21_14","DOI":"10.1145\/258533.258604"},{"unstructured":"J.Y. Cai, A. Nerurkar. An improved worst-case to average-case connection for lattice problems. In 38th IEEE Symposium on Foundations of Computer Science, 1997","key":"14_CR22_14"},{"unstructured":"J.Y. Cai. Applications of a new transference theorem to Ajtai\u2019s connection factor. In Proc. of the 14th Annual IEEE Conference on Computational Complexity, 1999","key":"14_CR23_14"},{"doi-asserted-by":"crossref","unstructured":"O. Regev. New lattice based cryptographic constructions. To appear in Proc. of the 35th Annual ACM Symposium on the Theory of Computing, 2003","key":"14_CR24_14","DOI":"10.1145\/780542.780603"},{"doi-asserted-by":"crossref","unstructured":"O. Goldreich, D. Micciancio, S. Safra, J.P. Seifert. Approximating shortest lattice vectors is not harder than approximating closest lattice vectors. Information Processing Letters, 1999","key":"14_CR25_14","DOI":"10.1016\/S0020-0190(99)00083-6"},{"doi-asserted-by":"crossref","unstructured":"S. Arora, L. Babai, J. Stern, E.Z. Sweedyk. The hardness of approximate optima in lattices, codes and systems of linear equations. Journal of Computer and Systems Sciences (54), 1997, pp 317\u2013331","key":"14_CR26_14","DOI":"10.1006\/jcss.1997.1472"},{"unstructured":"I. Dinur, G. Kindler, S. Safra. Approximating CVP to within almost-polynomial factors is NP-hard. In Proc. of the 39th IEEE Symposium on Foundations of Computer Science, 1998","key":"14_CR27_14"},{"issue":"3","key":"14_CR28_14","doi-asserted-by":"crossref","first-page":"1212","DOI":"10.1109\/18.915688","volume":"47","author":"D. Micciancio","year":"2001","unstructured":"D. Micciancio. The hardness of the closest vector problem with preprocessing. IEEE Transactions on Information Theory, vol 47(3), 2001, pp 1212\u20131215","journal-title":"IEEE Transactions on Information Theory"},{"doi-asserted-by":"crossref","unstructured":"U. Feige and D. Micciancio. The inapproximability of lattice and coding problems with preprocessing. Computational Complexity, 2002, pp 44\u201352","key":"14_CR29_14","DOI":"10.1109\/CCC.2002.1004338"},{"issue":"9","key":"14_CR30_14","doi-asserted-by":"publisher","first-page":"2031","DOI":"10.1109\/TIT.2004.833350","volume":"50","author":"O Regev","year":"2004","unstructured":"O. Regev. Improved inapproximability of lattice and coding problems with preprocessing. IEEE Transactions on Information Theory, 50(9), 2004, pp 2031\u20132037","journal-title":"IEEE Transactions on Information Theory"},{"unstructured":"M. Alekhnovich, S. Khot, G. Kindler, N. Vishnoi. Hardness of approximating the closest vector problem with pre-processing. In Proc. of the 46th IEEE Symposium on Foundations of Computer Science, 2005","key":"14_CR31_14"},{"issue":"5","key":"14_CR32_14","doi-asserted-by":"publisher","first-page":"749","DOI":"10.1145\/1089023.1089025","volume":"52","author":"D Aharonov","year":"2005","unstructured":"D. Aharonov, O. Regev. Lattice problems in NP \u2229 coNP. Journal of the ACM, 52(5), 2005, pp 749\u2013765","journal-title":"Journal of the ACM"},{"unstructured":"I. Haviv, O. Regev. Hardness of the covering radius problem on lattices. In Proc. of the 21st Annual IEEE Computational Complexity Conference, 2006","key":"14_CR33_14"},{"doi-asserted-by":"crossref","unstructured":"J. Bl\u00f6mer, J.P. Seifert. On the complexity of compuing short linearly independent vectors and short bases in a lattice. In Proc. of the 31st Annual ACM Symposium on the Theory of Computing, 1999, pp 711\u2013720","key":"14_CR34_14","DOI":"10.1145\/301250.301441"},{"doi-asserted-by":"crossref","unstructured":"O. Regev, R. Rosen. Lattice problems and norm embeddings. In Proc. of the 38th Annual ACM Symposium on the Theory of Computing, 2006","key":"14_CR35_14","DOI":"10.1145\/1132516.1132581"},{"doi-asserted-by":"crossref","unstructured":"I. Dinur. Approximating SVP \u221e to within almost polynomial factors is NP-hard. Proc. of the 4th Italian Conference on Algorithms and Complexity, LNCS, vol 1767, Springer, 2000","key":"14_CR36_14","DOI":"10.1007\/3-540-46521-9_22"},{"key":"14_CR37_14","doi-asserted-by":"publisher","first-page":"625","DOI":"10.1007\/BF01445125","volume":"296","author":"W Banaszczyk","year":"1993","unstructured":"W. Banaszczyk. New bounds in some transference theorems in the geometry of numbers. Mathematische Annalen, vol. 296, 1993, pp 625\u2013635","journal-title":"Mathematische Annalen"},{"doi-asserted-by":"crossref","unstructured":"O. Goldreich, S. Goldwasser. On the limits of non-approximability of lattice problems. In Proc. of the 30th Annual ACM Symposium on the Theory of Computing, 1998, pp 1\u20139","key":"14_CR38_14","DOI":"10.1145\/276698.276704"},{"issue":"2","key":"14_CR39_14","doi-asserted-by":"publisher","first-page":"90","DOI":"10.1007\/s00037-005-0193-y","volume":"14","author":"V Guruswami","year":"2005","unstructured":"V. Guruswami, D. Micciancio, O. Regev. The complexity of the covering radius problem on lattices. Computational Complexity 14(2), 2005, pp 90\u2013121","journal-title":"Computational Complexity"},{"issue":"1","key":"14_CR40_14","doi-asserted-by":"publisher","first-page":"70","DOI":"10.1145\/273865.273901","volume":"45","author":"S Arora","year":"1998","unstructured":"S. Arora and S. Safra. Probabilistic checking of proofs : A new characterization of NP. Journal of the ACM, 45(1), 1998, pp 70\u2013122","journal-title":"Journal of the ACM"},{"issue":"3","key":"14_CR41_14","doi-asserted-by":"publisher","first-page":"501","DOI":"10.1145\/278298.278306","volume":"45","author":"S Arora","year":"1998","unstructured":"S. Arora, C. Lund, R. Motwani, M. Sudan, M. Szegedy. Proof verification and the hardness of approximation problems. Journal of the ACM, 45(3), 1998, pp 501\u2013555","journal-title":"Journal of the ACM"},{"issue":"3","key":"14_CR42_14","doi-asserted-by":"publisher","first-page":"763","DOI":"10.1137\/S0097539795280895","volume":"27","author":"R Raz","year":"1998","unstructured":"R. Raz. A parallel repetition theorem. SIAM Journal of Computing, 27(3), 1998, pp 763\u2013803","journal-title":"SIAM Journal of Computing"},{"key":"14_CR43_14","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-88330-9","volume-title":"Symmetric bilinear forms","author":"J Milnor","year":"1973","unstructured":"J. Milnor, D. Husemoller. Symmetric bilinear forms. Springer, Berlin, 1973"},{"key":"14_CR44_14","doi-asserted-by":"publisher","first-page":"333","DOI":"10.1007\/BF02128669","volume":"10","author":"JC Lagarias","year":"1990","unstructured":"J.C. Lagarias, H.W. Lenstra, C.P. Schnorr. Korkine-Zolotarev bases and successive minima of a lattice and its reciprocal lattice. Combinatorica, vol 10, 1990, pp 333\u2013348","journal-title":"Combinatorica"}],"container-title":["Information Security and Cryptography","The LLL Algorithm"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-02295-1_14","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,13]],"date-time":"2025-02-13T08:58:59Z","timestamp":1739437139000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-642-02295-1_14"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009]]},"ISBN":["9783642022944","9783642022951"],"references-count":44,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-02295-1_14","relation":{},"ISSN":["1619-7100"],"issn-type":[{"type":"print","value":"1619-7100"}],"subject":[],"published":{"date-parts":[[2009]]},"assertion":[{"value":"7 October 2009","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}