I have some trouble understanding how Kernel Attack to MinRank is implemented.
MinRank: Let $k, n, r$ be positive integers, and let $M_0, M_1, \dots, M_k$ be $n \times n$ matrices with entries in a finite field $\mathbb{F}_q$. We want to find (if they exist) $\lambda_1, \dots, \lambda_k \in \mathbb{F}_q$ such that $E_\lambda := M_0 - \sum_{i=1}^k \lambda_i M_i$ has rank not exceeding $r$.
Regarding the Kernel Attack, I understood that, given $m$ random column vectors $\mathbf{x}^{(1)}, \dots, \mathbf{x}^{(m)} \in \mathbb{F}_q^n$, the probability that they all belong to $\ker(E_\lambda)$ is at least $q^{-mr}$; and that, if they do, then $\lambda_1, \dots, \lambda_k$ can be found by solving the linear system of $mn$ equations in $k$ unknown $\lambda_1, \dots, \lambda_k$ given by $(M_0 - \sum_{i=1}^k \lambda_i M_i) \mathbf{x}^{(j)} = \mathbf{0}$ for $j=1,\dots,m$. Hence, generating the random vectors $\mathbf{x}^{(1)}, \dots, \mathbf{x}^{(m)}$ many times, the average number of attempts before we find $\lambda_1, \dots, \lambda_k$ is $O(q^{mr})$.
My question is: How do we check (in the least expensive way) that the vectors $\mathbf{x}^{(1)}, \dots, \mathbf{x}^{(m)}$ gives $\lambda_1, \dots, \lambda_k$ and so we can stop?
Clearly:
If the system $(M_0 - \sum_{i=1}^k \lambda_i M_i) \mathbf{x}^{(j)} =\mathbf{0}$ has no solution, then we have to try another random $\mathbf{x}^{(1)}, \dots, \mathbf{x}^{(m)}$.
If the previous system has a solution $\lambda_1, \dots, \lambda_k$, and the rank of the $m \times n$ matrix with columns $\mathbf{x}^{(1)}, \dots, \mathbf{x}^{(m)}$ is at least $n - r$, then the rank of $E_\lambda$ is not exceeding $r$ (by rank+nullity theorem).
But is (2) efficient? Maybe it is better checking directly the rank of $E_\lambda$...
