Paper 2011/598

New Subexponential Algorithms for Factoring in $SL(2,\fq)$

Jean-Charles Faugère, Ludovic Perret, Christophe Petit, and Guénaël Renault

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 $\gen$ for this group and an element $g\in 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:=\G$. We first reduce the problem to the resolution of a particular kind of multivariate equation over $\fq$. 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 $\gen$ of $\G$. 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$.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Published elsewhere. Unknown where it was published
Contact author(s)
christophe petit @ uclouvain be
History
2011-11-10: last of 2 revisions
2011-11-10: received
See all versions
Short URL
https://ia.cr/2011/598
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2011/598,
      author = {Jean-Charles Faugère and Ludovic Perret and Christophe Petit and Guénaël Renault},
      title = {New Subexponential Algorithms for Factoring in $SL(2,\fq)$},
      howpublished = {Cryptology ePrint Archive, Paper 2011/598},
      year = {2011},
      note = {\url{https://eprint.iacr.org/2011/598}},
      url = {https://eprint.iacr.org/2011/598}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.