You are looking at a specific version 20100324:154206 of this paper. See the latest version.

Paper 2010/158

A variant of the F4 algorithm

Antoine Joux and Vanessa Vitse

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.

Metadata
Available format(s)
PDF
Publication info
Published elsewhere. Unknown where it was published
Keywords
Gröbner basisF4F5multivariate cryptographyalgebraic cryptanalysis
Contact author(s)
vanessa vitse @ prism uvsq fr
History
2010-03-24: received
Short URL
https://ia.cr/2010/158
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.