5
$\begingroup$

We have the following matrix: $$\begin{pmatrix}0&1&1&1\\ 1&0&1&1\\ 1&1&0&1\\ 1&1&1&0\end{pmatrix}$$

What is the branch number?

Is this a MDS marix?

$\endgroup$
7
  • $\begingroup$ Can any matrix with a 0 entry be MDS? $\endgroup$
    – poncho
    May 4, 2016 at 18:02
  • $\begingroup$ @poncho I would not ask, if I would know. But I suspect it can't be. $\endgroup$
    – LightBit
    May 4, 2016 at 18:04
  • $\begingroup$ Hint: what's the definition of MDS? $\endgroup$
    – poncho
    May 4, 2016 at 18:49
  • $\begingroup$ Also, the answer depends on the ring that the matrix is based on. This matrix is singular if the matrix elements are $GF(3)$ $\endgroup$
    – poncho
    May 4, 2016 at 21:44
  • $\begingroup$ @poncho, you're right that a zero in $A$ constrains the rank. Having all nonzero entries over $GF(2)$ (thus all 1's) results in a singular $A$ and a (relatively) bad code. $\endgroup$
    – kodlu
    May 5, 2016 at 0:28

1 Answer 1

6
$\begingroup$

The matrix is not MDS over $GF(2)$; No binary MDS codes exist and non nonbinary (over $GF(2^n)$ MDS codes would have this generator whose scalar entries are in the field $GF(2)$). Over $GF(2^n)$ The branch number, which is the minimum weight of the corresponding linear code is 4, in $GF(2^n)$ for all $n$. This covers all possible fields of interest for crypto.

Note that you just need to take the given matrix, call it $A,$ form $G=[I | A]$ over the relevant field and determine the minimum weight of the resulting code. Magma (and GAP, Pari, Python) can do this for you easily. This code turns out to be a quasi-cyclic code over the fields $GF(2^n)$ with minimum distance 4.

Edit: It seems that 4 is the limit for the minimum distance of this type of code. In particular a $16\times16$ version, still has minimum distance only 4, for the fields $GF(2^n)$ where $n=1,2,\ldots,8.$ I assume $n=8$ is of interest to the OP, since it corresponds to having bytes as code symbols, as in AES.

This was checked on Magma as well.

$\endgroup$
2
  • $\begingroup$ So 16 x 16 matrix like this would have branch number 16? $\endgroup$
    – LightBit
    May 7, 2016 at 7:52
  • 1
    $\begingroup$ @LightBit unfortunately no, see the edit. $\endgroup$
    – kodlu
    May 7, 2016 at 9:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.