New Subexponential Algorithms for Factoring in SL(2;F2n)
(2011) , 21 pages
Files
No attached file found for this publication.
Details
- Authors
- Abstract
- Cayley hash functions are a particular kind of cryptographic hash functions with very appealing properties. Unfortunately, their security is related to a mathematical problem whose hardness is not very well understood, the factorization problem in finite groups. Given a group G, a set of generators S for this group and an element g 2 G, the factorization problem asks for a “short” representation of g as a product of the generators. In this paper, we provide a new algorithm for solving this problem for the group G := SL(2;F2n ). We first reduce the problem to the resolution of a particular kind of multivariate equation over F2n . Then, we introduce a dedicated approach to solve this equation with Gröbner bases. We provide a complexity analysis of our approach that is of independent interest from the point of view of Gröbner basis algorithms. Finally, we give the first subexponential time algorithm computing polynomial length factorizations of any element g with respect to any generator set S of SL(2;F2n ). Previous algorithms only worked for specific generator sets, ran in exponential time or produced factorizations that had at least a subexponential length. In practice, our algorithm beats the birthday-bound complexity of previous attacks for medium and large values of n.
- Affiliations
Citations
Faugère, J.-C., Perret, L., Petit, C., & Renault, G. (2011). New Subexponential Algorithms for Factoring in SL(2;F2n). https://hdl.handle.net/2078.5/252899