Revue de l'Information Scientifique et Technique
Volume 24, Numéro 1, Pages 31-38
2019-05-22
On Public Key Cryptosystems Based On Thue Monoid Morphism Interpretation (tmmi)
Authors : Nacer Ghadbane .
Abstract
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.
Keywords
Free monoid, Thue system, Finitely presented monoids, Word problem in monoid, Public key cryptography
Les articles similaires
بن دراح زهرة
.
بوهنوش فاطمة
.
ص 284-294.
برحايل بودودة شريفة
.
بن موسى زين الدين
.
ص 408-426.
