Details:
Title  A variant of the F4 algorithm.  Author(s)  Antoine Joux, Vanessa Vitse  Type  Book, Chapter in Book, Conference Proceeding  Abstract  Algebraic 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 wellknown 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.  Keywords  Gröbner basis, Gröbner trace, F4, F5, multivariate cryptography, algebraic cryptanalysis  ISBN  9783642190735/pbk 
URL 
http://link.springer.com/chapter/10.1007%2F9783642190742_23 
Language  English  Pages  356375  Publisher  Berlin: Springer  Year  2011  Edition  0  Translation 
No  Refereed 
No 
