Hybrid Approach for Solving Multivariate Polynomial Systems over Finite Fields

This page is due to Luk Bettale. The goal is to present the implementation of the hybrid approach, and the tools to compute its complexity. All the material is available through the MAGMA package Hybrid.m. The code is also part of Luk's PhD thesis. We describe here the basics of this method as well as how to use the functions in Hybrid.m. The description of the main intrinsics are given here. You may also want to use Luk's magma-mode for editing and interpreting magma code in emacs.

Let {f1, …, fm} ⊂ K [x1, …, xn] be a set of m polynomials in n variables of degree d, where K is a finite field of size q. The general PoSSo problem is to find (if any) (z1, …, zn) ∈ Kn such that:

   f1 (z1, …, zn) =0
  ⋮
   fm (z1, …, zn) =0

If the system is zero-dimensional, the classical method to address this problem is to compute the Lex Gröbner basis of the generated ideal. A Lex Gröbner basis allow to efficiently recover the solutions of the system. The strategy used by modern computer algebra softwares is the zero-dim strategy, that is:

  1. Compute a DRL Gröbner basis (Buchberger, F4, F5)
  2. Change order to Lex (FGLM)
  3. Return the solutions

For instance, consider the following code in MAGMA.

/* helper function to generate a random affine polynomial */
RandomAffine := func < d,R | &+ [ Random(deg,R,0) : deg in [0..d] ] >;

/* parameters */
q := 2^5; n := 12; m := 12; d := 2;

K := GF(q);
R<[x]> := PolynomialRing(K,n);
F := [ RandomAffine(d,R) : i in [1..m] ];
var := VarietySequence(Ideal(F));

When computing VarietySequence(Ideal(F)), that is computing the solutions of the system F, MAGMA will blindly perform the F4 algorithm and then the FGLM algorithm. These two steps are detailed when one activate the "Groebner" verbose flag with SetVerbose("Groebner",1).

The idea of the hybrid approach is to mix exhaustive search with Gröbner bases computations. Instead of computing one single Gröbner basis of the whole system, we compute the Gröbner bases of qk subsystems obtained by fixing k variables. In [BFP09], we show how this method improve the polynomial system solving in medium size fields. As proof of concept, we were able to break the parameters of several multivariate schemes assumed to be secure. We provide in the file Hybrid.m an implementation of the hybrid approach in magma. Using the previous example, the solutions can be computed this way:

Attach("Hybrid.m");
k := 1;
var := HybridSolving(F,k);

Here is a sample execution on the previous parameters.

> Attach("Hybrid.m");
> time var := VarietySequence(Ideal(F));
Time: 1345.460
> varHyb := [];
> time varHyb[1] := HybridSolving(F,1);
Time: 628.940
> time varHyb[2] := HybridSolving(F,2);
Time: 904.360
> time varHyb[3] := HybridSolving(F,3);
Time: 2695.400
> &and [ Set(var) eq Set(v) : v in varHyb ];
true

From the previous example, we see that the efficiency of the hybrid approach depend on the proper choice of a trade-off (the parameter k). In [BFP09], we analyze the complexity of the hybrid approach and we give a method to compute the best theoretical trade-off as well as asymptotic approximations. The precise knowledge of the complexity of the hybrid approach (for random systems) allows us to use it as a tool to calibrate the parameters of multivariate cryptosystems. In the file Hybrid.m, we also give the necessary material to compute the complexity of the hybrid approach in MAGMA. In the following example, we will compute the theoretical complexity of solving the previous system. We only need the parameters : q (the size of the field), n (the number of variables), d1,…,dm (the degrees of the m equations). As the complexity involves ω, the linear algebra constant, it is an optional parameter of our functions. It is set to default 2.4 as the matrices involved are very sparse. On the previous parameters, let's consider the following execution:

> Attach("Hybrid.m");
> for k := 0 to n do
for> print k,Log(2,HybridComplexity(q,n,[d : i in [1..m]],k));
for> end for;
0 53.5443928301582811251782842619
1 40.8987861460009854357400557271
2 41.1213430212063844576915480438
3 41.3213430212063844576915480438
4 41.4830833159207327207451848739
5 41.5765374294604444703777400963
6 45.3415618146690246933496998269
7 48.9376518129382498578607263614
8 49.3765374294604444703777400963
9 52.9726274277296696348887666308
10 56.2039100017307748354889734655
11 58.8039100017307748354889734655
12 60.0000000000000000000000000000

The experiments match the theoretical results as the best trade-off is to choose k=1.

Available intrinsics

HybridSolving(F, k) : [ RngMPolElt ], RngIntElt -> [ [ FldFinElt ] ]

Returns the variety of Ideal(F) in the coefficient field with the hybrid approach with the trade-off k.

BestTradeOff(q, n, degs) : RngIntElt, RngIntElt, [ RngIntElt ] -> RngIntElt, BoolElt

    Omega: FldReElt                    Default: 2.4

Returns the best trade-off for the hybrid approach for given parameters and true if the field equations have to be used to obtain the best trade-off.

HybridComplexity(q, n, degs, k) : RngIntElt, RngIntElt, [ RngIntElt ], RngIntElt -> RngIntElt

    Omega: FldReElt                     Default: 2.4

Returns the complexity of the hybrid approach for a semi-regular system of m equations of degree degs[1..m] in n variables in q, with the trade-off k.

DegreeOfRegularity(n, degs) : RngIntElt, [ RngIntElt ] -> RngIntElt

Returns the degree of regularity of a semi-regular system of m equations of degree degs[1..m] in n variables.

F5Complexity(n, m, degs) : RngIntElt, RngIntElt, [ RngIntElt ] -> RngIntElt

    Omega: FldReElt                     Default: 2.4

Returns the complexity of F5 for a system with n variables, m equations and whose degree of regularity is dreg.

FGLMComplexity(n, degs) : RngIntElt, [ RngIntElt ] -> RngIntElt

    Omega: FldReElt                     Default: 2.4

Returns the complexity of FGLM for a generic system of m equations of degree degs[1..m] in n variables.

PossoComplexity(n, degs) : RngIntElt, [ RngIntElt ] -> RngIntElt

    Omega: FldReElt                     Default: 2.4

Returns the complexity of Posso for a semi-regular system of m equations of degree degs[1..m] in n variables (F5 + FGLM).

Back