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

  • Authors

    • Nacer Ghadbane Laboratory of Pure and Applied Mathematics , Departmentof Mathematics, University of MÂ’sila, Algeria
    • Douadi Mihoubi Laboratory of Pure and Applied Mathematics , Department of Mathematics, University of MÂ’sila, Algeria
    2016-09-17
    https://doi.org/10.14419/ijamr.v5i4.6204
  • Free monoid, Thue system, Morphism monoids, The closure of a binary relation, The word problem in a monoid, Public Key Cryptography.
  • 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.

  • References

    1. [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).

  • Downloads

  • How to Cite

    Ghadbane, N., & Mihoubi, D. (2016). Some attacks of an encryption system based on the word problem in a monoid. International Journal of Applied Mathematical Research, 5(4), 158-161. https://doi.org/10.14419/ijamr.v5i4.6204