Abstract
We analyse the hash function family based on walks in LPS Ramanujan graphs recently introduced by Charles et al. We present an algorithm for finding collisions that runs in quasi-linear time in the length of the hashed value. A concrete instance of the hash function is considered, based on a 100-digit prime. A short collision is given, together with implementation details.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Abdukhalikov, K.S., Kim, C.: On the security of the hashing scheme based on SL2. In: Vaudenay, S. (ed.) FSE 1998. LNCS, vol. 1372, pp. 93–102. Springer, Heidelberg (1998)
Charles, D.X., Goren, E.Z., Lauter, K.E.: Cryptographic hash functions from expander graphs. In: Second NIST cryptographic hash workshop, Santa Barbara, USA (August 2006)
Charles, D.X., Goren, E.Z., Lauter, K.E.: Cryptographic hash functions from expander graphs. Journal of Cryptology, to appear in print, published online (September 15, 2007) http://www.springerlink.com/content/cv4r187833614475/
Charnes, C., Pieprzyk, J.: Attacking the SL2 hashing scheme. In: Safavi-Naini, R., Pieprzyk, J.P. (eds.) ASIACRYPT 1994. LNCS, vol. 917, pp. 322–330. Springer, Heidelberg (1995)
Davidoff, G., Sarnak, P., Valette, A.: Elementary Number Theory, Group Theory, and Ramanujan Graphs. Cambridge University Press, Cambridge (2003)
Geiselmann, W.: A note on the hash function of Tillich and Zémor. In: Gollmann, D. (ed.) FSE 1996. LNCS, vol. 1039, pp. 51–52. Springer, Heidelberg (1996)
Grosswald, E.: Representation of integers as sum of squares. Springer, Heidelberg (1985)
Helfgott, H.A.: Growth and generation in SL2(Z/pZ), to appear in Annals of Math. (2005), http://arxiv.org/abs/math/0509024
Hoory, S., Linial, N., Wigderson, A.: Expander graphs and their applications. Bull. AMS 43, 439–561 (2006)
Lauter, K.E., Charles, D.X., Goren, E.Z.: Hash function constructions from expander graphs, United States Patent 20070098150 (May 2007), http://www.freepatentsonline.com/20070098150.html
Lubotzky, A., Phillips, R., Sarnak, P.: Ramanujan graphs. Combinatorica 8(3), 261–277 (1988)
Quisquater, J., Joye, M.: Authentication of sequences with the SL2 hash function: Application to video sequences. Journal of Computer Security 5(3), 213–223 (1997)
Sarnak, P.: Some applications of modular forms. Cambridge U. Press, Cambridge (1990)
Steinwandt, R., Grassl, M., Geiselmann, W., Beth, T.: Weaknesses in the SL2 hashing scheme. In: Bellare, M. (ed.) CRYPTO 2000. LNCS, vol. 1880, pp. 287–299. Springer, Heidelberg (2000)
Shpilrain, V.: Hashing with polynomials. In: Rhee, M.S., Lee, B. (eds.) ICISC 2006. LNCS, vol. 4296, pp. 22–28. Springer, Heidelberg (2006)
Tillich, J.-P., Zémor, G.: Group-theoretic hash functions. In: Cohen, G., Lobstein, A., Zémor, G., Litsyn, S.N. (eds.) Algebraic Coding 1993. LNCS, vol. 781, pp. 90–110. Springer, Heidelberg (1994)
Tillich, J.-P., Zémor, G.: Hashing with SL2. In: Desmedt, Y.G. (ed.) CRYPTO 1994. LNCS, vol. 839, pp. 40–49. Springer, Heidelberg (1994)
Zémor, G.: Hash functions and graphs with large girth. In: Davies, D.W. (ed.) EUROCRYPT 1991. LNCS, vol. 547, Springer, Heidelberg (1991)
Zémor, G.: Hash functions and Cayley graphs. Designs, Codes and Cryptography 4, 381–394 (1994)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2008 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Tillich, JP., Zémor, G. (2008). Collisions for the LPS Expander Graph Hash Function. In: Smart, N. (eds) Advances in Cryptology – EUROCRYPT 2008. EUROCRYPT 2008. Lecture Notes in Computer Science, vol 4965. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-78967-3_15
Download citation
DOI: https://doi.org/10.1007/978-3-540-78967-3_15
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-78966-6
Online ISBN: 978-3-540-78967-3
eBook Packages: Computer ScienceComputer Science (R0)