Cryptology ePrint Archive: Report 2019/1130

On affine Cremona semigroups, corresponding protocols of Non-commutative Cryptography and encryption with several nonlinear multivariate transformations on secure Eulerian mode.

V. Ustimenko

Abstract: We suggest new applications of protocols of Non-commutative cryptography defined in terms of subsemigroups of Affine Cremona Semigroups over finite commutative rings and their homomorphic images to the constructions of possible instruments of Post Quantum Cryptography. This approach allows to define cryptosystems which are not public keys. When extended protocol is finished correspondents have the collision multivariate transformation on affine space K ^n or variety (K*)^n where K is a finite commutative ring and K* is nontrivial multiplicative subgroup of K . The security of such protocol rests on the complexity of word problem to decompose element of Affine Cremona Semigroup given in its standard form into composition of given generators. The collision map can serve for the safe delivery of several bijective multivariate maps F_i (generators) on K^n (or (K*)^n) from one correspondent to another. So asymmetric cryptosystem with nonpublic multivariate generators where one side (Alice) knows inverses of F_i but other does not have such a knowledge is possible. We consider the usage of single protocol or combinations of two protocols with platforms of different nature. The usage of two protocols with the collision spaces K^n and (K*)^n allows safe delivery of two sets of generators of different nature. In terms of such sets we define an asymmetric encryption scheme with the plainspace (K*)^n, cipherspace K^n and multivariate non-bijective encryption map of unbounded degree O(n) and polynomial density on K^n with injective restriction on (K*)^n. Algebraic cryptanalysis faces the problem to interpolate a natural decryption transformation which is not a map of polynomial density.

Category / Keywords: cryptographic protocols / Multivariate Cryptography, Noncommutative Cryptography, stable trans-formation groups and semigroups, semigroups of monomial transformations, word problem for nonlinear multivariate maps, hidden tame homomorphisms, key exchange protocols, cryptosystems, linguistic graphs

Date: received 1 Oct 2019

Contact author: vasyl at hektor umcs lublin pl

Available format(s): PDF | BibTeX Citation

Version: 20191002:081904 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]