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?
$\begingroup$
$\endgroup$
7
-
$\begingroup$ Can any matrix with a 0 entry be MDS? $\endgroup$– ponchoMay 4, 2016 at 18:02
-
$\begingroup$ @poncho I would not ask, if I would know. But I suspect it can't be. $\endgroup$– LightBitMay 4, 2016 at 18:04
-
$\begingroup$ Hint: what's the definition of MDS? $\endgroup$– ponchoMay 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$– ponchoMay 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$– kodluMay 5, 2016 at 0:28
|
Show 2 more comments
1 Answer
$\begingroup$
$\endgroup$
2
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.
-
$\begingroup$ So 16 x 16 matrix like this would have branch number 16? $\endgroup$– LightBitMay 7, 2016 at 7:52
-
1