Home | Quick Search | Advanced Search | Bibliography submission | Bibliography submission using bibtex | Bibliography submission using bibtex file | Links | Help | Internal


TitleA variant of the F4 algorithm.
Author(s) Antoine Joux, Vanessa Vitse
TypeBook, Chapter in Book, Conference Proceeding
AbstractAlgebraic cryptanalysis usually requires to find solutions of several similar polynomial systems. A standard tool to solve this problem consists of computing the Gröbner bases of the corresponding ideals, and Faugère’s F4 and F5 are two well-known algorithms for this task. In this paper, we adapt the “Gröbner trace” method of Traverso to the context of F4. The resulting variant is a heuristic algorithm, well suited to algebraic attacks of cryptosystems since it is designed to compute with high probability Gröbner bases of a set of polynomial systems having the same shape. It is faster than F4 as it avoids all reductions to zero, but preserves its simplicity and its efficiency, thus competing with F5.
KeywordsGröbner basis, Gröbner trace, F4, F5, multivariate cryptography, algebraic cryptanalysis
URL http://link.springer.com/chapter/10.1007%2F978-3-642-19074-2_23
PublisherBerlin: Springer
Translation No
Refereed No