Paper 2021/1466

On semigroups of multivariate transformations constructed in terms of time dependent linguistic graphs and solutions of Post Quantum Multivariate Cryptography.

V. Ustimenko

Abstract

Time dependent linguistic graphs over abelian group H are introduced. In the case $H=K*$ such bipartite graph with point set $P=H^n$ can be used for generation of Eulerian transformation of $(K*)^n$, i.e. the endomorphism of $K[x_1, x_2,… , x_n]$ sending each variable to a monomial term. Subsemigroups of such endomorphisms together with their special homomorphic images are used as platforms of cryptographic protocols of noncommutative cryptography. The security of these protocol is evaluated via complexity of hard problem of decomposition of Eulerian transformation into the product of known generators of the semigroup. Nowadays the problem is intractable one in the Postquantum setting. The symbiotic combination of such protocols with special graph based stream ciphers working with plaintext space of kind $K^m$ where $m=n^t$ for arbitrarily chosen parameter $t$ is proposed. This way we obtained a cryptosystem with encryption/decryption procedure of complexity $O(m^{1+2/t})$.

Note: We present protocol based cryptosystem which is not a public key algorithm.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Preprint. MINOR revision.
Keywords
Post Quantum CryptographyComputer Algebratime dependent algebraic graphsaffine Cremona semigroupEulerian transformations
Contact author(s)
vasyl @ hektor umcs lublin pl
History
2021-11-06: received
Short URL
https://ia.cr/2021/1466
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2021/1466,
      author = {V.  Ustimenko},
      title = {On semigroups of multivariate transformations constructed in terms of time dependent linguistic graphs and solutions of Post Quantum Multivariate Cryptography.},
      howpublished = {Cryptology ePrint Archive, Paper 2021/1466},
      year = {2021},
      note = {\url{https://eprint.iacr.org/2021/1466}},
      url = {https://eprint.iacr.org/2021/1466}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.