Hashing with SL2

  • Jean-Pierre Tillich
  • Gilles Zémor
Conference paper
Part of the Lecture Notes in Computer Science book series (LNCS, volume 839)


We propose a new family of hash functions based on computations over a finite field of characteristic 2. These functions can be computed quickly, detect small modifications of the input text, and their security is equivalent to a precise mathematical problem. They rely on the arithmetic of the group of matrices SL 2, and improve upon previous functions based on the same strategy.


  1. 1.
    Babai, L., Kantor, W. M., Lubotsky, A: Small-diameter Cayley graphs for finite simple groups. Europ. J. of Combinatorics 10 (1989) 507–522zbMATHMathSciNetGoogle Scholar
  2. 2.
    Bosset, J: Contre les risques d’altération, un système de certifications des informations. 01 Informatique (1977)Google Scholar
  3. 3.
    Camion, P: Can a fast signature scheme without secret key be secure? In proc. AAECC (1987) Springer-Verlag Lec. N. Comp. Sci. 228 pp. 187–196Google Scholar
  4. 4.
    Dickson, L: Linear groups with an exposition of the Galois field theory. Dover New York 1958Google Scholar
  5. 5.
    Jerrum, M. R: The complexity of finding minimum length generator sequences. Theoretical Computer Science 36 (1985) 265–289zbMATHCrossRefMathSciNetGoogle Scholar
  6. 6.
    J. Lafferty, Rockmore, D: Numerical investigation of the spectrum for certain families of cayley graphs. In 1992 DIMACS Workshop on expanders graphs (1993) D. S. in Disc. Math., T. C. S. in Discrete Mathematics, and T. C. Science, Eds. pp. 63–74Google Scholar
  7. 7.
    Margulis, G. A: Explicit constructions of graphs without short cycles and low density codes. COMBINATORICA 2 (1982) 71–78zbMATHCrossRefMathSciNetGoogle Scholar
  8. 8.
    Margulis, G. A: Explicit group-theoretical constructions of combinatorial schemes and their application to the design of expanders and concentrators. Problemy Peredachi Informatsii 24 (1988) 51–60MathSciNetGoogle Scholar
  9. 9.
    Sarnack, P: Some applications of modular forms. Cambridge University Press 1990Google Scholar
  10. 10.
    Suzuki, M: Group theory, volume I. Springer-Verlag 1982Google Scholar
  11. 11.
    Tillich, J.-P., Zémor, G: Group-theoretic hash functions. In First French-Israeli workshop on algebraic coding (1994) Springer-Verlag Lec. N. Comp. Sci. 781 pp. 90–110Google Scholar
  12. 12.
    Zémor, G: Hash functions and Cayley graphs. To appear in Designs, Codes and CryptographyGoogle Scholar
  13. 13.
    Zémor, G: Hash functions and graphs with large girths. In EUROCRYPT 91 (1991) LNCS 547 Springer-Verlag pp. 508–511Google Scholar

Copyright information

© Springer-Verlag Berlin Heidelberg 1994

Authors and Affiliations

  • Jean-Pierre Tillich
    • 1
  • Gilles Zémor
    • 1
  1. 1.Network DepartmentEcole Nationale Supérieure des TélécommunicationsParis Cedex 13France

Personalised recommendations