4
$\begingroup$

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.

$\endgroup$

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.