While reading this article on rank attacks on STS (a public-key scheme based on Multivariate Quadratic (MQ) equations), I stumbled upon some claims that I've also seen in other presentations on rank-attacks. However I'm not able to see why this claim follows. A description of STS and rank-attacks follows.
If you are already familiar with STS and rank-attacks, feel free to skip this section
In STS, the public key is (as usual in MQ-systems) created as: $\mathcal{P} = T \circ \mathcal{Q} \circ S$, where $S$ and $T$ are invertible linear maps and $\mathcal{Q}$ the central map consisting of $m$ quadratic equations in $n$ variables, for simplicity we just assume $m = n$. In STS, the $m$ equations are divided into $L = n/r$ "steps", where step $\ell$ consists of $r$ equations in $\ell r$ variables. I.e. for each new step, you add $r$ new equations, having $r$ more variables than in the previous step (this is where the name stepwise-triangular comes from, ref Fig. 1, in the linked paper). For this question, I will also make the simplifying assumption that $S = T = I_n$.
Let $A_i$ be the symmetric matrix representing the quadratic form of each polynomial in $\mathcal{Q}$. That is, for a polynomial $p_i(x)$, the expression: $x A_ix^T$ gives all its quadratic terms, where $x \in \mathbb{F}^n$. Now, the basic idea of rank-attacks is to find a linear combination of these matrices $A_i$, such that $\mathrm{rank}(\sum_{i=1}^mb_iA_i)\leq lr$. This equation be used to determine a chain of kernels of the matrices, so as to find the secret map $T$. I know I assumed $T = I_n$ above, but this is not very important for my question (just assume we don't know $T$). The essence of the attack in the paper is to make a guess on the rows of $T$, and this guess can be verified by the condition on the rank above.
My questions (finally ...)
In the paper, the following chain of subspaces is considered: $$ \mathbb{F}_q^m = J_L \supset J_{L-1} \supset \dots \supset J_1, $$ where $$ J_{\ell} := \{ b \in \mathbb{F}_q^m | b_{\ell r + 1} = \dotso = b_m = 0 \}, \text{ for } 1 \leq \ell < L.$$ It's easy to see that $\mathrm{dim }(J_{\ell}) = \ell r$. If you pick a random element $b \in_R J_{\ell + 1}$, then, with probability $q^{-r}$, we also have $b \in J_{\ell}$. To check this property, they propose the following test:
$$\mathrm{rank}(\sum_{i=1}^mb_iA_i)\leq lr \text{ if and only if } b \in J_{\ell} $$
but is this true??
Isn't this a counterexample: $$ \mathbb{F}_q^m = \mathbb{F}_3^6, \\ L = 3, \\ r = 2, \\ p_1 = x_1^2 + x_2^2, \\ p_2 = 0, \\ p_3 = x_1^2 + x_2^2 + x_3^2 + x_4^2, \\ p_4 = p_5 = p_6 = 0 $$ If you look at $b = (1, 0, 2, 0, 0, 0) \in J_2$ , then $$\mathrm{rank}(\sum_{i=1}^6b_iA_i) = \mathrm{rank}(A_1 + 2A_3) = \mathrm{rank} \begin{pmatrix} 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 2 & 0 & 0 & 0\\ 0 & 0 & 0 & 2 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0\\ \end{pmatrix} = 2 \leq 4$$
but $b \notin J_1$!!! Is there something fundamental I've misunderstood?This question is simply about the representation of the quadratic form of each polynomial in the public key. Say we want to find the matrix $A_i$ representing the quadratic form of $p_i(x)$ in $\mathcal{P}$. We know that $p_i$ is the $i$'th coordinate of the vector $T \cdot \widehat{\mathbf{p}}$, where $\widehat{\mathbf{p}}$ again is a vector of quadratic polynomials, created as $\mathcal{Q} \circ S (x)$ and $T = (t_{i,j})_{1 \leq i,j \leq m}$.
If we let the matrix representation of each coordinate (i.e. a polynomial) in $\widehat{\mathbf{p}}$ be $\widehat{A}_i$, we should get $A_i = \sum_{j=1}^m t_{i,j}\widehat{A}_{\mathbf{j}}$ right? (Note the $\mathbf{j}$ in $\widehat{A}_{\mathbf{j}}$)
However: in the linked paper (see the equation just above the start of section 2.2) and many other papers on MQ, I see $A_i$ presented as: $$A_i = \sum_{j=1}^m t_{i,j}\widehat{A}_{\mathbf{i}} \;\;\; \text{ (note the } \mathbf{i}).$$ Isn't this simply plain wrong?!
