Paper 2014/964

On two windows multivariate cryptosystem depending on random parameters

Urszula Romańczuk-Polubiec and 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.

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.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Preprint.
Keywords
CryptosystemMultivariate cryptographyPostquantum cryptographyAlgebraic incidence structurePseudorandom sequencesPseudorandom walk in graph
Contact author(s)
urszula_romanczuk @ yahoo pl
History
2014-11-25: received
Short URL
https://ia.cr/2014/964
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2014/964,
      author = {Urszula Romańczuk-Polubiec and Vasyl Ustimenko},
      title = {On two windows multivariate cryptosystem depending on random parameters},
      howpublished = {Cryptology ePrint Archive, Paper 2014/964},
      year = {2014},
      note = {\url{https://eprint.iacr.org/2014/964}},
      url = {https://eprint.iacr.org/2014/964}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.