{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,5]],"date-time":"2026-10-05T02:26:30Z","timestamp":1791167190503,"version":"4.1.0"},"publisher-location":"Berlin, Heidelberg","reference-count":22,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540327318","type":"print"},{"value":"9783540327325","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2006]]},"DOI":"10.1007\/11681878_8","type":"book-chapter","created":{"date-parts":[[2006,2,28]],"date-time":"2006-02-28T02:41:35Z","timestamp":1141094495000},"page":"145-166","source":"Crossref","is-referenced-by-count":214,"title":["Efficient Collision-Resistant Hashing from Worst-Case Assumptions on Cyclic Lattices"],"prefix":"10.1007","author":[{"given":"Chris","family":"Peikert","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Alon","family":"Rosen","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"key":"8_CR1","doi-asserted-by":"crossref","unstructured":"Ajtai, M.: Generating hard instances of lattice problems (extended abstract). In: Proc. 28th Annual ACM Symposium on Theory of Computing (STOC 1996), pp. 99\u2013108 (1996)","DOI":"10.1145\/237814.237838"},{"key":"8_CR2","doi-asserted-by":"crossref","unstructured":"Ajtai, M.: The shortest vector problem in L2 is NP-hard for randomized reductions (extended abstract). In: Proc. 30th Annual ACM Symposium on Theory of Computing (STOC 1998), pp. 10\u201319 (1998)","DOI":"10.1145\/276698.276705"},{"key":"8_CR3","doi-asserted-by":"crossref","unstructured":"Ajtai, M., Dwork, C.: A public-key cryptosystem with worst-case\/average-case equivalence. In: Proc. 29th Annual ACM Symposium on Theory of Computing (STOC 1997), pp. 284\u2013293 (1997)","DOI":"10.1145\/258533.258604"},{"issue":"2","key":"8_CR4","doi-asserted-by":"publisher","first-page":"317","DOI":"10.1006\/jcss.1997.1472","volume":"54","author":"S. Arora","year":"1997","unstructured":"Arora, S., Babai, L., Stern, J., Sweedyk, Z.: The hardness of approximate optima in lattices, codes, and systems of linear equations. J. Computer and System Sciences\u00a054(2), 317\u2013331 (1997)","journal-title":"J. Computer and System Sciences"},{"issue":"2","key":"8_CR5","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\u2009+\u20091\/dim\u03b5) is NP-hard under randomized reductions. Jounal of Computer and System Sciences\u00a059(2), 221\u2013239 (1999)","journal-title":"Jounal of Computer and System Sciences"},{"key":"8_CR6","doi-asserted-by":"crossref","unstructured":"Cai, J.-Y., Nerurkar, A.P.: An improved worst-case to average-case connection for lattice problems. In: Proc. 38th Annual Symposium on Foundations of Computer Science (FOCS 1997), p. 468 (1997)","DOI":"10.1109\/SFCS.1997.646135"},{"key":"8_CR7","first-page":"99","volume-title":"Proc. 39th Annual Symposium on Foundations of Computer Science (FOCS 1998)","author":"I. Dinur","year":"1998","unstructured":"Dinur, I., Kindler, G., Safra, S.: Approximating-CVP to within almostpolynomial factors is NP-hard. In: Proc. 39th Annual Symposium on Foundations of Computer Science (FOCS 1998), pp. 99\u2013111. IEEE Computer Society, Los Alamitos (1998)"},{"key":"8_CR8","volume-title":"Abstract Algebra","author":"D.S. Dummit","year":"1999","unstructured":"Dummit, D.S., Foote, R.M.: Abstract Algebra, 2nd edn. Prentice Hall, Upper Saddle River (1999)","edition":"2"},{"issue":"1","key":"8_CR9","doi-asserted-by":"publisher","first-page":"217","DOI":"10.1137\/S0097539704443276","volume":"35","author":"R. Genarro","year":"2005","unstructured":"Genarro, R., Gertner, Y., Katz, J., Trevisan, L.: Bounds on the efficiency of generic cryptographic constructions. SIAM J. Computing\u00a035(1), 217\u2013246 (2005)","journal-title":"SIAM J. Computing"},{"key":"8_CR10","unstructured":"Goldreich, O., Goldwasser, S., Halevi, S.: Collision-free hashing from lattice problems. Electronic Colloquium on Computational Complexity (ECCC) Report TR96-042 (1996)"},{"key":"8_CR11","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":"8_CR12","first-page":"126","volume-title":"Proc. 45th Symposium on Foundations of Computer Science (FOCS 2004)","author":"S. Khot","year":"2004","unstructured":"Khot, S.: Hardness of approximating the shortest vector problem in lattices. In: Proc. 45th Symposium on Foundations of Computer Science (FOCS 2004), pp. 126\u2013135. IEEE Computer Society, Los Alamitos (2004)"},{"key":"8_CR13","unstructured":"Lyubashevsky, V., Micciancio, D.: Generalized compact knapsacks are collision resistant. Electronic Colloquium on Computational Complexity (ECCC) Report TR05-142 (2005)"},{"key":"8_CR14","unstructured":"Micciancio, D.: Generalized compact knapsaks, cyclic lattices, and efficient oneway functions from worst-case complexity assumptions. In: Proc. 43rd Annual Symposium on Foundations of Computer Science (FOCS (2002)"},{"issue":"6","key":"8_CR15","doi-asserted-by":"publisher","first-page":"2008","DOI":"10.1137\/S0097539700373039","volume":"30","author":"D. Micciancio","year":"2001","unstructured":"Micciancio, D.: The shortest vector problem is NP-hard to approximate to within some constant. SIAM J. Computing\u00a030(6), 2008\u20132035 (March 2001)","journal-title":"SIAM J. Computing"},{"key":"8_CR16","series-title":"The Kluwer International Series in Engineering and Computer Science","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4615-0897-7","volume-title":"Complexity of Lattice Problems: a cryptographic perspective","author":"D. Micciancio","year":"2002","unstructured":"Micciancio, D., Goldwasser, S.: Complexity of Lattice Problems: a cryptographic perspective. The Kluwer International Series in Engineering and Computer Science, vol.\u00a0671. Kluwer Academic Publishers, Boston, Massachusetts (2002)"},{"key":"8_CR17","unstructured":"Micciancio, D., Regev, O.: Worst-case to average-case reductions based on Gaussian measure, pp. 371\u2013381"},{"issue":"6","key":"8_CR18","doi-asserted-by":"publisher","first-page":"899","DOI":"10.1145\/1039488.1039490","volume":"51","author":"O. Regev","year":"2004","unstructured":"Regev, O.: New lattice-based cryptographic constructions. J. ACM\u00a051(6), 899\u2013942 (2004)","journal-title":"J. ACM"},{"key":"8_CR19","doi-asserted-by":"crossref","unstructured":"Regev, O.: On lattices, learning with errors, random linear codes, and cryptography. In: Proc. 37th Annual ACM Symposium on Theory of Computing (STOC 2005), pp. 84\u201393 (2005)","DOI":"10.1145\/1060590.1060603"},{"key":"8_CR20","unstructured":"van Emde Boas, P.: Another NP-complete problem and the complexity of computing short vectors in a lattice. Technical Report 81-04, University of Amsterdam (1981)"},{"key":"8_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1007\/11535218_2","volume-title":"Advances in Cryptology \u2013 CRYPTO 2005","author":"X. Wang","year":"2005","unstructured":"Wang, X., Yin, Y.L., Yu, H.: Finding collisions in the full SHA-1. In: Shoup, V. (ed.) CRYPTO 2005. LNCS, vol.\u00a03621, pp. 17\u201336. Springer, Heidelberg (2005)"},{"key":"8_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1007\/11426639_2","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2005","author":"X. Wang","year":"2005","unstructured":"Wang, X., Yu, H.: How to break MD5 and other hash functions. In: Cramer, R. (ed.) EUROCRYPT 2005. LNCS, vol.\u00a03494, pp. 19\u201335. Springer, Heidelberg (2005)"}],"container-title":["Lecture Notes in Computer Science","Theory of Cryptography"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11681878_8.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T03:16:53Z","timestamp":1619493413000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11681878_8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006]]},"ISBN":["9783540327318","9783540327325"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/11681878_8","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2006]]}}}