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

Details:

   
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
ISBN978-3-642-19073-5/pbk
URL http://link.springer.com/chapter/10.1007%2F978-3-642-19074-2_23
LanguageEnglish
Pages356--375
PublisherBerlin: Springer
Year2011
Edition0
Translation No
Refereed No
Webmaster