Some attacks of an encryption system based on the word problem in a monoid

 
 
 
  • Abstract
  • Keywords
  • References
  • PDF
  • Abstract


    In this work, we are interested in ATS-monoid protocol proposed by P. J. Abisha, D. G. Thomas G. and K. Subramanian}, the idea of this protocol is to transform a system of Thue \(S_{1}=\left( \Sigma ,R\right) \) for which the word problem is undecidable a system of Thue  \(S_{2}=\left( \Delta ,R_{\theta }\right)\) or \(\theta \subseteq \Delta \times\Delta \) for which the word problem is decidable in linear time.
    Specifically, it gives attacks against ATS monoid in spesifiques case and thenme examples of these cases.


  • Keywords


    Free monoid, Thue system, Morphism monoids, The closure of a binary relation, The word problem in a monoid, Public Key Cryptography.

  • References


      [1] A. Ali, P et N. Hadj. S, "La Cryptographie et ses Principaux Systèmes de Références," RIST, no 4, (2002).

      [2] Benois, "Application de l'étude de certaines congruences à un problème de décidabilité," Séminaire Dubreil , no 7, (1972).

      [3] R. Cori et D. Perrin, "Automates et Commutations Partielles," RAIRO-Informatique théorique, tome19, no 1, p.21-32, (1985).

      [4] W. Diffie, M. E. Hellman, "New Direction in Cryptography," IEEE Trans, on Inform Theory, 22(6), P. 644-665, (1976).

      [5] M. Eytan, G. TH, "Guilbaud. Présentation de quelques monoïdes finis. Mathématiques et sciences humaines," tome 7, p. 3-10, (1964).

      [6] R. Floyd, R. Beigel, "Traduction de D. Krob. Le langage des machines," International Thomthenn France, Paris, (1995).

      [7] Y. Lafont, "Réécritue et problème du mot," Gazette des Mathématiciens, Laboratoire de Mathématiques Discrètes de Luminy, Marseille, France, (2009).

      [8] A. Markov, "On the impossibility of certain algorithme in the theory of asthenciative systems, » Doklady Akademi Nauk SSSR,55, 58:587-590, 353-356, (1947).

      [9] Y. Metiver, "Calcul de longueurs de chaines de réécriture dans un monoïde libre," U.E.R. de Mathématiques et informatique, Université de Bordeaux 1, France (1983).

      [10] M. Nivat, "Sur le noyau d'un morphisme du monoïde libre," Séminaire Schutzenberger, tom 1, no 4, p, 1-6, (1970).

      [11] L. Perret, "Etude d'outils algébriques et combinatoires pour la cryptographie à clef publique," thèse de doctorat, Universit´e de Marne-la-Vallée, (2005).

      [12] H. Phan, P. Guillot," Preuves de sécurité des schémas cryptographiques," université Paris 8, (2013).

      [13] E. Post, "Recursive unthenlvability of a problem of Thue,", Journal of Symbolic Logic, 12(1):1-11, (1947).

      [14] S. Qiao, W. Han, Y. Li and L. Jiao, "Construction of Extended Multivariante Public Key Cryptosystems," International Journal of Network Security, Vol. 18, No.1, pp. 60-67, (2016).

      [15] H. Rosen, "Cryptography Theory and Practice," Third Edition, Chapman and Hall/CRC, (2006).

      [16] R. V. Book, H. N. Liu, "Rewriting Systems and Word Problems in a Free Partially Commutative Monoid," Information Processing Letters no 26, p. 29-32, (1987).


 

View

Download

Article ID: 6204
 
DOI: 10.14419/ijamr.v5i4.6204




Copyright © 2012-2015 Science Publishing Corporation Inc. All rights reserved.