4
$\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$
  • $\begingroup$ Can any matrix with a 0 entry be MDS? $\endgroup$ – poncho May 4 '16 at 18:02
  • $\begingroup$ @poncho I would not ask, if I would know. But I suspect it can't be. $\endgroup$ – LightBit May 4 '16 at 18:04
  • $\begingroup$ Hint: what's the definition of MDS? $\endgroup$ – poncho May 4 '16 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 '16 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 '16 at 0:28
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$
  • $\begingroup$ So 16 x 16 matrix like this would have branch number 16? $\endgroup$ – LightBit May 7 '16 at 7:52
  • 1
    $\begingroup$ @LightBit unfortunately no, see the edit. $\endgroup$ – kodlu May 7 '16 at 9:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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