{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,10]],"date-time":"2026-04-10T04:19:31Z","timestamp":1775794771005,"version":"3.50.1"},"publisher-location":"New York, NY, USA","reference-count":52,"publisher":"ACM","license":[{"start":{"date-parts":[[2010,6,5]],"date-time":"2010-06-05T00:00:00Z","timestamp":1275696000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2010,6,5]]},"DOI":"10.1145\/1806689.1806739","type":"proceedings-article","created":{"date-parts":[[2010,6,8]],"date-time":"2010-06-08T12:37:34Z","timestamp":1276000654000},"page":"351-358","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":110,"title":["A deterministic single exponential time algorithm for most lattice problems based on voronoi cell computations"],"prefix":"10.1145","author":[{"given":"Daniele","family":"Micciancio","sequence":"first","affiliation":[{"name":"University of California, San Diego, La Jolla, CA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Panagiotis","family":"Voulgaris","sequence":"additional","affiliation":[{"name":"University of California, San Diego, La Jolla, CA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2010,6,5]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2002.800499"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/1089023.1089025"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/276698.276705"},{"key":"e_1_3_2_1_4_1","volume-title":"Quaderni di Matematica, 13:1--32","author":"Ajtai M.","year":"2004","unstructured":"M. Ajtai . Generating hard instances of lattice problems. Complexity of Computations and Proofs , Quaderni di Matematica, 13:1--32 , 2004 . Preliminary version in STOC 1996. M. Ajtai. Generating hard instances of lattice problems. Complexity of Computations and Proofs, Quaderni di Matematica, 13:1--32, 2004. Preliminary version in STOC 1996."},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/380752.380857"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.5555\/872747.873162"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2005.40"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1997.1472"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579403"},{"key":"e_1_3_2_1_10_1","series-title":"LNCS","first-page":"248","volume-title":"Proceedings of ICALP '00","author":"Bl\u00f6mer J.","year":"2000","unstructured":"J. Bl\u00f6mer . Closest vectors, successive minima and dual HKZ-bases of lattices . In Proceedings of ICALP '00 , volume 1853 of LNCS , pages 248 -- 259 . Springer , July 2000 . J. Bl\u00f6mer. Closest vectors, successive minima and dual HKZ-bases of lattices. In Proceedings of ICALP '00, volume 1853 of LNCS, pages 248--259. Springer, July 2000."},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2008.12.045"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/301250.301441"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1999.1649"},{"key":"e_1_3_2_1_14_1","volume-title":"An introduction to the geometry of numbers","author":"Cassels J. W. S.","year":"1971","unstructured":"J. W. S. Cassels . An introduction to the geometry of numbers . Springer-Verlag , New York , 1971 . J. W. S. Cassels. An introduction to the geometry of numbers. Springer-Verlag, New York, 1971."},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2007.03.014"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2006.881835"},{"key":"e_1_3_2_1_17_1","volume-title":"Sphere packings, lattices and groups","author":"Conway J. H.","year":"1998","unstructured":"J. H. Conway and N. J. A. Sloane . Sphere packings, lattices and groups . Springer Verlag , 3 rd edition, 1998 . J. H. Conway and N. J. A. Sloane. Sphere packings, lattices and groups. Springer Verlag, 3rd edition, 1998.","edition":"3"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01201999"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-003-0019-y"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2004.01.002"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/11818175_7"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/1374376.1374408"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(99)00083-6"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-005-0193-y"},{"key":"e_1_3_2_1_25_1","series-title":"LNCS","first-page":"170","volume-title":"Proceedings of CRYPTO '07","author":"Hanrot G.","year":"2007","unstructured":"G. Hanrot and D. Stehl\u00e9 . Improved analysis of kannan's shortest lattice vector algorithm . In Proceedings of CRYPTO '07 , volume 4622 of LNCS , pages 170 -- 186 . Springer , Aug. 2007 . G. Hanrot and D. Stehl\u00e9. Improved analysis of kannan's shortest lattice vector algorithm. In Proceedings of CRYPTO '07, volume 4622 of LNCS, pages 170--186. Springer, Aug. 2007."},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2006.23"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/1250790.1250859"},{"key":"e_1_3_2_1_28_1","volume-title":"Dec.","author":"Helfrich B.","year":"1985","unstructured":"B. Helfrich . Algorithms to construct Minkowski reduced and Hermite reduced lattice bases. Theoretical Computer Science, 41(2--3):125--139 , Dec. 1985 . B. Helfrich. Algorithms to construct Minkowski reduced and Hermite reduced lattice bases. Theoretical Computer Science, 41(2--3):125--139, Dec. 1985."},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/s001459900042"},{"key":"e_1_3_2_1_30_1","volume-title":"Aug.","author":"Kannan R.","year":"1987","unstructured":"R. Kannan . Minkowski's convex body theorem and integer programming. Mathematics of operation research, 12(3):415--440 , Aug. 1987 . Prelim. version in STOC 1983. R. Kannan. Minkowski's convex body theorem and integer programming. Mathematics of operation research, 12(3):415--440, Aug. 1987. Prelim. version in STOC 1983."},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/1089023.1089027"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/800061.808743"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01457454"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.8.4.538"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1109\/18.915688"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539700373039"},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539703433511"},{"key":"e_1_3_2_1_38_1","first-page":"84","volume-title":"Proceedings of SODA 2008","author":"Micciancio D.","year":"2008","unstructured":"D. Micciancio . Efficient reductions among lattice problems . In Proceedings of SODA 2008 , pages 84 -- 93 . ACM\/SIAM, Jan. 2008 . D. Micciancio. Efficient reductions among lattice problems. In Proceedings of SODA 2008, pages 84--93. ACM\/SIAM, Jan. 2008."},{"key":"e_1_3_2_1_39_1","series-title":"The Kluwer International Series in Engineering and Computer Science","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4615-0897-7","volume-title":"Complexity of Lattice Problems: a cryptographic perspective","author":"Micciancio D.","year":"2002","unstructured":"D. Micciancio and S. Goldwasser . Complexity of Lattice Problems: a cryptographic perspective , volume 671 of The Kluwer International Series in Engineering and Computer Science . Kluwer Academic Publishers , Boston, Massachusetts , Mar. 2002 . D. Micciancio and S. Goldwasser. Complexity of Lattice Problems: a cryptographic perspective, volume 671 of The Kluwer International Series in Engineering and Computer Science. Kluwer Academic Publishers, Boston, Massachusetts, Mar. 2002."},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539705447360"},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.5555\/1873601.1873720"},{"key":"e_1_3_2_1_42_1","series-title":"LNCS","first-page":"146","volume-title":"Proceedings of CaLC '01","author":"Nguyen P.","year":"2001","unstructured":"P. Nguyen and J. Stern . The two faces of lattices in cryptology . In Proceedings of CaLC '01 , volume 2146 of LNCS , pages 146 -- 180 . Springer , Mar. 2001 . P. Nguyen and J. Stern. The two faces of lattices in cryptology. In Proceedings of CaLC '01, volume 2146 of LNCS, pages 146--180. Springer, Mar. 2001."},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1515\/JMC.2008.009"},{"key":"e_1_3_2_1_44_1","series-title":"Procedings of Symposia in Applied Mathematics","first-page":"75","volume-title":"Cryptology and computational number theory","author":"Odlyzko A. M.","year":"1989","unstructured":"A. M. Odlyzko . The rise and fall of knapsack cryptosystems . In C. Pomerance, editor, Cryptology and computational number theory , volume 42 of Procedings of Symposia in Applied Mathematics , pages 75 -- 88 , Boulder, Colorado , 1989 . AMS. A. M. Odlyzko. The rise and fall of knapsack cryptosystems. In C. Pomerance, editor, Cryptology and computational number theory, volume 42 of Procedings of Symposia in Applied Mathematics, pages 75--88, Boulder, Colorado, 1989. AMS."},{"key":"e_1_3_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2004.833350"},{"key":"e_1_3_2_1_47_1","volume-title":"Aug.","author":"Schnorr C.-P.","year":"1987","unstructured":"C.-P. Schnorr . A hierarchy of polynomial time lattice basis reduction algorithms. Theoretical Computer Science, 53(2--3):201--224 , Aug. 1987 . C.-P. Schnorr. A hierarchy of polynomial time lattice basis reduction algorithms. Theoretical Computer Science, 53(2--3):201--224, Aug. 1987."},{"key":"e_1_3_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(88)90004-1"},{"key":"e_1_3_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.5555\/1140956.1709619"},{"key":"e_1_3_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01581144"},{"key":"e_1_3_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0025-5718-09-02224-8"},{"key":"e_1_3_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1137\/060676362"},{"key":"e_1_3_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1109\/18.481786"}],"event":{"name":"STOC'10: Symposium on Theory of Computing","location":"Cambridge Massachusetts USA","acronym":"STOC'10","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the forty-second ACM symposium on Theory of computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1806689.1806739","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1806689.1806739","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T11:39:37Z","timestamp":1750246777000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1806689.1806739"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,6,5]]},"references-count":52,"alternative-id":["10.1145\/1806689.1806739","10.1145\/1806689"],"URL":"https:\/\/doi.org\/10.1145\/1806689.1806739","relation":{},"subject":[],"published":{"date-parts":[[2010,6,5]]},"assertion":[{"value":"2010-06-05","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}