Challenge matrices

Now, that we have a decent PNG reader/writer in M4RI, it’s much easier to get some challenge matrices out of the library. Below, I list and link a few such matrices as they appear during Gröbner basis computations.

file matrix dimensions density PLE M4RI GB
HFE 25 matrix 5 (5.1M) 12307 x 13508 0.07600 1.03 0.59 0.81
HFE 30 matrix 5 (16M) 19907 x 29323 0.06731 4.79 2.70 4.76
HFE 35 matrix 5 (37M) 29969 x 55800 0.05949 19.33 9.28 19.51
Mutant matrix (39M) 26075 x 26407 0.18497 5.71 3.98 2.10
random n=24, m=26 matrix 3 (30M) 37587 x 38483 0.03832 20.69 21.08 19.36
random n=24_ m=26 matrix 4 (24M) 37576 x 32288 0.04073 18.65 28.44 17.05
SR(2,2,2,4) compressed, matrix 2 (328K) 5640 x 14297 0.00333 0.40 0.29 0.18
SR(2,2,2,4) compressed, matrix 4 (2.4M) 13665 x 17394 0.01376 2.18 3.04 2.04
SR(2,2,2,4) compressed, matrix 5 (2.8M) 11606 x 16282 0.03532 1.94 4.46 1.59
SR(2,2,2,4) matrix 6 (1.4M) 13067 x 17511 0.00892 1.90 2.09 1.38
SR(2,2,2,4) matrix 7 (1.7M) 12058 x 16662 0.01536 1.53 1.93 1.66
SR(2,2,2,4) matrix 9 (36M) 115834 x 118589 0.00376 528.21 578.54 522.98

The first three rows are from GB computations for the hidden field equations cryptosystem (those matrices were provided by Michael Brickenstein). The “mutant” row is a matrix as it appears during a run of the MXL2 algorithm on a random system (I believe). It was contributed by Wael Said. The rows “random n=25,m=26” are matrices as they appear during a GB computation with PolyBoRi for a random system of equations in 24 variables and 26 equations. The remaining rows are matrices from PolyBoRi computations on small scale AES instances. Those rows which have “compressed” in their description correspond to systems where “linear variables” were eliminate before running the Gröbner basis algorithm.

The last three columns give running times (quite rough ones!) for computing an echelon form (not reduced) using (a) the M4RI algorithm, (b) PLE decomposition and (c) a first implementation of the TRSM for trivial pivots trick. As you can see, currently it’s not straight-forward to pick which strategy to use to eliminate matrices appearing during Gröbner basis computations: the best algorithm to pick varies between different problems and the differences can be dramatic.

Advertisements

6 thoughts on “Challenge matrices”

  1. Here’s the message schedule for SHA-1, generated with M4RI. It’s much smaller than your examples, though.

    (That’s the w[i] = rotl32(w[i – 3] ^ w[i – 8] ^ w[i – 14] ^ w[i – 16], 1) part of the algorithm.)

    Unfortunately, I wasn’t able to use mzd_solve_left() — it seems to return incorrect solutions. Is it supposed to be working? I noticed that solve.h contains the following line:

    * \attention This file is currently broken.

    But maybe I’m just using it incorrectly.

  2. Hi, we should remove this line, so I just did 🙂

    How are you calling mzd_slove_left() and what’s the answer you expect vs. the answer you get? I noticed that xor-0-original.png is not square, so I don’t what you are trying to solve?

    1. The matrix above (augmented with a few rows to support fixing certain variables) is A, and another 1x(80*32) matrix B which is mostly zero but has ones for the corresponding variables in A which were fixed to 1. I wanted to use mzd_solve_left(A, B, 0, 1) to solve Ax = B, where x is the (sought) solution.

      What happens is that the solution (now in variable B) is completely blank — it contains only 0 entries, even where I forced certain variables to 1 by including the equations 1x = 1.

  3. Just to make sure, you are using the library correctly, here’s a small program that should be quite similar to your case. So far, I couldn’t detect a bug. Perhaps you could send me both your final A and your final B and then I’d see if I can reproduce the bug?

    #include
    #include

    rci_t mzd_rank(mzd_t *A) {
    mzd_t *AA = mzd_copy(NULL,A);
    rci_t r = mzd_echelonize(AA, 0);
    mzd_free(AA);
    return r;
    }

    int main(int argc, char *argv[]) {
    const rci_t m = 2048;
    const rci_t n = m+100;

    mzd_t *A = mzd_init(m, n);
    while(mzd_rank(A) != m) {
    mzd_randomize(A);
    }

    mzd_t *X = mzd_init(n, 1);
    mzd_randomize(X);

    mzd_t *B = mzd_init(n, 1);
    mzd_t *Bw = mzd_init_window(B, 0, 0, m, 1);

    mzd_mul(Bw, A, X, 0);

    mzd_copy(X, B);

    mzd_t *AA = mzd_copy(NULL, A);
    mzd_solve_left(AA,X,0,1);

    mzd_t *B2 = mzd_mul(NULL, A, X, 0);

    printf(“%d\n”,mzd_cmp(B2,Bw));

    mzd_free(A);
    mzd_free(AA);
    mzd_free(X);
    mzd_free(B);
    mzd_free(Bw);
    mzd_free(B2);
    }

  4. One more thing, we have the convention in M4RI that the redundant bits are set to zero when we are solving. But it seems you are looking for a vector with those bits set to something nonzero. You could use mzd_kernel_left_pluq() to do that, as illustrated by the following Sage code (since I’m too laze to write it in C right now):

    sage: m,n = 5, 10
    sage: A = random_matrix(GF(2), m, n)
    sage: X = random_vector(GF(2), n)
    sage: B = A*X
    sage: AB = A.augment(B)
    sage: X2 = AB.right_kernel().matrix()
    sage: for row in X2.rows():
    … if row[-1]:
    … A * row[:-1] == B
    True
    True
    True

    Note that Sage’s notion of left and right is reversed from the M4RI (and standard?) notion, i.e. in M4RI it would be the left kernel.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s