RUS  ENG
Полная версия
ЖУРНАЛЫ // Algebra and Discrete Mathematics // Архив

Algebra Discrete Math., 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.

MSC: 12Y05, 12Y99, 05C81, 05C85, 05C90, 94A60, 14G50

Поступила в редакцию: 11.06.2017

Язык публикации: английский



Реферативные базы данных:


© МИАН, 2025