On new multivariate cryptosystems with nonlinearity gap

Vasyl Ustimenko

Algebra and discrete mathematics, Tome 23 (2017) no. 2, pp. 331-348

Résumé

The pair of families of bijective multivariate maps of kind $F_n$ and ${F_n}^{-1}$ on affine space $K^n$ over finite commutative ring $K$ given in their standard forms has a nonlinearity gap if the degree of $F_n$ is bounded from above by independent constant $d$ and degree of $F^{-1}$ is bounded from below by $c^n$, $c>1$. We introduce examples of such pairs with invertible decomposition $F_n ={G^1}_n{G^2}_n\dots {G^k}_n$, i.e. the decomposition which allows to compute the value of ${F^n}^{-1}$ in given point $\mathrm{p}=(p_1, p_2, \dots, p_n)$ in a polynomial time $O(n^2)$. The pair of families ${F_n}$, $F'_n$ of nonbijective polynomial maps of affine space $K^n$ such that composition $F_nF'_n$ leaves each element of ${K^*}^n$ unchanged such that $\operatorname{deg}(F_n)$ is bounded by independent constant but $\operatorname{deg}(F'_n)$ is of an exponential size and there is a decomposition ${G^1}_n{G^2}_n\dots {G^k}_n$ of $F_n$ which allows to compute the reimage of vector from $F({K^*}^n)$ in time $0(n^2)$. We introduce examples of such families in cases of rings $K=F_q$ and $K=Z_m$.

Détail

Keywords: multivariate cryptography, linguistic graphs, multivariate stable maps.