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?

Improve this question
$\endgroup$
7
  • $\begingroup$ Can any matrix with a 0 entry be MDS? $\endgroup$ Commented May 4, 2016 at 18:02
  • $\begingroup$ @poncho I would not ask, if I would know. But I suspect it can't be. $\endgroup$ Commented May 4, 2016 at 18:04
  • $\begingroup$ Hint: what's the definition of MDS? $\endgroup$ Commented 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$ Commented 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$ Commented May 5, 2016 at 0:28

1 Answer 1

Reset to default
7
$\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.

Improve this answer
$\endgroup$
3
  • $\begingroup$ So 16 x 16 matrix like this would have branch number 16? $\endgroup$ Commented May 7, 2016 at 7:52
  • 1
    $\begingroup$ @LightBit unfortunately no, see the edit. $\endgroup$ Commented May 7, 2016 at 9:54
  • $\begingroup$ @kodlu Do you know where there is a python code to determine the branch number a matrix. The def of branch number is complicated and how to the differential and linear branch number are the same. Thank you. $\endgroup$ Commented Apr 10, 2024 at 9:53

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.