# Help with cryptanalysis of branching in schemes based on Multivariate Public Key Cryptography

I'm familiarized with the structure of branching found in Multivariate Cryptography, as it allows us to partition a $$n$$-tuple over $$F_{q}$$ into a $$k$$-tuple where the $$i$$-th element is in $$F_{q^{\lambda_i}}$$ for $$\lambda \vdash n$$ and $$k$$ is the partition length.

Thus, instead of having just a single private polynomial over $$F_{q^n}$$, we have $$k$$ private polynomials $$f_i(X_i) \in F_{q^{\lambda_i}}[x]$$. The speedup is significant as we can divide the decryption/signing process into multiple execution units, so it's highly parallelizable.

The mathematical representation of this technique can be given as:

$$\phi : F_{q}^n \mapsto F_{q^{\lambda_1}}\times \cdots \times F_{q^{\lambda_k}}, \quad (x_1,\cdots,x_n) \mapsto (\varphi_{\lambda_1}(x_1,\cdots,x_{\lambda_1}),\cdots,\varphi_{\lambda_k}(x_{(1+\sum_{i=1}^{k-1}\lambda_i)},\cdots,x_n)$$

where:

$$\varphi_{\lambda_i} : F_q^{\lambda_i} \mapsto F_{q^{\lambda_i}}, \quad (x_1,\cdots,x_{\lambda_i}) \mapsto \sum_{i=1}^{\lambda_i}x_i y^{i-1}$$

Define $$\mathcal{F}=(f_1(X),\cdots,f_k(X))\in F_{q^{\lambda_1}}\times \cdots \times F_{q^{\lambda_k}}$$ as the private polynomial map composed of $$k$$ polynomials over distinct fields. Then let $$P(X)$$ be the public map composition that is publicly published:

$$P(X)= T \circ \phi^{-1} \circ \mathcal{F} \circ \phi \circ S (x_1\cdots,x_n)$$

where $$S,T \in GL(n,F_q)\times F_q^n$$ this is both $$S,T$$ are affine transforms.

It results that the original scheme $$C^*$$ presented by Matsumoto-Imai in 1 included the branching variant based in a selected partition $$n_1 + \cdots + n_d = n$$. The general description can be stated the same as the presentation I gave above.

I'm struggling with the cryptanalysis of branching techniques applied on schemes based on $$\textbf{MPKC}$$. In my research, the $$k$$ private polynomials found in $$\mathcal{F}$$ are $$\textbf{HFE}$$ polynomials instead of Mat-Imai monomials. However, it seems that branching is discouraged when $$k>2$$, so it's not fancy anymore.

Can someone give me a simple explanation on why the technique exposed in 2 (section $$4$$), 3 (section $$11.2$$) and 4 (page $$3$$) works?

What I've understood at this point is that cryptanalysis on branching pursues the separation of these branches into independent sets of equations, each set $$i$$ concerning variables that don't come from branch $$\lambda_i$$. Once these sets are computed, apply exhaustive-search on each branch as these branches are small.