{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,8]],"date-time":"2024-09-08T11:01:28Z","timestamp":1725793288246},"publisher-location":"Cham","reference-count":22,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319063195"},{"type":"electronic","value":"9783319063201"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014]]},"DOI":"10.1007\/978-3-319-06320-1_37","type":"book-chapter","created":{"date-parts":[[2014,4,27]],"date-time":"2014-04-27T20:59:27Z","timestamp":1398632367000},"page":"511-523","source":"Crossref","is-referenced-by-count":0,"title":["New Variants of Lattice Problems and Their NP-Hardness"],"prefix":"10.1007","author":[{"given":"Wulu","family":"Li","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"37_CR1","doi-asserted-by":"crossref","unstructured":"Ajtai, M.: The shortest vector problem in l 2 is np-hard for randomized reductions. In: Proceedings of the Thirtieth Annual ACM Symposium on Theory of Computing, pp. 10\u201319. ACM (1998)","DOI":"10.1145\/276698.276705"},{"key":"37_CR2","doi-asserted-by":"crossref","unstructured":"Ajtai, M., Dwork, C.: A public-key cryptosystem with worst-case\/average-case equivalence. In: Proceedings of the Twenty-ninth Annual ACM Symposium on Theory of Computing, pp. 284\u2013293. ACM (1997)","DOI":"10.1145\/258533.258604"},{"key":"37_CR3","doi-asserted-by":"crossref","unstructured":"Ajtai, M., Kumar, R., Sivakumar, D.: A sieve algorithm for the shortest lattice vector problem. In: Proceedings of the Thirty-third Annual ACM Symposium on Theory of Computing, pp. 601\u2013610. ACM (2001)","DOI":"10.1145\/380752.380857"},{"issue":"1","key":"37_CR4","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/BF02579403","volume":"6","author":"L. Babai On","year":"1986","unstructured":"Babai On, L.: lov\u00e1szlattice reduction and the nearest lattice point problem. Combinatorica\u00a06(1), 1\u201313 (1986)","journal-title":"Combinatorica"},{"key":"37_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"65","DOI":"10.1007\/978-3-540-73420-8_8","volume-title":"Automata, Languages and Programming","author":"J. Bl\u00f6mer","year":"2007","unstructured":"Bl\u00f6mer, J., Naewe, S.: Sampling methods for shortest vectors, closest vectors and successive minima. In: Arge, L., Cachin, C., Jurdzi\u0144ski, T., Tarlecki, A. (eds.) ICALP 2007. LNCS, vol.\u00a04596, pp. 65\u201377. Springer, Heidelberg (2007)"},{"issue":"2","key":"37_CR6","doi-asserted-by":"publisher","first-page":"221","DOI":"10.1006\/jcss.1999.1649","volume":"59","author":"J.-Y. Cai","year":"1999","unstructured":"Cai, J.-Y., Nerurkar, A.: Approximating the svp to within a factor (1+ 1\/dim e) is np-hard under randomized reductions. Journal of Computer and System Sciences\u00a059(2), 221\u2013239 (1999)","journal-title":"Journal of Computer and System Sciences"},{"key":"37_CR7","unstructured":"Gary, M.R., Johnson, D.S.: Computers and intractability: A guide to the theory of np-completeness (1979)"},{"key":"37_CR8","doi-asserted-by":"crossref","unstructured":"Gentry, C.: Fully homomorphic encryption using ideal lattices (2009)","DOI":"10.1145\/1536414.1536440"},{"key":"37_CR9","doi-asserted-by":"crossref","unstructured":"Goldreich, O., Goldwasser, S.: On the limits of non-approximability of lattice problems. In: Proceedings of the Thirtieth Annual ACM Symposium on Theory of Computing, pp. 1\u20139. ACM (1998)","DOI":"10.1145\/276698.276704"},{"key":"37_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"112","DOI":"10.1007\/BFb0052231","volume-title":"Advances in Cryptology - CRYPTO \u201997","author":"O. Goldreich","year":"1997","unstructured":"Goldreich, O., Goldwasser, S., Halevi, S.: Public-key cryptosystems from lattice reduction problems. In: Kaliski Jr., B.S. (ed.) CRYPTO 1997. LNCS, vol.\u00a01294, pp. 112\u2013131. Springer, Heidelberg (1997)"},{"key":"37_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"267","DOI":"10.1007\/BFb0054868","volume-title":"Algorithmic Number Theory","author":"J. Hoffstein","year":"1998","unstructured":"Hoffstein, J., Pipher, J., Silverman, J.H.: NTRU: A ring-based public key cryptosystem. In: Buhler, J.P. (ed.) ANTS 1998. LNCS, vol.\u00a01423, pp. 267\u2013288. Springer, Heidelberg (1998)"},{"issue":"5","key":"37_CR12","doi-asserted-by":"publisher","first-page":"789","DOI":"10.1145\/1089023.1089027","volume":"52","author":"S. Khot","year":"2005","unstructured":"Khot, S.: Hardness of approximating the shortest vector problem in lattices. Journal of the ACM (JACM)\u00a052(5), 789\u2013808 (2005)","journal-title":"Journal of the ACM (JACM)"},{"issue":"4","key":"37_CR13","doi-asserted-by":"publisher","first-page":"515","DOI":"10.1007\/BF01457454","volume":"261","author":"A.K. Lenstra","year":"1982","unstructured":"Lenstra, A.K., Lenstra, H.W., Lov\u00e1sz, L.: Factoring polynomials with rational coefficients. Mathematische Annalen\u00a0261(4), 515\u2013534 (1982)","journal-title":"Mathematische Annalen"},{"issue":"6","key":"37_CR14","doi-asserted-by":"publisher","first-page":"2008","DOI":"10.1137\/S0097539700373039","volume":"30","author":"D. Micciancio","year":"2001","unstructured":"Micciancio, D.: The shortest vector in a lattice is hard to approximate to within some constant. SIAM Journal on Computing\u00a030(6), 2008\u20132035 (2001)","journal-title":"SIAM Journal on Computing"},{"issue":"1","key":"37_CR15","doi-asserted-by":"publisher","first-page":"487","DOI":"10.4086\/toc.2012.v008a022","volume":"8","author":"D. Micciancio","year":"2012","unstructured":"Micciancio, D.: Inapproximability of the shortest vector problem: Toward a deterministic reduction. Theory of Computing\u00a08(1), 487\u2013512 (2012)","journal-title":"Theory of Computing"},{"key":"37_CR16","doi-asserted-by":"crossref","unstructured":"Micciancio, D., Goldwasser, S.: Complexity of lattice problems: a cryptographic perspective, vol.\u00a0671. Springer (2002)","DOI":"10.1007\/978-1-4615-0897-7"},{"key":"37_CR17","doi-asserted-by":"crossref","unstructured":"Micciancio, D., Voulgaris, P.: A deterministic single exponential time algorithm for most lattice problems based on voronoi cell computations. In: Proceedings of the 42nd ACM Symposium on Theory of Computing, pp. 351\u2013358. ACM (2010)","DOI":"10.1145\/1806689.1806739"},{"key":"37_CR18","unstructured":"Minkowski, H.: Geometrie der zahlen. BG Teubner (1910)"},{"key":"37_CR19","doi-asserted-by":"crossref","unstructured":"Regev, O.: On lattices, learning with errors, random linear codes, and cryptography. J. ACM\u00a056(6), 34:1\u201334:40 (2009)","DOI":"10.1145\/1568318.1568324"},{"issue":"2","key":"37_CR20","doi-asserted-by":"publisher","first-page":"201","DOI":"10.1016\/0304-3975(87)90064-8","volume":"53","author":"C.-P. Schnorr","year":"1987","unstructured":"Schnorr, C.-P.: A hierarchy of polynomial time lattice basis reduction algorithms. Theoretical Computer Science\u00a053(2), 201\u2013224 (1987)","journal-title":"Theoretical Computer Science"},{"key":"37_CR21","unstructured":"van Emde-Boas, P.: Another NP-complete partition problem and the complexity of computing short vectors in a lattice, Department, Univ. (1981)"},{"key":"37_CR22","doi-asserted-by":"crossref","first-page":"198","DOI":"10.1515\/crll.1908.134.198","volume":"134","author":"G. Vorono\u00ef","year":"1908","unstructured":"Vorono\u00ef, G.: Nouvelles applications des param\u00e8tres continus \u00e0 la th\u00e9orie des formes quadratiques. deuxi\u00e8me m\u00e9moire. recherches sur les parall\u00e9llo\u00e8dres primitifs. Journal f\u00fcr die reine und angewandte Mathematik\u00a0134, 198\u2013287 (1908)","journal-title":"Journal f\u00fcr die reine und angewandte Mathematik"}],"container-title":["Lecture Notes in Computer Science","Information Security Practice and Experience"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-06320-1_37","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,8,18]],"date-time":"2020-08-18T08:18:43Z","timestamp":1597738723000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-06320-1_37"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014]]},"ISBN":["9783319063195","9783319063201"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-06320-1_37","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2014]]}}}