Petit, Christophe
[UCL]
The security of many cryptographic protocols relies on the hardness of some computational problems. Besides discrete logarithm or integer factorization, other problems are regularly proposed as potential hard problems. The factorization problem in finite groups is one of them. Given a finite group G, a set of generators S for this group and an element g ∈ G, the factorization problem asks for a “short” representation of g as a product of the generators. The problem is related to a famous conjecture of Babai on the diameter of Cayley graphs. It is also motivated by the preimage security of Cayley hash functions, a particular kind of cryptographic hash functions. The problem has been solved for a few particular generator sets, but essentially nothing is known for generic generator sets. In this paper, we make significant steps towards a solution of the factorization problem in the group G := SL(2, F2n ), a particularly interesting group for cryptographic applications. To avoid considering all generator sets separately, we first give a new reduction tool that allows focusing on some generator sets with a “nice” special structure. We then identify classes of trapdoor matrices for these special generator sets, such that the factorization of a single one of these matrices would allow efficiently factoring any element in the group. Finally, we provide a heuristic subexponential time algorithm that can compute subexponential length factorizations of any element for any pair of generators of SL(2, F2n ). Our results do not yet completely remove the factorization problem in SL(2, F2n ) from the list of potential hard problems useful for cryptography. However, we believe that each one of our individual results is a significant step towards a polynomial time algorithm for factoring in SL(2, F2n ).
- 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).
- 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).
- Babai L.: On the diameter of Eulerian orientations of graphs. In: SODA, pp. 822–831. ACM Press, New York (2006).
- Babai László, Seress Ákos, On the diameter of permutation groups, 10.1016/s0195-6698(05)80029-0
- 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).
- Breuillard Emmanuel, Green Ben, Tao Terence, Approximate Subgroups of Linear Groups, 10.1007/s00039-011-0122-y
- 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).
- 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).
- Charles Denis X., Lauter Kristin E., Goren Eyal Z., Cryptographic Hash Functions from Expander Graphs, 10.1007/s00145-007-9002-x
- 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).
- Coppersmith D., Fast evaluation of logarithms in fields of characteristic two, 10.1109/tit.1984.1056941
- 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).
- Grassl Markus, Ilić Ivana, Magliveras Spyros, Steinwandt Rainer, Cryptanalysis of the Tillich–Zémor Hash Function, 10.1007/s00145-010-9063-0
- Helfgott Harald, Growth and generation in SL2(ℤ∕pℤ), 10.4007/annals.2008.167.601
- Helfgott H.A.: Growth and generation in SL 3(Z/pZ). J. Eur. Math. Soc. 13(3), 761–851 (2011).
- Hoory Shlomo, Linial Nathan, Wigderson Avi, Expander graphs and their applications, 10.1090/s0273-0979-06-01126-8
- Joux, A., Lercier,R.: Discrete logarithms in GF(2607) and GF(2613). Email on the NMBRTHRY mailing list (2005)
- Joux Antoine, Stern Jacques, Lattice Reduction: A Toolbox for the Cryptanalyst, 10.1007/s001459900042
- Kantor William M., Some large trivalent graphs having small diameters, 10.1016/0166-218x(92)90145-z
- Kassabov M., Riley T.R.: Diameters of Cayley graphs of Chevalley groups. Eur. J. Comb. 28(3), 791–800 (2007).
- Larsen M.: Navigating the Cayley graph of $${SL_2(\mathbb{F}_p)}$$ . Int. Math. Res. Not. 27, 1465–1471 (2003).
- Lauder A.: Continued fractions of Laurent series with partial quotients from a given set. Acta Arith. XC 3, 252–271 (1999)
- Lenstra A.K., Lenstra Jr H.W., Lovász L.: Factoring polynomials with rational coefficients. Math. Ann. 261(5), 515–534 (1982).
- Liebeck Martin W., Shalev Aner, The probability of generating a finite simple group, 10.1007/bf01263616
- Lubotzky A.: Discrete groups, expanding graphs and invariant measures. Birkhaüser Verlag, Basel (1994).
- Lynch Nancy A., Straight-line program length as a parameter for complexity analysis, 10.1016/0022-0000(80)90024-0
- 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).
- Menezes Alfred, van Oorschot Paul, Vanstone Scott, Handbook of Applied Cryptography, ISBN:9780849385230, 10.1201/9781439821916
- 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
- Odlyzko A.M.: The rise and fall of knapsack cryptosystems. In: Cryptology and Computational Number Theory, pp. 75–88. American Mathematical Society, Providence (1990).
- 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),
- Petit C., Lauter K.E., Quisquater J.-J.: Cayley hashes: a class of efficient graph-based hash functions. http://perso.uclouvain.be/christophe.petit/files/Cayley.pdf (2007). Accessed 28 Aug 2012.
- 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).
- Petit C.: On graph-based cryptographic hash functions. PhD Thesis, Université catholique de Louvain. http://perso.uclouvain.be/christophe.petit/files/thesis.pdf (2009). Accessed 28 Aug 2012.
- 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
- Petit C., Quisquater J.-J.: Rubik’s for cryptographers. http://eprint.iacr.org/2011/638.pdf (2010b). Accessed 28 Aug 2012.
- 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).
- Pyber L., Szabó E.: Growth in finite simple groups of Lie type. http://arxiv.org/abs/1001.4556 (Jan 2010).
- Quisquater J.-J., Delescaille J.-P.: How easy is collision search? application to DES (extended summary). In: EUROCRYPT, pp. 429–434 (1989).
- Regev O.: Lattice-based cryptography. In: Dwork C. (ed.) CRYPTO. Lecture Notes in Computer Science, vol. 4117, pp. 131–141. Springer, Heidelberg (2006).
- 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
- Rivest R. L., Shamir A., Adleman L., A method for obtaining digital signatures and public-key cryptosystems, 10.1145/357980.358017
- 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).
- 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).
- 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).
- 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).
- Wagner D.: A generalized birthday problem. In: Yung M. (ed.) CRYPTO. Lecture Notes in Computer Science, vol. 2442, pp. 288–303. Springer, Berlin (2002).
- 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).
- Z�mor Gilles, Hash functions and Cayley graphs, 10.1007/bf01388652
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 |
http://hdl.handle.net/2078.1/120244 |