User menu

Towards factoring in SL(2, F2n)

Bibliographic reference Petit, Christophe. Towards factoring in SL(2, F2n). In: Designs, Codes and Cryptography, Vol. 71, no. 3, p. 409-471 (June 2014)
Permanent URL
  1. Abdukhalikov K.S., Kim C.: On the security of the hashing scheme based on SL2. In: FSE ’98: Proceedings of the 5th International Workshop on Fast Software Encryption, pp. 93–102. Springer, London (1998).
  2. Adleman L.M.: The function field sieve. In: Adleman L.M., Huang M.-D.A. (eds.) ANTS. Lecture Notes in Computer Science, vol. 877, pp. 108–121. Springer, Berlin (1994).
  3. Babai L.: On the diameter of Eulerian orientations of graphs. In: SODA, pp. 822–831. ACM Press, New York (2006).
  4. Babai László, Seress Ákos, On the diameter of permutation groups, 10.1016/s0195-6698(05)80029-0
  5. Babai L., Hetyei G., Kantor W.M., Lubotzky A., Seress Á.: On the diameter of finite groups. In: FOCS, vol. II, pp. 857–865. IEEE, Los Alamitos (1990).
  6. Breuillard Emmanuel, Green Ben, Tao Terence, Approximate Subgroups of Linear Groups, 10.1007/s00039-011-0122-y
  7. Cathalo J., Petit C.: One-time trapdoor one-way functions. In: Burmester M., Tsudik G., Magliveras S.S., Ilic I. (eds.) ISC. Lecture Notes in Computer Science, vol. 6531, pp. 283–298. Springer, Berlin (2010).
  8. Celler F., Leedham-Green C.: A non-constructive recognition algorithm for the special linear and other classical groups. In: Groups and Computation II, pp. 61–67. American Mathematical Society, Providence (1997).
  9. Charles Denis X., Lauter Kristin E., Goren Eyal Z., Cryptographic Hash Functions from Expander Graphs, 10.1007/s00145-007-9002-x
  10. Charnes C., Pieprzyk J.: Attacking the SL 2 hashing scheme. In: ASIACRYPT ’94: Proceedings of the 4th International Conference on the Theory and Applications of Cryptology, pp. 322–330. Springer, London (1995).
  11. Coppersmith D., Fast evaluation of logarithms in fields of characteristic two, 10.1109/tit.1984.1056941
  12. Geiselmann W.: A note on the hash function of Tillich and Zémor. In: Gollmann D. (ed.) Fast Software Encryption. Lecture Notes in Computer Science, vol. 1039, pp. 51–52. Springer, Cambridge (1996).
  13. Grassl Markus, Ilić Ivana, Magliveras Spyros, Steinwandt Rainer, Cryptanalysis of the Tillich–Zémor Hash Function, 10.1007/s00145-010-9063-0
  14. Helfgott Harald, Growth and generation in SL2(ℤ∕pℤ), 10.4007/annals.2008.167.601
  15. Helfgott H.A.: Growth and generation in SL 3(Z/pZ). J. Eur. Math. Soc. 13(3), 761–851 (2011).
  16. Hoory Shlomo, Linial Nathan, Wigderson Avi, Expander graphs and their applications, 10.1090/s0273-0979-06-01126-8
  17. Joux, A., Lercier,R.: Discrete logarithms in GF(2607) and GF(2613). Email on the NMBRTHRY mailing list (2005)
  18. Joux Antoine, Stern Jacques, Lattice Reduction: A Toolbox for the Cryptanalyst, 10.1007/s001459900042
  19. Kantor William M., Some large trivalent graphs having small diameters, 10.1016/0166-218x(92)90145-z
  20. Kassabov M., Riley T.R.: Diameters of Cayley graphs of Chevalley groups. Eur. J. Comb. 28(3), 791–800 (2007).
  21. Larsen M.: Navigating the Cayley graph of $${SL_2(\mathbb{F}_p)}$$ . Int. Math. Res. Not. 27, 1465–1471 (2003).
  22. Lauder A.: Continued fractions of Laurent series with partial quotients from a given set. Acta Arith. XC 3, 252–271 (1999)
  23. Lenstra A.K., Lenstra Jr H.W., Lovász L.: Factoring polynomials with rational coefficients. Math. Ann. 261(5), 515–534 (1982).
  24. Liebeck Martin W., Shalev Aner, The probability of generating a finite simple group, 10.1007/bf01263616
  25. Lubotzky A.: Discrete groups, expanding graphs and invariant measures. Birkhaüser Verlag, Basel (1994).
  26. Lynch Nancy A., Straight-line program length as a parameter for complexity analysis, 10.1016/0022-0000(80)90024-0
  27. McEliece R.J.: A public-key cryptosystem based on algebraic coding theory. The Deep Space Network Progress Report, DSN PR 42-44, Jan and Feb, Pasadena, CA, pp. 114–116 (1978).
  28. Menezes Alfred, van Oorschot Paul, Vanstone Scott, Handbook of Applied Cryptography, ISBN:9780849385230, 10.1201/9781439821916
  29. Mesirov Jill P., Sweet Melvin M., Continued fraction expansions of rational expressions with irreducible denominators in characteristic 2, 10.1016/0022-314x(87)90058-8
  30. Odlyzko A.M.: The rise and fall of knapsack cryptosystems. In: Cryptology and Computational Number Theory, pp. 75–88. American Mathematical Society, Providence (1990).
  31. Patarin J.: Hidden fields equations (hfe) and isomorphisms of polynomials (ip): two new families of asymmetric algorithms. In: Maurer U.M. (ed.) EUROCRYPT. Lecture Notes in Computer Science, vol. 1070, pp. 33–48. Springer, Heidelberg (1996),
  32. Petit C., Lauter K.E., Quisquater J.-J.: Cayley hashes: a class of efficient graph-based hash functions. (2007). Accessed 28 Aug 2012.
  33. Petit C., Lauter K. Quisquater J.-J.: Full cryptanalysis of LPS and Morgenstern hash functions. In: Ostrovsky R., Prisco R.D., Visconti I. (eds.) SCN. Lecture Notes in Computer Science, vol. 5229, pp. 263–277. Springer, Heidelberg (2008).
  34. Petit C.: On graph-based cryptographic hash functions. PhD Thesis, Université catholique de Louvain. (2009). Accessed 28 Aug 2012.
  35. Petit Christophe, Quisquater Jean-Jacques, Preimages for the Tillich-Zémor Hash Function, Selected Areas in Cryptography (2011) ISBN:9783642195730 p.282-301, 10.1007/978-3-642-19574-7_20
  36. Petit C., Quisquater J.-J.: Rubik’s for cryptographers. (2010b). Accessed 28 Aug 2012.
  37. Petit C., Quisquater J.-J., Tillich J.-P., Zémor G.: Hard and easy components of collision search in the Zémor–Tillich hash function: new attacks and reduced variants with equivalent security. In: Fischlin M. (ed.) CT-RSA. Lecture Notes in Computer Science, vol. 5473, pp. 182–194. Springer, Berlin (2009).
  38. Pyber L., Szabó E.: Growth in finite simple groups of Lie type. (Jan 2010).
  39. Quisquater J.-J., Delescaille J.-P.: How easy is collision search? application to DES (extended summary). In: EUROCRYPT, pp. 429–434 (1989).
  40. Regev O.: Lattice-based cryptography. In: Dwork C. (ed.) CRYPTO. Lecture Notes in Computer Science, vol. 4117, pp. 131–141. Springer, Heidelberg (2006).
  41. Riley T. R., Navigating in the Cayley Graphs of $${\rm SL}_{N}(\mathbb{Z})$$ and $${\rm SL}_{N}(\mathbb{F}_{p})$$, 10.1007/s10711-005-5230-0
  42. Rivest R. L., Shamir A., Adleman L., A method for obtaining digital signatures and public-key cryptosystems, 10.1145/357980.358017
  43. Steinwandt R., Grassl M., Geiselmann W., Beth T.: Weaknesses in the $${SL_2(\mathbb{F}_{2^n})}$$ hashing scheme. In: Bellare M. (ed.) CRYPTO. Lecture Notes in Computer Science, vol. 1880, pp. 287–299. Springer, Berlin (2000).
  44. Thomé E.: Computation of discrete logarithms in $${\mathbb{F}_2^{607}}$$ . In: Boyd C. (ed.) ASIACRYPT. Lecture Notes in Computer Science, vol. 2248, pp. 107–124. Springer, Berlin (2001).
  45. Tillich J.-P., Zémor G.: Hashing with SL 2. In: Desmedt Y. (ed.) CRYPTO. Lecture Notes in Computer Science, vol. 839, pp. 40–49. Springer, Berlin (1994).
  46. Tillich J.-P., Zémor G.: Collisions for the LPS expander graph hash function. In: Smart N.P. (ed.) EUROCRYPT. Lecture Notes in Computer Science, vol. 4965, pp. 254–269. Springer, Heidelberg (2008).
  47. Wagner D.: A generalized birthday problem. In: Yung M. (ed.) CRYPTO. Lecture Notes in Computer Science, vol. 2442, pp. 288–303. Springer, Berlin (2002).
  48. Zémor G.: Hash functions and graphs with large girths. In: Davies D.W. (ed.) EUROCRYPT. Lecture Notes in Computer Science, vol. 547, pp. 508–511. Springer, Berlin (1991).
  49. Z�mor Gilles, Hash functions and Cayley graphs, 10.1007/bf01388652