{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,10]],"date-time":"2026-04-10T04:21:52Z","timestamp":1775794912863,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":24,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540359074","type":"print"},{"value":"9783540359081","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2006]]},"DOI":"10.1007\/11787006_13","type":"book-chapter","created":{"date-parts":[[2006,6,28]],"date-time":"2006-06-28T19:23:09Z","timestamp":1151522589000},"page":"144-155","source":"Crossref","is-referenced-by-count":210,"title":["Generalized Compact Knapsacks Are Collision Resistant"],"prefix":"10.1007","author":[{"given":"Vadim","family":"Lyubashevsky","sequence":"first","affiliation":[]},{"given":"Daniele","family":"Micciancio","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"issue":"5","key":"13_CR1","doi-asserted-by":"publisher","first-page":"749","DOI":"10.1145\/1089023.1089025","volume":"52","author":"D. Aharonov","year":"2005","unstructured":"Aharonov, D., Regev, O.: Lattice problems in NP \u2229 coNP. Journal of the ACM\u00a052(5), 749\u2013765 (2005)","journal-title":"Journal of the ACM"},{"key":"13_CR2","doi-asserted-by":"crossref","unstructured":"M.\u00a0Ajtai. Generating hard instances of lattice problems. In STOC, pages 99\u2013108, 1996.","DOI":"10.1145\/237814.237838"},{"key":"13_CR3","doi-asserted-by":"crossref","unstructured":"Ajtai, M., Kumar, R., Sivakumar, D.: A sieve algorithm for the shortest lattice vector problem. In: STOC, pp. 601\u2013610 (2001)","DOI":"10.1145\/380752.380857"},{"key":"13_CR4","doi-asserted-by":"crossref","unstructured":"Biham, E., Chen, R., Joux, A., Carribault, P., Jalby, W., Lemuet, C.: Collisions of SHA-0 and Reduced SHA-1. In: EUROCRYPT (2005)","DOI":"10.1007\/11426639_3"},{"key":"13_CR5","unstructured":"Cai, J., Nerurkar, A.: An improved worst-case to average-case connection for lattice problems. In: FOCS, pp. 468\u2013477 (1997)"},{"issue":"5","key":"13_CR6","doi-asserted-by":"publisher","first-page":"901","DOI":"10.1109\/18.21214","volume":"34","author":"B. Chor","year":"1988","unstructured":"Chor, B., Rivest, R.L.: A knapsack type public-key cryptosystem based on arithmetic in finite fields. IEEE Trans. Inform. Theory\u00a034(5), 901\u2013909 (1988)","journal-title":"IEEE Trans. Inform. Theory"},{"key":"13_CR7","doi-asserted-by":"crossref","unstructured":"Damgard, I.: A design principle for hash functions. In: CRYPTO 1989, pp. 416\u2013427 (1989)","DOI":"10.1007\/0-387-34805-0_39"},{"issue":"1","key":"13_CR8","doi-asserted-by":"publisher","first-page":"55","DOI":"10.1016\/S0304-3975(01)00290-0","volume":"285","author":"I. Dinur","year":"2002","unstructured":"Dinur, I.: Approximating SVP \u2009\u221e\u2009 to within almost-polynomial factors is NP-hard. Theor. Comput. Sci.\u00a0285(1), 55\u201371 (2002)","journal-title":"Theor. Comput. Sci."},{"key":"13_CR9","doi-asserted-by":"crossref","unstructured":"Goldreich, O., Goldwasser, S.: On the limits of nonapproximability of lattice problems. J. Comput. Syst. Sci.\u00a060(3) (2000)","DOI":"10.1006\/jcss.1999.1686"},{"key":"13_CR10","doi-asserted-by":"crossref","unstructured":"Hoffstein, J., Pipher, J., Silverman, J.H.: Ntru: A ring-based public key cryptosystem. In: ANTS, pp. 267\u2013288 (1998)","DOI":"10.1007\/BFb0054868"},{"key":"13_CR11","doi-asserted-by":"crossref","unstructured":"Joux, A., Granboulan, L.: A practical attack against knapsack based hash functions. In: EUROCRYPT 1994, pp. 58\u201366 (1994)","DOI":"10.1007\/BFb0053424"},{"key":"13_CR12","doi-asserted-by":"publisher","first-page":"513","DOI":"10.1007\/BF01457454","volume":"261","author":"A.K. Lenstra","year":"1982","unstructured":"Lenstra, A.K., Lenstra, J.H.W., Lovasz, L.: Factoring polynomials with rational coefficients. Mathematische Annalen\u00a0261, 513\u2013534 (1982)","journal-title":"Mathematische Annalen"},{"key":"13_CR13","doi-asserted-by":"publisher","first-page":"525","DOI":"10.1109\/TIT.1978.1055927","volume":"IT-24","author":"R.C. Merkle","year":"1978","unstructured":"Merkle, R.C., Hellman, M.E.: Hiding information and signatures in trapdoor knapsacks. IEEE Transactions on Information Theory\u00a0IT-24, 525\u2013530 (1978)","journal-title":"IEEE Transactions on Information Theory"},{"key":"13_CR14","doi-asserted-by":"crossref","unstructured":"Micciancio, D.: Generalized compact knapsacks, cyclic lattices, and efficient one-way functions from worst-case complexity assumptions. In: Computational Complexity (to appear preliminary version in FOCS 2002).","DOI":"10.1109\/SFCS.2002.1181960"},{"issue":"1","key":"13_CR15","doi-asserted-by":"publisher","first-page":"118","DOI":"10.1137\/S0097539703433511","volume":"34","author":"D. Micciancio","year":"2004","unstructured":"Micciancio, D.: Almost perfect lattices, the covering radius problem, and applications to Ajtai\u2019s connection factor. SIAM J. on Computing\u00a034(1), 118\u2013169 (2004)","journal-title":"SIAM J. on Computing"},{"key":"13_CR16","doi-asserted-by":"crossref","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. Kluwer Academic Publishers, Dordrecht (2002)"},{"key":"13_CR17","doi-asserted-by":"crossref","unstructured":"Micciancio, D., Regev, O.: Worst-case to average-case reductions based on Gaussian measures. In: SIAM J. on Computing, (to appear preliminary version in FOCS 2004)","DOI":"10.1109\/FOCS.2004.72"},{"key":"13_CR18","doi-asserted-by":"crossref","unstructured":"Peikert, C., Rosen, A.: Efficient Collision-Resistant Hashing from Worst-Case Assumptions on Cyclic Lattices. In: TCC (2006)","DOI":"10.1007\/11681878_8"},{"key":"13_CR19","series-title":"Algorithms and Computation in Mathematics","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-03980-5","volume-title":"Polynomials","author":"V.V. Prasolov","year":"2004","unstructured":"Prasolov, V.V.: Polynomials. Algorithms and Computation in Mathematics, vol.\u00a011. Springer, Heidelberg (2004)"},{"key":"13_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 basis reduction algorithms. Theoretical Computer Science\u00a053, 201\u2013224 (1987)","journal-title":"Theoretical Computer Science"},{"issue":"5","key":"13_CR21","doi-asserted-by":"publisher","first-page":"699","DOI":"10.1109\/TIT.1984.1056964","volume":"IT-30","author":"A. Shamir","year":"1984","unstructured":"Shamir, A.: A polynomial time algorithm for breaking the basic Merkle-Hellman cryptosystem. IEEE Transactions on Information Theory\u00a0IT-30(5), 699\u2013704 (1984)","journal-title":"IEEE Transactions on Information Theory"},{"issue":"2","key":"13_CR22","doi-asserted-by":"publisher","first-page":"87","DOI":"10.1007\/s001450010005","volume":"14","author":"S. Vaudenay","year":"2001","unstructured":"Vaudenay, S.: Cryptanalysis of the Chor\u2013Rivest cryptosystem. Journal of Cryptology\u00a014(2), 87\u2013100 (2001)","journal-title":"Journal of Cryptology"},{"key":"13_CR23","doi-asserted-by":"crossref","unstructured":"Wang, X., Lai, X., Feng, D., Chen, H., Yu, X.: Cryptanalysis for Hash Functions MD4 and RIPEMD. In: EUROCRYPT (2005)","DOI":"10.1007\/11426639_1"},{"key":"13_CR24","doi-asserted-by":"crossref","unstructured":"Wang, X., Yu, H.: How to Break MD5 and Other Hash Functions. In: EUROCRYPT (2005)","DOI":"10.1007\/11426639_2"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11787006_13.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T03:20:01Z","timestamp":1619493601000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11787006_13"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006]]},"ISBN":["9783540359074","9783540359081"],"references-count":24,"URL":"https:\/\/doi.org\/10.1007\/11787006_13","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2006]]}}}