A Dense Variant of the F4 Groebner Basis Algorithm

Allan Steel (December 2013)

UPDATE: Minrank Challenge C Solved Directly (August 2014)

Magma V2.20 (released December 2013) contains a new dense variant of the Faugere F4 algorithm for computing Groebner bases, which I developed in 2013. This page briefly outlines some basic information and timing results for this algorithm.

The dense variant of the F4 algorithm is currently only practically applicable to input systems over a finite field where the input polynomials are considered "dense"; that is, if the input polynomials are written as a matrix with columns labelled by the monomials, then the input matrix should be dense. Equivalently: if the field size is q and the set of all monomials occurring in the input has size m, then the number of monomials in each input polynomial should be reasonably close to (1-1/q)*m.

Dense input systems which are applicable include various cryptographic inputs such as HFE, MQQ and Minrank systems (as seen below), but systems which do not involve the solving of simultaneous equations are also applicable. (The algorithm does work correctly on sparser input systems but is usually not as efficient as the standard F4 algorithm for such inputs.)

Some key features of the dense variant of the F4 algorithm are as follows:

This variant essentially uses the same matrices as in the standard F4 algorithm (i.e., uses the same S-polynomials and reductors as usual) but exploits dense portions of the matrices where possible in the linear algebra phase, leading to significant speedups for larger examples.
There is often also significant savings in memory usage over the standard F4 algorithm.
If an NVIDIA GPU is available, then this is also exploited (in a special CUDA-enabled Magma executable), yielding greater speedups for larger examples.
Finally, there is a new experimental optional heuristic which can be selected for the algorithm when solving systems of equations over GF(2), called the Reduction Heuristic (see below), which can give an even greater reduction in time and memory usage for some large examples.

Some Timings For Systems Over GF(2)

The following table gives basic timings for some system solving examples over GF(2), as follows:

Timings are given in seconds, followed by the number of gigabytes of maximum memory usage in square brackets.
Columns are:
- System: The (dense) input problem. HFEn_k indicates an n-variable Hidden Fields Equations system with secret degree k. [Links for the actual input files will be added soon.]
- #vars: indicates the number of variables in the input system.
- D: indicates the maximal degree reached in the F4 algorithm.
- V2.19: uses the standard F4 algorithm (in Magma V2.19).
- V2.20: uses the new dense F4 algorithm (in Magma V2.20).
- V2.20 GPU: uses the new dense F4 algorithm combined with an NVIDIA Tesla C2075 GPU (448 CUDA cores).
- V2.20 RH: uses the new dense F4 algorithm combined with the Reduction Heuristic.
- V2.20 RH+GPU: uses the new dense F4 algorithm combined with the Reduction Heuristic and an NVIDIA Tesla C2075 GPU.
- Speedup Ratio: Gives the ratio of the timing with V2.19 to the timing with V2.20 RH+GPU and the respective ratio of the memory usage in brackets.
All runs use only one core and are run on a 3.2GHz Intel Xeon E5-1650 system (with 64GB memory), except for HFE200_100, HFE250_100, HFE60_288 and HFE80_288, which are run on a 3.1GHz Intel Xeon E5-2687W system (with 384GB memory).
Both Intel Xeon systems have have one NVIDIA Tesla C2075 GPU (448 CUDA cores), which was used for the computations with the GPU switched on. Note that this particular GPU is actually about 3 years old now, so is not state-of-the-art; current high-end GPUs should give greater speedups.

System
#vars
D
V2.19
V2.20
V2.20
GPU V2.20
RH V2.20
RH+GPU Speedup
Ratio

MQQ160 160 3 123.6
[2.6] 48.2
[1.5] 36.9
[1.5] 10.8
[1.5] 10.0
[1.5] 12.4
[1.7]

HFE40_96 40 4 23.1
[0.25] 9.7
[0.18] 6.9
[0.18] 6.3
[0.16] 4.8
[0.16] 4.8
[1.6]

HFE80_100 80 4 3477.1
[13.7] 447.4
[5.7] 220.7
[5.7] 180.4
[2.2] 86.0
[2.2] 40.4
[6.2]

HFE140_100 140 4 217984.6
[384] 17715.4
[142] 5853.9
[142] 4196.8
[26] 1246.2
[26] 174.9
[14.7]

HFE200_100 200 4 40227.7
[124] 10906.3
[124]

HFE250_100 250 4 152294.4
[369] 37405.4
[363]

HFE50_288 50 5 25571.9
[27.0] 9332.9
[22.9] 2165.4
[20.7] 2488.9
[15.0] 830.4
[13.5] 30.8
[2.0]

HFE60_288 60 5 154219.2
[111.8] 46371.0
[81.0] 9737.0
[75.9] 11570.3
[43.6] 3218.6
[43.6] 47.9
[2.6]

HFE80_288 80 5

118119.6
[275] 34498.3
[276]

System	#vars	D	V2.19	V2.20	V2.20 GPU	V2.20 RH	V2.20 RH+GPU	Speedup Ratio
MQQ160	160	3	123.6 [2.6]	48.2 [1.5]	36.9 [1.5]	10.8 [1.5]	10.0 [1.5]	12.4 [1.7]
HFE40_96	40	4	23.1 [0.25]	9.7 [0.18]	6.9 [0.18]	6.3 [0.16]	4.8 [0.16]	4.8 [1.6]
HFE80_100	80	4	3477.1 [13.7]	447.4 [5.7]	220.7 [5.7]	180.4 [2.2]	86.0 [2.2]	40.4 [6.2]
HFE140_100	140	4	217984.6 [384]	17715.4 [142]	5853.9 [142]	4196.8 [26]	1246.2 [26]	174.9 [14.7]
HFE200_100	200	4				40227.7 [124]	10906.3 [124]
HFE250_100	250	4				152294.4 [369]	37405.4 [363]
HFE50_288	50	5	25571.9 [27.0]	9332.9 [22.9]	2165.4 [20.7]	2488.9 [15.0]	830.4 [13.5]	30.8 [2.0]
HFE60_288	60	5	154219.2 [111.8]	46371.0 [81.0]	9737.0 [75.9]	11570.3 [43.6]	3218.6 [43.6]	47.9 [2.6]
HFE80_288	80	5				118119.6 [275]	34498.3 [276]

Some comments:

Note that the system HFE80_100 is the first 80-variable HFE Challenge of Patarin, which was first solved by J.-C. Faugere in 2002 and then by Magma V2.11 in 2004 in about 22 hours on a 750MHz Ultrasparc. Apart from processor speedup and exploitation of advanced hardware instructions (SSE and AVX), the code for the standard F4 is essentially unchanged from the V2.11 version (2004) up to the present.
When computing a Groebner basis, Magma V2.20 will automatically select the dense variant of the F4 algorithm if it considers that the input system is sufficiently dense. But one can force the dense variant to be used or not by setting the parameter Dense to true or false respectively for the Groebner procedure or the GroebnerBasis function. If the dense variant is turned off, V2.20 will use the standard F4 algorithm and take the same time as V2.19 on these inputs.
I hope to develop a multi-core version of this algorithm in 2014. Likewise for the Intel Phi architecture when that becomes available.
I thank Mohamed Saied Emam Mohamed for providing me with Magma code to generate the HFE systems. If you have any other dense input systems which have a non-trivial number of variables (especially of some other type), please send them to me to try out!

The Reduction Heuristic for Solving Systems over GF(2)

This is a brand new experimental heuristic which can be selected with the dense variant of F4 when attempting to solve certain kinds of systems of equations over GF(2) where it is assumed that there is a very small number of solutions, so the Groebner basis will consist of mostly linear polynomials or collapse to {1} when there is no solution.

The heuristic attempts to reduce the size of the matrices involved in the linear algebra phase of each F4 step. When the heuristic is selected, the run may simply fail, but when it succeeds, it often saves significant time and memory usage. The kinds of systems for which the saving in time and memory usage tends to be greatest are those such that in the F4 steps of maximal degree D, the number of S-polynomials is relatively small compared to the total number of monomials of degree D. The systems in the above table are all of this kind, so that is why there is a great speedup for them by using the heuristic.

Currently the heuristic depends on a manual choice by the user of a numerical parameter M and this is specified by passing the parameter ReductionHeuristic := M to the function GroebnerBasis with a maximal degree bound D. Thus if B is the sequence of input polynomials, to select the Reduction Heuristic with parameter M, one should invoke the algorithm with something like:

    GroebnerBasis(B, D: ReductionHeuristic := M);

where D is the expected maximal degree reached in the computation.

If M is large enough, then the computation will finish correctly and hopefully in considerably less time than would be the case without the heuristic selected; there always exists some number such that if M is greater than this, success is guaranteed. But if M is too small, then the algorithm will fail: a runtime error is usually triggered at the point that the algorithm realizes that M is too small. Also, conceivably the algorithm could fail to discover that M is too small and so a wrong Groebner basis could be returned (this point thus makes the algorithm Monte-Carlo). However: (1) a value of M which is too small is usually detected by Magma (and a runtime error is triggered); (2) the algorithm can actually be considered Las Vegas when solving a typical system known to have at least one solution since potential solutions can be trivially checked at the end (so coupled with checking, the algorithm either finds correct solutions or simply fails).

At the moment, it is impossible to suggest what is a suitable choice for M for any given system: I do not yet know in general how to pick a value for M which is guaranteed to work or is reasonably close to optimal -- if I knew how to do this, then this would be automatically incorporated into the algorithm (the heuristic is certainly very experimental at this stage)! But it is currently recommended in practice that one start with M=500 or 1000, and if there is failure, one should increase M successively by 500 or 1000 and restart from scratch and repeat this until the algorithm succeeds. Note that making M much larger than necessary reduces the effectiveness of the heuristic, so one should not just set M to a very large value.

It may seem inefficient if one has to try several runs with potential failure, but this is often alleviated as follows:

Since the algorithm often runs much faster with a small value for M (whether it succeeds or not), the total time taken for all runs including the ones which fail may still be significantly less than running without the heuristic selected.
Each run with the heuristic may use much less memory than the default run without the heuristic would use, so no matter how much time is taken, one will eventually be able to solve systems with the heuristic which are not solvable in the available memory with the default algorithm (for example, the systems above with 200 variables or more).
When solving a whole class of systems of the same type, one can determine a suitable M for one system and then use that for all the others. This includes multiple systems arising from evaluating a number of variables in some original system.

The values for M which were used in the above timings table are:

MQQ160: 500
HFE40_100: 1000
HFE80_100: 1000
HFE140_100: 2000
HFE200_100: 2500
HFE250_100: 3000
HFE50_288: 1500
HFE60_288: 2000
HFE80_288: 2500

In the near future, I hope to explain this heuristic in detail and generalize and automate it as much as possible...

Minrank Systems

The (n,k,r)-MinRank problem can be stated as follows: given a square linear matrix of size n with k variables (i.e., a matrix whose entries are k polynomials of degree 1 over a field), the goal is to find the locus of the points such that the evaluated matrix has rank less than or equal to r. This can be solved by applying Groebner basis techniques to the dense system of polynomial equations generated by all of the dim-(r+1) minors of the matrix.

The Courtois Minrank cryptographic challenge ("Problem C" [2001]) has (n,k,r)=(11,9,8). In their ISSAC 2010 paper (Sec 5.3), Faugere, Safey El Din and Spaenlehauer analyzed this challenge for the largest 16-bit prime field K=GF(65521) and suggested that the best attack would be to perform 65521 Groebner basis computations of the system with one variable evaluated at each value of K. Here is a comparison of their result with what can be done with Magma's new dense variant of F4:

Faugere et al estimated that a single instance (computing the Groebner basis of the evaluation of the system at one variable) takes 80255 seconds using Faugere's F5 code, so the challenge can be solved in about 166.7 core years, or in about 238 days on a 256-core Xeon cluster.
With the dense variant of F4 in Magma V2.20 [using some parameters to be released/explained soon], a single instance (again computing the Groebner basis of the evaluation of the system at one variable) takes 1637 seconds, so the challenge can be solved in about 3.4 core years, or in about 4.8 days on a 256-core cluster. Note that this single instance time is for a typical single 3.2GHz Intel core only, and does not exploit a Tesla GPU, since one will typically not have a very large number of GPUs in a cluster.

Thus the new Magma V2.20 time seems to be about 50 times faster than that of Faugere et al and clearly the challenge problem can now be easily solved on a moderately-sized cluster.

Update: Minrank Challenge C Solved Directly (August 2014)

In 2014 I have developed code within Magma for the Wiedemann algorithm for computing the minimal polynomial of large sparse matrices.

Using this, on 23 August 2014 I managed to solve a random instance over GF(65521) of the Cortois Minrank Challenge C where (n,k,r)=(11,9,8), using the direct approach with the Wiedemann algorithm (that is, without using the above evaluation method).

The current times for this direct method are:

Dense F4: 7.0 hours [computes the grevlex GB of the zero-dimensional ideal; the GB has 51275 polys with up to 48620 terms each].
Wiedemann: 23.2 hours [computes the minimal polynomial of a 259545 by 259545 matrix with density 13.4%].

This is using just one Intel E5-2687W (3.1GHz) core and a Tesla C2075 GPU (same as above).

Update (July 2015): Details on the computation (which can now be done in 15.1 hours with just one core and a K40 Tesla GPU) can be found in my PASCO 2015 paper.