Linear finite transducers underlie a series of schemes for Public Key Cryptography (PKC) proposed in the 90s of the last century. The uninspiring and arid language then used, condemned these works to oblivion. Although some of these schemes were afterwards shown to be insecure, the promise of a new system of PKC relying on different complexity assumptions is still quite exciting. The algorithms there used depend heavily on the results of invertibility of linear transducers. In this paper we introduce the notion of post-initial linear transducer, which is an extension of the notion of linear finite transducer with memory, and for which the previous fundamental results on invertibility still hold. This extension enabled us to give a new method to obtain a left inverse of any invertible linear finite transducer with memory. It also plays an essencial role in the necessary and sufficient condition that we give for left invertibility of linear finite transducers.
@article{ITA_2014__48_1_107_0,
author = {Amorim, Ivone and Machiavelo, Ant\'onio and Reis, Rog\'erio},
title = {On the invertibility of finite linear transducers},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
volume = {48},
year = {2014},
pages = {107-125},
doi = {10.1051/ita/2014004},
mrnumber = {3195791},
language = {en},
url = {http://dml.mathdoc.fr/item/ITA_2014__48_1_107_0}
}
Amorim, Ivone; Machiavelo, António; Reis, Rogério. On the invertibility of finite linear transducers. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 48 (2014) pp. 107-125. doi : 10.1051/ita/2014004. http://gdmltest.u-ga.fr/item/ITA_2014__48_1_107_0/
[1] , The First Ten Years of Public-Key Cryptography. Proc. IEEE 76 (1988) 560-577.
[2] and , Self-Injective Rings and Linear (Weak) Inverses of Linear Finite Automata over Rings. Science in China, Series A 42 (1999) 140-146. | MR 1694161 | Zbl 0921.68061
[3] , W H Freeman & Co (1985). | MR 780184 | Zbl 0557.16001
[4] and , Inverses of Linear Sequential Circuits. IEEE Trans. Comput. C-17 (1968) 330-337. | Zbl 0169.01501
[5] , Linear Automaton Transformations. Proc. Amer. Math. Soc. 9 (1958) 541-544. | MR 135681 | Zbl 0089.33403
[6] , Integral Matrices. Academic Press (1972). | MR 340283 | Zbl 0254.15009
[7] , Invertible Linear Finite Automata. Sci. Sinica XVI (1973) 565-581. | MR 439478 | Zbl 0341.94027
[8] , Invertibility of Linear Finite Automata Over a Ring. Automata, Languages and Programming, in vol. 317 of Lect. Notes Comput. Sci. Springer Berlin, Heidelberg (1988) 489-501. | MR 1023656 | Zbl 0654.68055
[9] , Finite Automata and Application to Cryptography. Springer Publishing Company, Incorporated (2009). | MR 2648095 | Zbl 1157.68044
[10] and , A Finite Automaton Public Key Cryptosystem and Digital Signatures. Chinese J. Comput. 8 (1985) 401-409. (in Chinese). | MR 829320 | Zbl 0956.94011
[11] and , A Variant of the Public Key Cryptosystem FAPKC3. J. Netw. Comput. Appl. 20 (1997) 283-303.
[12] and , The Generalization of Public Key Cryptosystem FAPKC4. Chinese Sci. Bull. 44 (1999) 784-790. | MR 1713625 | Zbl 1020.68505
[13] , and , FAPKC3: A New Finite Automaton Public Key Cryptosystem. J. Comput. Sci. Techn. 12 (1997) 289-305. | MR 1464072
[14] , Generalized subresultants for computing the Smith normal form of polynomial matrices. J. Symb. Comput. 20 (1995) 269-286. | MR 1378100 | Zbl 0851.68048
[15] and , Weak Invertibility of Linear Finite Automata I, Classification and Enumeration of Transfer Functions. Sci. In China (Series A) 39 (1996) 613-623. | MR 1409105 | Zbl 0855.68063
[16] , and , Weak Invertibility of Finite Automata and Cryptanalysis on FAPKC. Advances in Cryptology - AsiaCrypt'98, in vol. 1514 of Lect. Notes Comput. Sci. Edited by K. Ohta and D. Pei. Springer-Verlag (1998) 227-241. | MR 1727920 | Zbl 0930.94035
[17] , , and , Classification and Enumeration of Matched Free Response Matrices of Linear Finite Automata. Acta Math. Sinica, New Ser. 13 (1997) 133-144. | MR 1465544 | Zbl 0881.68080