|
Algebra and Discrete Mathematics, 2017, том 23, выпуск 2, страницы 331–348
(Mi adm614)
|
|
|
|
RESEARCH ARTICLE
On new multivariate cryptosystems with nonlinearity gap
Vasyl Ustimenko Institute of Mathematics, Maria Curie-Sklodowska University, Plac Marii Curie-Skllodowskiej 5, 20-031 Lublin, Poland
Аннотация:
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$.
Ключевые слова:
multivariate cryptography, linguistic graphs, multivariate stable maps.
Поступила в редакцию: 11.06.2017
Образец цитирования:
Vasyl Ustimenko, “On new multivariate cryptosystems with nonlinearity gap”, Algebra Discrete Math., 23:2 (2017), 331–348
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/adm614 https://www.mathnet.ru/rus/adm/v23/i2/p331
|
|