International Association
for Cryptologic Research

The concept of multivariate bijective map of an affine space $K^n$ over commutative

Ring $K$ was already used in Cryptography. We consider the idea of nonbijective multivariate

polynomial map $F_n$ of $K^n$ into $K^n$ represented as \'\'partially invertible decomposition\'\'

$F^{(1)}_nF^{(2)}_n \\dots

F^{(k)}_n$, $k=k(n)$, such that knowledge on the decomposition and given

value $u=F(v)$ allow to restore a special part $v\'$ of reimage $v$.

We combine an idea of \'\'oil and vinegar signatures cryptosystem\'\' with the idea of linguistic graph based map with partially invertible decomposition to introduce a new

cryptosystem. The decomposition will be induced by pseudorandom walk on the linguistic graph

and its special quotient (homomorphic image). We estimate the complexity of such general algorithm in case of special family of graphs with quotients, where both graphs form known

families of Extremal Graph Theory. The map created by key holder (Alice) corresponds to

pseudorandom sequence of ring elements.

The postquantum version of the algorithm can be obtained simply by the usage of random strings

instead of pseudorandom.