On a public-key cryptosystem based on iterated morphisms and substitutions (Q1098821)

\textit{A. Salomaa} and \textit{E. Welzl} [A cryptographic trapdoor based on iterated morphisms, Manuscript (1983)] introduced a public-key cryptosystem based on L systems as follows. First choose a DTOL system \(G=(\Sigma,h_ 0,h_ 1,w)\) which is backward deterministic, i.e., \((w)i_ 0...i_ n=(w)j_ 0...j_ m\) yields \(i_ 0...i_ n=j_ 0...j_ m\), for each i and j in \(\{h_ 0,h_ 1\}\). Next choose an alphabet \(\Delta\) of a much greater cardinality than \(\Sigma\), and a morphism \(g:\Delta^*\to \Sigma^*\) mapping every letter to a letter or the empty word such that \(g^{-1}(a)\) is nonempty for a in \(\Sigma\). Define two finite substitutions \(\sigma_ 0\) and \(\sigma_ 1\) on \(\Delta^*\) by letting \(\sigma_ i(d)\) be a finite nonempty subset of \(g^{-1}(h_ i(g(d)))\) for all d in \(\Delta\), \(i=0,1\). Choose u from \(g^{-1}(w)\). Then the TOL system \(H=(\Delta,\sigma_ 0,\sigma_ 1,u)\) is the public key and (G,g) is the secret key. The cryptotext of binary sequence \(i_ 0...i_ n\) is an arbitrary word in \((u)\sigma_{i_ 0}...\sigma_{i_ n}\). This system was further investigated by \textit{J. Dassow} [A note on DTOL systems, Tech. Rep., Techn. Univ. Magdeburg (1984)], \textit{T. Baunwall}, \textit{P. Bertelsen} and \textit{S. Weibel} [An analysis of the Salomaa system, Tech. Rep., Dep. Comput. Sci., Aarhus Univ. (1986)], and \textit{K. G. Subramanian}, \textit{R. Siromoney} and \textit{P. J. Abisha} [A DOL-TOL public key cryptosystem, Inf. Process. Lett. 26, 95-97 (1987)]. This paper gives a further investigation of this cryptosystem, both from mathematical and cryptanalytic point of view. The results are promising in the sense that cryptanalysis seems to be very difficult and the system seems to work in a proper way also with respect to encryption, decryption, word length, etc.