# Questions on rank-attacks in Multivariate Cryptography

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 ...)

1. 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?

2. 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?!

[To the moderators]

I know that this basically boils down to a linear algebra question, so feel free to move it to math, if you think that's the better place. I posted it here, since the reason for studying this question is so intimately related to cryptanalysis.

-

# Q1

You are right. The authors' test returns true in your false-negative counterexample.

I note that the authors proposed the following test

$\mathsf{matrixCheck}(P_1,\dots,P_m,v,l)$ returns true iff $Rank(\sum_{i=1}^{m} v_i P_i) \leq lr$.

This sentence says how the algorithm $\mathsf{matrixCheck}$ is defined and says nothing on the correctness.

Although this checking algorithm has false-negative error, it is enough to mount the authors' attack, since submatrices of $A_3$ and $A_4$ are linearly independent from $A_1$ and $A_2$ with high probability.

# Q2

You are right. It is a confusing typo.

-