On Public Key Cryptosystems Based On Thue Monoid Morphism Interpretation (tmmi)

Résumé: The asymmetric encryption methods are based on difficult problems in mathematics. Let Σ^* be the free monoid over a finite alphabet Σ and R a binary relation on Σ^*. The pair (Σ,R) is called a Thue system. The congruence generated by R is defined as follows: xuy⟷_R xvy, whenever x,y∈Σ^*and uRv or vRu. w〖⟷_R〗^* w', whenever u_0,u_1,…,u_n∈Σ^*with, u_0=w,u_i ⟷_R u_(i+1),∀0≤i≤n-1,u_n=w^'. The word problem for R on Σ^* is then following : given two words w_1,w_2∈Σ^*, do we have〖 w〗_1 〖⟷_R〗^* w_2 ? [7] In this paper we investigate on a public key cryptosystems based on the difficult word problem in free monoid, introduced by Wagner and Magyarik in 1985. It's well known that the word problem is undecidable in general, meaning that there is no algorithm to solve it. We introduce some cryptosystems based on the Thue Monoid Morphism Interpresentation where the word problem is decidable in linear time.

Publié dans la revue: Revue de l'Information Scientifique et Technique