**On two windows multivariate cryptosystem depending on random parameters**

*Urszula Romańczuk-Polubiec, Vasyl Ustimenko*

**Abstract: **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.

**Category / Keywords: **public-key cryptography / Cryptosystem, Multivariate cryptography, Postquantum cryptography, Algebraic incidence structure, Pseudorandom sequences, Pseudorandom walk in graph

**Date: **received 25 Nov 2014

**Contact author: **urszula_romanczuk at yahoo pl

**Available format(s): **PDF | BibTeX Citation

**Note: **Authors were the participants of the International Algebraic
Conference dedicated to 100-th anniversary of L. A. Kaluzhnin (July
7-12, 2014, Kyiv, Ukraine). Our paper is dedicated to the memory of
Lev Arkad'evich Kaluzhnin and his achievements in Mathematics.

**Version: **20141125:204650 (All versions of this report)

**Short URL: **ia.cr/2014/964

[ Cryptology ePrint archive ]