On algebraic graph theory and non-bijective multivariate maps in cryptography

Abstract

Special family of non-bijective multivariate maps \(F_n\) of \({Z_m}^n\)
into itself is constructed for \(n = 2, 3, \dots\) and composite~\(m\).
The map \(F_n\) is injective on \(\Omega_n=\{{\rm x}|x_1+x_2 + \dots
x_n \in {Z_m}^* \}\) and solution of the equation \(F_n({\rm x})={\rm
b}, {\rm x}\in \Omega_n\) can be reduced to the solution of equation \(z^r=\alpha\), \(z \in {Z_m}^*\), \((r, \phi(m))=1\). The ``hidden RSA
cryptosystem'' is proposed.

Similar construction is suggested for the case  \(\Omega_n={{Z_m}^*}^n\).