{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,7]],"date-time":"2026-02-07T15:49:42Z","timestamp":1770479382250,"version":"3.49.0"},"publisher-location":"Berlin, Heidelberg","reference-count":24,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540648925","type":"print"},{"value":"9783540684626","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1998]]},"DOI":"10.1007\/bfb0055731","type":"book-chapter","created":{"date-parts":[[2006,7,27]],"date-time":"2006-07-27T17:12:36Z","timestamp":1154020356000},"page":"223-242","source":"Crossref","is-referenced-by-count":44,"title":["Cryptanalysis of the Ajtai-Dwork cryptosystem"],"prefix":"10.1007","author":[{"given":"Phong","family":"Nguyen","sequence":"first","affiliation":[]},{"given":"Jacques","family":"Stern","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2006,5,28]]},"reference":[{"key":"16_CR1","doi-asserted-by":"crossref","unstructured":"L. M. Adleman. On breaking generalized knapsack public key cryptosystems. In Proc. 15th ACMSTOC, pages 402\u2013412, 1983.","DOI":"10.1145\/800061.808771"},{"key":"16_CR2","doi-asserted-by":"crossref","unstructured":"M. Ajtai. Generating hard instances of lattice problems. In Proc. 28th ACM STOC, pages 99\u2013108, 1996. Available at [11] as TR96-007.","DOI":"10.1145\/237814.237838"},{"key":"16_CR3","doi-asserted-by":"crossref","unstructured":"M. Ajtai. The shortest vector problem in L 2 is NP-hard for randomized reductions. In Proc. 30th ACM STOC, 1998. Available at [11] as TR97-047.","DOI":"10.1145\/276698.276705"},{"key":"16_CR4","doi-asserted-by":"crossref","unstructured":"M. Ajtai and C. Dwork. A public-key cryptosystem with worst-case\/average-case equivalence. In Proc. 29th ACM STOC, pages 284\u2013293, 1997. Available at [11] as TR96-065.","DOI":"10.1145\/258533.258604"},{"issue":"2","key":"16_CR5","doi-asserted-by":"publisher","first-page":"317","DOI":"10.1006\/jcss.1997.1472","volume":"54","author":"S. Arora","year":"1997","unstructured":"S. Arora, L. Babai, J. Stern, and Z. Sweedyk. The hardness of approximate optima in lattices, codes, and systems of linear equations. Journal of Computer and System Sciences, 54(2):317\u2013331, 1997.","journal-title":"Journal of Computer and System Sciences"},{"key":"16_CR6","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/BF02579403","volume":"6","author":"L. Babai","year":"1986","unstructured":"L. Babai. On Lov\u00e1sz lattice reduction and the nearest lattice point problem. Combinatorica, 6:1\u201313, 1986.","journal-title":"Combinatorica"},{"key":"16_CR7","first-page":"342","volume":"196","author":"E. Brickell","year":"1985","unstructured":"E. Brickell. Breaking iterated knapsacks. In Proc. CRYPTO'84, volume 196 of LNCS, pages 342\u2013358, 1985.","journal-title":"LNCS"},{"key":"16_CR8","unstructured":"J.-Y. Cai and A. P. Nerurkar. An improved worst-case to average-case connection for lattice problems. In Proc. 38th IEEE FOCS, pages 468\u2013477, 1997."},{"issue":"4","key":"16_CR9","doi-asserted-by":"publisher","first-page":"233","DOI":"10.1007\/s001459900030","volume":"10","author":"D. Coppersmith","year":"1997","unstructured":"D. Coppersmith. Small solutions to polynomial equations, and low exponent RSA vulnerabilities. J. of Cryptology, 10(4):233\u2013260, 1997.","journal-title":"J. of Cryptology"},{"key":"16_CR10","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1007\/BF01201999","volume":"2","author":"M.J. Coster","year":"1992","unstructured":"M.J. Coster, A. Joux, B.A. LaMacchia, A.M. Odlyzko, C.-P. Schnorr, and J. Stern. Improved low-density subset sum algorithms. Computational Complexity, 2:111\u2013128, 1992.","journal-title":"Computational Complexity"},{"key":"16_CR11","unstructured":"ECCC. http:\/\/www.eccc.uni-trier.de\/eccc\/. The Electronic Colloquium on Computational Complexity."},{"key":"16_CR12","unstructured":"P. van Emde Boas. Another NP-complete problem and the complexity of computing short vectors in a lattice. Technical report, Mathematische Instituut, University of Amsterdam, 1981. Report 81-04."},{"key":"16_CR13","unstructured":"O. Goldreich. Foundations of Cryptography (Fragments of a Book). Weizmann Institute of Science, 1995. Available at [11]."},{"key":"16_CR14","doi-asserted-by":"crossref","unstructured":"O. Goldreich and S. Goldwasser. On the limits of non-approximability of lattice problems. In Proc. 30th ACM STOC, 1998. Available at [11] as TR97-031.","DOI":"10.1145\/276698.276704"},{"key":"16_CR15","doi-asserted-by":"crossref","unstructured":"O. Goldreich, S. Goldwasser, and S. Halevi. Eliminating decryption errors in the Ajtai-Dwork cryptosystem. In Proc. of Crypto'97, volume 1294 of LNCS, pages 105\u2013111. Springer-Verlag, 1997. Available at [11] as TR97-018.","DOI":"10.1007\/BFb0052230"},{"key":"16_CR16","unstructured":"A. Joux and J. Stern. Lattice reduction: a toolbox for the cryptanalyst. (to appear in J. of Cryptology)."},{"key":"16_CR17","doi-asserted-by":"crossref","unstructured":"J.C. Lagarias and A.M. Odlyzko. Solving low-density subset sum problems. In Proc. 24th IEEE FOCS, pages 1\u201310. IEEE, 1983.","DOI":"10.1109\/SFCS.1983.70"},{"key":"16_CR18","doi-asserted-by":"publisher","first-page":"515","DOI":"10.1007\/BF01457454","volume":"261","author":"A. K. Lenstra","year":"1982","unstructured":"A. K. Lenstra, H. W. Lenstra, and L. Lov\u00e1sz. Factoring polynomials with rational coefficients. Math. Ann., 261:515\u2013534, 1982.","journal-title":"Math. Ann."},{"key":"16_CR19","doi-asserted-by":"crossref","unstructured":"P. Nguyen and J. Stern. Merkle-Hellman revisited: a cryptanalysis of the Qu-Vanstone cryptosystem based on group factorizations. In Proc. of Crypto '97, volume 1294 of LNCS, pages 198\u2013212. Springer-Verlag, 1997.","DOI":"10.1007\/BFb0052236"},{"key":"16_CR20","unstructured":"P. Nguyen and J. Stern. A converse to the Ajtai-Dwork security proof and its cryptographic implications. Technical Report TR98-010, ECCC, 1998. Revision available at [11]."},{"key":"16_CR21","doi-asserted-by":"publisher","first-page":"201","DOI":"10.1016\/0304-3975(87)90064-8","volume":"53","author":"C.-P. Schnorr","year":"1987","unstructured":"C.-P. Schnorr. A hierarchy of polynomial lattice basis reduction algorithms. Theoretical Computer Science, 53:201\u2013224, 1987.","journal-title":"Theoretical Computer Science"},{"key":"16_CR22","doi-asserted-by":"crossref","unstructured":"A. Shamir. A polynomial time algorithm for breaking the basic Merkle-Hellman cryptosystem. In Proc. 23rd IEEE FOCS, pages 145\u2013152, 1982.","DOI":"10.1109\/SFCS.1982.5"},{"key":"16_CR23","unstructured":"V. Shoup. Number Theory C++ Library (NTL) version 2.0. Can be obtained at http:\/\/www.cs.wisc.edu\/~shoup\/ntl\/."},{"key":"16_CR24","doi-asserted-by":"crossref","unstructured":"J. Stern. Secret linear congruential generators are not cryptographically secure. In Proc. 28th IEEE FOCS, pages 421\u2013426, 1987.","DOI":"10.1109\/SFCS.1987.51"}],"container-title":["Lecture Notes in Computer Science","Advances in Cryptology \u2014 CRYPTO '98"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BFb0055731","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,20]],"date-time":"2019-04-20T05:09:06Z","timestamp":1555736946000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BFb0055731"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1998]]},"ISBN":["9783540648925","9783540684626"],"references-count":24,"URL":"https:\/\/doi.org\/10.1007\/bfb0055731","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[1998]]}}}