Is there an efficient algorithm which can be used to determine the branch number of any given linear mapping?
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
3
As explained in the answer to the question here the branch number of a linear mapping $$ A:F_q^n \rightarrow F_q^n, \quad x\mapsto A\cdot x $$ is the minimum weight of the linear code generated by the matrix $$ G=[~I~|~A]. $$ For an arbitrary matrix $A$ this problem is NP hard, i.e., very hard. For structured matrices like the MDS matrix in AES the answer is known, see the link.
For the hardness result see Vardy's paper "the intractability of computing the minimum distance of a code". It or a related version is also available on citeseer. Since this code is linear minimum distance equals minimum weight.
-
$\begingroup$ Where can I find more information about why it is NP complete? Is it proven? $\endgroup$– MonsterMar 31, 2021 at 15:32
-
-
$\begingroup$ By the definition of the NP completeness, a solution to an NP complete problem can be verified quickly. Let's say we have an 8x8 matrix with elements in GF(2^8), the maximum branch number of it is 9. Can't we just quickly check whether the branch number is 2, 3, .., 9? $\endgroup$– MonsterApr 1, 2021 at 15:38