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


$$\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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.