{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,23]],"date-time":"2026-08-23T15:54:31Z","timestamp":1787500471001,"version":"build-2736575974"},"publisher-location":"Berlin, Heidelberg","reference-count":37,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783662493007","type":"print"},{"value":"9783662493014","type":"electronic"}],"license":[{"start":{"date-parts":[[2016,1,1]],"date-time":"2016-01-01T00:00:00Z","timestamp":1451606400000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2016]]},"DOI":"10.1007\/978-3-662-49301-4_19","type":"book-chapter","created":{"date-parts":[[2016,3,18]],"date-time":"2016-03-18T11:15:43Z","timestamp":1458299743000},"page":"304-311","source":"Crossref","is-referenced-by-count":5,"title":["Cryptographic Hash Functions and Expander Graphs: The End of the Story?"],"prefix":"10.1007","author":[{"given":"Christophe","family":"Petit","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jean-Jacques","family":"Quisquater","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2016,3,18]]},"reference":[{"key":"19_CR1","doi-asserted-by":"publisher","first-page":"507","DOI":"10.1016\/S0195-6698(89)80067-8","volume":"10","author":"L Babai","year":"1989","unstructured":"Babai, L., Kantor, W.M., Lubotzky, A.: Small-diameter Cayley graphs for finite simple groups. European J. Combin. 10, 507\u2013552 (1989)","journal-title":"European J. Combin."},{"issue":"4","key":"19_CR2","doi-asserted-by":"publisher","first-page":"231","DOI":"10.1016\/S0195-6698(05)80029-0","volume":"13","author":"L Babai","year":"1992","unstructured":"Babai, L., Seress, \u00c1.: On the diameter of permutation groups. European J. Combin. 13(4), 231\u2013243 (1992)","journal-title":"European J. Combin."},{"key":"19_CR3","unstructured":"Babai, L., Hayes, T.P.: Near-independence of permutations and an almost sure polynomial bound on the diameter of the symmetric group. In: SODA, pp. 1057\u20131066. SIAM (2005)"},{"key":"19_CR4","doi-asserted-by":"crossref","unstructured":"Babai, L., Hetyei, G., Kantor, W.M., Lubotzky, A., Seress, \u00c1.: On the diameter of finite groups. In: FOCS, vol. II, pp. 857\u2013865. IEEE (1990)","DOI":"10.1109\/FSCS.1990.89608"},{"issue":"2","key":"19_CR5","doi-asserted-by":"publisher","first-page":"625","DOI":"10.4007\/annals.2008.167.625","volume":"167","author":"J Bourgain","year":"2008","unstructured":"Bourgain, J., Gamburd, A.: Uniform expansion bounds for cayley graphs of $$sl_2(\\mathbb{F}_p)$$ . Ann. Math. 167(2), 625\u2013642 (2008)","journal-title":"Ann. Math."},{"key":"19_CR6","doi-asserted-by":"crossref","unstructured":"Breuillard, E., Green, B., Tao, T.,Approximate subgroups of linear groups. arXiv:1005.1881v1 , May 2010","DOI":"10.3934\/era.2010.17.57"},{"issue":"1","key":"19_CR7","doi-asserted-by":"publisher","first-page":"93","DOI":"10.1007\/s00145-007-9002-x","volume":"22","author":"DX Charles","year":"2009","unstructured":"Charles, D.X., Lauter, K.E., Goren, E.Z.: Cryptographic hash functions from expander graphs. J. Cryptology 22(1), 93\u2013113 (2009)","journal-title":"J. Cryptology"},{"key":"19_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"203","DOI":"10.1007\/3-540-39118-5_19","volume-title":"Advances in Cryptology - EUROCRYPT 1987","author":"IB Damg\u00e5rd","year":"1988","unstructured":"Damg\u00e5rd, I.B.: Collision free hash functions and public key signature schemes. In: Price, W.L., Chaum, D. (eds.) EUROCRYPT 1987. LNCS, vol. 304, pp. 203\u2013216. Springer, Heidelberg (1988)"},{"key":"19_CR9","unstructured":"de Meulenaer, G., Petit, C., Quisquater, J.-J.: Hardware implementations of a variant of the Zmor-Tillich hash function: can a provably secure hash function be very efficient ? Cryptology ePrint Archive, Report \/229 (2009). http:\/\/eprint.iacr.org\/"},{"key":"19_CR10","doi-asserted-by":"publisher","first-page":"3137","DOI":"10.1090\/S0002-9939-06-08384-5","volume":"134","author":"O Dinai","year":"2006","unstructured":"Dinai, O.: Poly-log diameter bounds for some families of finite groups. Proc. Amer. Math. Soc. 134, 3137\u20133142 (2006)","journal-title":"Proc. Amer. Math. Soc."},{"issue":"3","key":"19_CR11","doi-asserted-by":"publisher","first-page":"311","DOI":"10.1016\/0196-6774(81)90029-8","volume":"2","author":"S Even","year":"1981","unstructured":"Even, S., Goldreich, O.: The minimum-length generator sequence problem is NP-hard. J. Algorithms 2(3), 311\u2013313 (1981)","journal-title":"J. Algorithms"},{"key":"19_CR12","doi-asserted-by":"crossref","unstructured":"Goldwasser, S., Micali, S., Rivest, R.L.: A \u201cparadoxical\u201d solution to the signature problem (extended abstract). In: FOCS, pp. 441\u2013448. IEEE (1984)","DOI":"10.1109\/SFCS.1984.715946"},{"issue":"1","key":"19_CR13","doi-asserted-by":"publisher","first-page":"148","DOI":"10.1007\/s00145-010-9063-0","volume":"24","author":"M Grassl","year":"2011","unstructured":"Grassl, M., Ilic, I., Magliveras, S.S., Steinwandt, R.: Cryptanalysis of the Tillich-Z\u00e9mor hash function. J. Cryptology 24(1), 148\u2013156 (2011)","journal-title":"J. Cryptology"},{"key":"19_CR14","unstructured":"Helfgott, H., Seress, A.: On the diameter of permutation groups (2011). http:\/\/arxiv.org\/abs\/1109.3550"},{"issue":"2","key":"19_CR15","doi-asserted-by":"publisher","first-page":"601","DOI":"10.4007\/annals.2008.167.601","volume":"167","author":"HA Helfgott","year":"2008","unstructured":"Helfgott, H.A.: Growth, generation in $$SL_2(Z, pZ)$$ . Ann. Math. 167(2), 601\u2013623 (2008)","journal-title":"Ann. Math."},{"key":"19_CR16","doi-asserted-by":"publisher","first-page":"439","DOI":"10.1090\/S0273-0979-06-01126-8","volume":"43","author":"S Hoory","year":"2006","unstructured":"Hoory, S., Linial, N., Wigderson, A.: Expander graphs and their applications. Bull. Amer. Math. Soc. 43, 439\u2013561 (2006)","journal-title":"Bull. Amer. Math. Soc."},{"issue":"2\u20133","key":"19_CR17","doi-asserted-by":"publisher","first-page":"265","DOI":"10.1016\/0304-3975(85)90047-7","volume":"36","author":"MR Jerrum","year":"1985","unstructured":"Jerrum, M.R.: The complexity of finding minimum-length generator sequences. Theor. Comput. Sci. 36(2\u20133), 265\u2013289 (1985)","journal-title":"Theor. Comput. Sci."},{"issue":"38","key":"19_CR18","doi-asserted-by":"publisher","first-page":"353","DOI":"10.1016\/0166-218X(92)90145-Z","volume":"37","author":"WM Kantor","year":"1992","unstructured":"Kantor, W.M.: Some large trivalent graphs having small diameters. Discrete Appl. Math. 37(38), 353\u2013357 (1992)","journal-title":"Discrete Appl. Math."},{"issue":"3","key":"19_CR19","doi-asserted-by":"publisher","first-page":"791","DOI":"10.1016\/j.ejc.2005.12.005","volume":"28","author":"M Kassabov","year":"2007","unstructured":"Kassabov, M., Riley, T.R.: Diameters of Cayley graphs of Chevalley groups. Eur. J. Comb. 28(3), 791\u2013800 (2007)","journal-title":"Eur. J. Comb."},{"key":"19_CR20","doi-asserted-by":"crossref","unstructured":"Landau, Z., Russell, A.: Random cayley graphs are expanders: a simple proof of the alon-roichman theorem. Electr. J. Comb. 11(1) (2004)","DOI":"10.37236\/1815"},{"key":"19_CR21","doi-asserted-by":"publisher","first-page":"1465","DOI":"10.1155\/S1073792803130383","volume":"27","author":"M Larsen","year":"2003","unstructured":"Larsen, M.: Navigating the Cayley graph of $$SL_2(\\mathbb{F}_p)$$ . Int. Math. Res. Not. IMRN 27, 1465\u20131471 (2003)","journal-title":"Int. Math. Res. Not. IMRN"},{"key":"19_CR22","doi-asserted-by":"publisher","first-page":"261","DOI":"10.1007\/BF02126799","volume":"8","author":"A Lubotzky","year":"1988","unstructured":"Lubotzky, A., Phillips, R., Sarnak, P.: Ramanujan graphs. Combinatorica 8, 261\u2013277 (1988)","journal-title":"Combinatorica"},{"key":"19_CR23","doi-asserted-by":"publisher","first-page":"113","DOI":"10.1090\/S0273-0979-2011-01359-3","volume":"49","author":"A Lubotzky","year":"2012","unstructured":"Lubotzky, A.: Expander graphs in pure and applied mathematics. Bull. Amer. Math. Soc. 49, 113\u2013162 (2012)","journal-title":"Bull. Amer. Math. Soc."},{"issue":"3","key":"19_CR24","doi-asserted-by":"publisher","first-page":"409","DOI":"10.1007\/s10623-012-9743-x","volume":"71","author":"Christophe Petit","year":"2012","unstructured":"Petit, C.: Towards factoring in $$SL(2,\\mathbb{F}_{2^n})$$ . Design, Codes and Cryptography, September 2012. doi: 10.1007\/s10623-012-9743-x","journal-title":"Designs, Codes and Cryptography"},{"key":"19_CR25","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"263","DOI":"10.1007\/978-3-540-85855-3_18","volume-title":"Security and Cryptography for Networks","author":"C Petit","year":"2008","unstructured":"Petit, C., Lauter, K., Quisquater, J.-J.: Full cryptanalysis of LPS and Morgenstern hash functions. In: Ostrovsky, R., De Prisco, R., Visconti, I. (eds.) SCN 2008. LNCS, vol. 5229, pp. 263\u2013277. Springer, Heidelberg (2008)"},{"key":"19_CR26","unstructured":"Petit, C., Lauter, K.E., Quisquater, J.-J.: Cayley hashes: a class of efficient graph-based hash functions (2007). http:\/\/perso.uclouvain.be\/christophe.petit\/index.html"},{"key":"19_CR27","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"282","DOI":"10.1007\/978-3-642-19574-7_20","volume-title":"Selected Areas in Cryptography","author":"C Petit","year":"2011","unstructured":"Petit, C., Quisquater, J.-J.: Preimages for the Tillich-Z\u00e9mor hash function. In: Biryukov, A., Gong, G., Stinson, D.R. (eds.) SAC 2010. LNCS, vol. 6544, pp. 282\u2013301. Springer, Heidelberg (2011)"},{"key":"19_CR28","doi-asserted-by":"publisher","first-page":"733","DOI":"10.1090\/noti1001","volume":"60","author":"C Petit","year":"2013","unstructured":"Petit, C., Quisquater, J.-J.: Rubik\u2019s for cryptographers. Not. Am. Math. Soc. 60, 733\u2013739 (2013)","journal-title":"Not. Am. Math. Soc."},{"key":"19_CR29","unstructured":"Pyber, L., Szab, E.: Growth in finite simple groups of Lie type. arXiv:1001.4556v1 , January 2010"},{"issue":"1","key":"19_CR30","doi-asserted-by":"publisher","first-page":"215","DOI":"10.1007\/s10711-005-5230-0","volume":"113","author":"TR Riley","year":"2005","unstructured":"Riley, T.R.: Navigating in the Cayley graphs of $$SL_N(\\mathbb{Z})$$ and $$SL_N(\\mathbb{F}_p)$$ . Geom. Dedicata 113(1), 215\u2013229 (2005)","journal-title":"Geom. Dedicata"},{"key":"19_CR31","unstructured":"Mullan, C., Blackburn, S.R., Cid, C.: Group theory in cryptography (2010). http:\/\/arxiv.org\/abs\/0906.5545"},{"key":"19_CR32","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"287","DOI":"10.1007\/3-540-44598-6_18","volume-title":"Advances in Cryptology - CRYPTO 2000","author":"R Steinwandt","year":"2000","unstructured":"Steinwandt, R., Grassl, M., Geiselmann, W., Beth, T.: Weaknesses in the $$SL_2(\\mathbb{F}_{2^{n}})$$ hashing scheme. In: Bellare, M. (ed.) CRYPTO 2000. LNCS, vol. 1880, pp. 287\u2013299. Springer, Heidelberg (2000)"},{"key":"19_CR33","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"90","DOI":"10.1007\/3-540-57843-9_12","volume-title":"Algebraic Coding","author":"J-P Tillich","year":"1994","unstructured":"Tillich, J.-P., Z\u00e9mor, G.: Group-theoretic hash functions. In: Cohen, G., Lobstein, A., Z\u00e9mor, G., Litsyn, S.N. (eds.) Algebraic Coding 1993. LNCS, vol. 781, pp. 90\u2013110. Springer, London (1994)"},{"key":"19_CR34","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"40","DOI":"10.1007\/3-540-48658-5_5","volume-title":"Advances in Cryptology - CRYPTO \u201994","author":"J-P Tillich","year":"1994","unstructured":"Tillich, J.-P., Z\u00e9mor, G.: Hashing with $$SL_2$$ . In: Desmedt, Y.G. (ed.) CRYPTO 1994. LNCS, vol. 839, pp. 40\u201349. Springer, Heidelberg (1994)"},{"key":"19_CR35","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"254","DOI":"10.1007\/978-3-540-78967-3_15","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2008","author":"J-P Tillich","year":"2008","unstructured":"Tillich, J.-P., Z\u00e9mor, G.: Collisions for the LPS expander graph hash function. In: Smart, N.P. (ed.) EUROCRYPT 2008. LNCS, vol. 4965, pp. 254\u2013269. Springer, Heidelberg (2008)"},{"issue":"3","key":"19_CR36","doi-asserted-by":"publisher","first-page":"553","DOI":"10.1109\/18.54902","volume":"36","author":"MJ Wiener","year":"1990","unstructured":"Wiener, M.J.: Cryptanalysis of short RSA secret exponents. IEEE Trans. Inf. Theory 36(3), 553\u2013558 (1990)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"19_CR37","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"508","DOI":"10.1007\/3-540-46416-6_44","volume-title":"Advances in Cryptology - EUROCRYPT 1991","author":"G Z\u00e9mor","year":"1991","unstructured":"Z\u00e9mor, G.: Hash functions and graphs with large Girths. In: Davies, D.W. (ed.) EUROCRYPT 1991. LNCS, vol. 547, pp. 508\u2013511. Springer, Heidelberg (1991)"}],"container-title":["Lecture Notes in Computer Science","The New Codebreakers"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-49301-4_19","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,1]],"date-time":"2025-06-01T16:58:35Z","timestamp":1748797115000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-662-49301-4_19"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016]]},"ISBN":["9783662493007","9783662493014"],"references-count":37,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-49301-4_19","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016]]}}}