"Kernel attack" on MinRank -- why do we guess $\left\lceil \frac k n \right\rceil$ vectors? The kernel attack on MinRank is described here (page 5). My question refers to this line:


  Note that if $m = \left\lceil \frac k n \right\rceil$, the system essentially has only one solution $\lambda = (\lambda_1, \ldots, \lambda_k)$.


Why is this so? I understand that when $m = \left\lceil \frac k n \right\rceil$ the described system is never underdetermined, but how does this help? Any insight / further references?
So we have $k+1$ matrices $M_0, M_1, \ldots, M_k \in \mathbb{K}^{n\times{}n}$. We are trying to find weights $\mu_1, \dots, \mu_k$ such that the rank of the weighted sum of matrices is smaller than or equal to some target rank: $\mathsf{rank}(-M_0 + \sum_{i=1}^k\mu_iM_i) \leq r$.

The Courtois and Goubin strategy is to select $m$ random vectors $\mathbf{x}^{(i)} \in \mathbb{K}^n$ (for $i$ from $1$ to $m$) and hope they all lie in the kernel of some combination of the matrices. If these vectors do lie in the kernel of suck a weighted sum, we can then easily find those weights by solving for $\mu = (\mu_1,\ldots,\mu_k)$ the linear system
$ \left\{ (-M_0 + \sum_{j=1}^k\mu_jM_j)\mathbf{x}^{(i)} = \mathbf{0} \right\} $
for all
$ i \in \{1, \ldots, m\}$.

This linear system consists of $mn$ equations and $k$ variables. If $k = mn$, then we expect there to be one solution. If $k &lt; mn$, then the system might well be over-determined and might not admit any solutions, whereas if $k &gt; mn$ then we might find several solutions rather than a single one. We are aiming for the case in which the system has one solution, so we must choose $m$ so that $k \approx mn$ holds as well as possible. Further constraints on $m$ are that it is an integer -- so we must round up or down -- and that it is different from zero -- because otherwise we have no equations. So the natural choice is $m = \lceil {k \over n} \rceil$.