International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

A variant of the F4 algorithm

Authors:
Antoine Joux
Vanessa Vitse
Download:
URL: http://eprint.iacr.org/2010/158
Search ePrint
Search Google
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 well-known algorithms for this task. In this paper, we present a new variant of the F4 algorithm which is well suited to algebraic attacks of cryptosystems since it is designed to compute 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 computation efficiency, thus competing with F5.
BibTeX
@misc{eprint-2010-23059,
  title={A variant of the F4 algorithm},
  booktitle={IACR Eprint archive},
  keywords={Gröbner basis, F4, F5, multivariate cryptography, algebraic cryptanalysis},
  url={http://eprint.iacr.org/2010/158},
  note={ vanessa.vitse@prism.uvsq.fr 14692 received 24 Mar 2010},
  author={Antoine Joux and Vanessa Vitse},
  year=2010
}