{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,28]],"date-time":"2026-04-28T10:15:56Z","timestamp":1777371356882,"version":"3.51.4"},"publisher-location":"Berlin, Heidelberg","reference-count":17,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540658948","type":"print"},{"value":"9783540488927","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1999]]},"DOI":"10.1007\/3-540-48892-8_18","type":"book-chapter","created":{"date-parts":[[2007,8,28]],"date-time":"2007-08-28T16:11:38Z","timestamp":1188317498000},"page":"219-233","source":"Crossref","is-referenced-by-count":8,"title":["A Lattice- Based Public-Key Cryptosystem"],"prefix":"10.1007","author":[{"given":"Jin -Yi","family":"Cai","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Thomas W.","family":"Cusick","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2002,3,28]]},"reference":[{"key":"18_CR1","unstructured":"M. Ajtai. Generating hard instances of lattice problems. In Proc. 28th Annual ACM Symposium on the Theory of Computing, 1996. Full version available from ECCC, Electronic Colloquium on Computational Complexity TR96-007, at http:\/\/www.eccc.uni-trier.de\/eccc\/ ."},{"key":"18_CR2","unstructured":"M. Ajtai. The shortest vector problem in L2 is NP-hard for randomized reductions. Electronic Colloquium on Computational Complexity, TR97-047 at http:\/\/www.eccc.uni-trier.de\/eccc\/ ."},{"key":"18_CR3","doi-asserted-by":"crossref","unstructured":"M. Ajtai and C. Dwork. A public-key cryptosystem with worst-case\/average-case equivalence. 1996. Available from ECCC, Electronic Colloquium on Computational Complexity TR96-065, at http:\/\/www.eccc.uni-trier.de\/eccc\/ .","DOI":"10.1145\/258533.258604"},{"key":"18_CR4","doi-asserted-by":"crossref","unstructured":"S. Arora, L. Babai, J. Stern, and Z. Sweedyk. The hardness of approximate optima in lattices, codes, and systems of linear equations. In Proc. 34th IEEE Symposium on Foundations of Computer Science (FOCS), 1993, 724\u2013733.","DOI":"10.1109\/SFCS.1993.366815"},{"key":"18_CR5","unstructured":"J-Y. Cai and A. Nerurkar. An Improved Worst-Case to Average-Case Connection for Lattice Problems. In Proc. 38th IEEE Symposium on Foundations of Computer Science (FOCS), 1997, 468\u2013477."},{"key":"18_CR6","unstructured":"J-Y. Cai and A. Nerurkar. Approximating the SVP to within a factor (1 + 1\/dim\u2208) is NP-hard under randomized reductions. Available from ECCC, Electronic Colloquium on Computational Complexity TR97-059, at http:\/\/www.eccc.uni-trier.de\/eccc\/ ."},{"key":"18_CR7","unstructured":"J-Y. Cai. A Primal-Dual Relation for Lattices and the Complexity of Shortest Lattice Vector Problem. To appear in Theoretical Computer Science."},{"key":"18_CR8","unstructured":"J-Y. Cai. A new transference theorem and applications to Ajtai\u2019s connection factor. Electronic Colloquium on Computational Complexity TR98-005, at http:\/\/www.eccc.uni-trier.de\/eccc\/ ."},{"key":"18_CR9","unstructured":"O. Goldreich and S. Goldwasser. On the Limits of Non-Approximability of Lattice Problems. Electronic Colloquium on Computational Complexity TR97-031, at http:\/\/www.eccc.uni-trier.de\/eccc\/ ."},{"key":"18_CR10","unstructured":"O. Goldreich, S. Goldwasser, and S. Halevi. Collision-free hashing from lattice problems. 1996. Available from ECCC, Electronic Colloquium on Computational Complexity TR96-042, at http:\/\/www.eccc.uni-trier.de\/eccc\/ ."},{"key":"18_CR11","unstructured":"O. Goldreich, S. Goldwasser, and S. Halevi. Public-key cryptosystems from lattice reduction problems. 1996. Available from ECCC, Electronic Colloquium on Computational Complexity TR96-056, at http:\/\/www.eccc.uni-trier.de\/eccc\/ ."},{"key":"18_CR12","doi-asserted-by":"publisher","first-page":"196","DOI":"10.1137\/0214016","volume":"14","author":"J. C. Lagarias","year":"1985","unstructured":"J. C. Lagarias. The computational complexity of simultaneous diophantine approximation problems. SIAM Journal of Computing, Volume 14, page 196\u2013209, 1985.","journal-title":"SIAM Journal of Computing"},{"issue":"4","key":"18_CR13","doi-asserted-by":"publisher","first-page":"333","DOI":"10.1007\/BF02128669","volume":"10","author":"J. C. Lagarias","year":"1990","unstructured":"J. C. Lagarias, H. W. Lenstra, and C. P. Schnorr. Korkin-Zolotarev Bases and Successive Minima of a Lattice and its Reciprocal Lattice. Combinatorica, 10:(4), 1990, 333\u2013348.","journal-title":"Combinatorica"},{"key":"18_CR14","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. Mathematische Annalen, 261:515\u2013534, 1982.","journal-title":"Mathematische Annalen"},{"key":"18_CR15","doi-asserted-by":"crossref","unstructured":"A.M. Odlyzko. The rise and fall of knapsack cryptosystems. in Cryptology and Computational Number Theory, American Mathematical Society, pp. 75\u201388, 1990.","DOI":"10.1090\/psapm\/042\/1095552"},{"key":"18_CR16","unstructured":"C. P. Schnorr. A hierarchy of polynomial time basis reduction algorithms. Theory of Algorithms, pages 375\u2013386, 1985."},{"key":"18_CR17","unstructured":"P. van Emde Boas. Another NP-complete partition problem and the complexity of computing short vectors in lattices. Technical Report 81-04, Mathematics Department, University of Amsterdam, 1981."}],"container-title":["Lecture Notes in Computer Science","Selected Areas in Cryptography"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-48892-8_18","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,5,13]],"date-time":"2023-05-13T23:04:08Z","timestamp":1684019048000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-48892-8_18"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1999]]},"ISBN":["9783540658948","9783540488927"],"references-count":17,"URL":"https:\/\/doi.org\/10.1007\/3-540-48892-8_18","relation":{},"ISSN":["0302-9743"],"issn-type":[{"value":"0302-9743","type":"print"}],"subject":[],"published":{"date-parts":[[1999]]}}}