On new multivariate cryptosystems with nonlinearity gap

Abstract

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 \({\rm 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 \({\rm deg}(F_n)\) is bounded by independent constant but \({\rm 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\).