1
$\begingroup$

Is there an efficient algorithm which can be used to determine the branch number of any given linear mapping?

$\endgroup$
3
$\begingroup$

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.

https://ieeexplore.ieee.org/document/641542

$\endgroup$
3
  • $\begingroup$ Where can I find more information about why it is NP complete? Is it proven? $\endgroup$ – Monster Mar 31 at 15:32
  • $\begingroup$ See edit please $\endgroup$ – kodlu Mar 31 at 22:40
  • $\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$ – Monster Apr 1 at 15:38

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.