On desynchronised El Gamal algorithm

Vasyl Ustimenko

Paper 2017/712

On desynchronised El Gamal algorithm

Vasyl Ustimenko

Abstract

Families of stable cyclic groups of nonlinear polynomial transformations of affine spaces $K^{n}$ over general commutative ring $K$ of increasing with $n$ order can be used in the key exchange protocols and related to them El Gamal multivariate cryptosystems. We suggest to use high degree of noncommutativity of affine Cremona group and modify multivariate El Gamal algorithm via the usage of conjugations for two polynomials of kind $g^{k}$ and $g^{- 1}$ given by key holder (Alice) or giving them as elements of different transformation groups. We present key exchange protocols based on twisted discrete logarithms problem which uses noncommutativity of semigroup. Recent results on the existence of families of stable transformations of prescribed degree and density and exponential order over finite fields can be used for the implementation of schemes as above with feasible computational complexity. We introduce an example of a new implemented quadratic multivariate cryptosystem based on the above mentioned ideas.

Note: Part of paper content were presented at CECC2016 and CECC2017

Metadata

Available format(s): PDF
Publication info: Preprint. MINOR revision.
Keywords: Multivariate Cryptography stable transformations shifted multivariate El Gamal algorithm desyncronisation diagram
Contact author(s): vasyl @ hektor umcs lublin pl
History: 2017-07-27: received
Short URL: https://ia.cr/2017/712
License: CC BY

BibTeX

@misc{cryptoeprint:2017/712,
      author = {Vasyl Ustimenko},
      title = {On desynchronised El Gamal algorithm},
      howpublished = {Cryptology {ePrint} Archive, Paper 2017/712},
      year = {2017},
      url = {https://eprint.iacr.org/2017/712}
}