On the invertibility of finite linear transducers
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 48 (2014) no. 1, pp. 107-125.

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.

DOI : 10.1051/ita/2014004
Mots-clés : linear transducers, invertibility of transducers, automata based cryptography, transducer injectivity with delay 
@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},
     pages = {107--125},
     publisher = {EDP-Sciences},
     volume = {48},
     number = {1},
     year = {2014},
     doi = {10.1051/ita/2014004},
     mrnumber = {3195791},
     language = {en},
     url = {http://www.numdam.org/articles/10.1051/ita/2014004/}
}
TY  - JOUR
AU  - Amorim, Ivone
AU  - Machiavelo, António
AU  - Reis, Rogério
TI  - On the invertibility of finite linear transducers
JO  - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY  - 2014
SP  - 107
EP  - 125
VL  - 48
IS  - 1
PB  - EDP-Sciences
UR  - http://www.numdam.org/articles/10.1051/ita/2014004/
DO  - 10.1051/ita/2014004
LA  - en
ID  - ITA_2014__48_1_107_0
ER  - 
%0 Journal Article
%A Amorim, Ivone
%A Machiavelo, António
%A Reis, Rogério
%T On the invertibility of finite linear transducers
%J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
%D 2014
%P 107-125
%V 48
%N 1
%I EDP-Sciences
%U http://www.numdam.org/articles/10.1051/ita/2014004/
%R 10.1051/ita/2014004
%G en
%F 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) no. 1, pp. 107-125. doi : 10.1051/ita/2014004. http://www.numdam.org/articles/10.1051/ita/2014004/

[1] W. Diffie, The First Ten Years of Public-Key Cryptography. Proc. IEEE 76 (1988) 560-577.

[2] O. Haiwen and D. Zongduo, Self-Injective Rings and Linear (Weak) Inverses of Linear Finite Automata over Rings. Science in China, Series A 42 (1999) 140-146. | MR | Zbl

[3] N. Jacobson, Basic Algebra I. W H Freeman & Co (1985). | MR | Zbl

[4] J.L. Massey and M.K. Slain, Inverses of Linear Sequential Circuits. IEEE Trans. Comput. C-17 (1968) 330-337. | Zbl

[5] A. Nerode, Linear Automaton Transformations. Proc. Amer. Math. Soc. 9 (1958) 541-544. | MR | Zbl

[6] M. Newman, Integral Matrices. Academic Press (1972). | MR | Zbl

[7] R. Tao, Invertible Linear Finite Automata. Sci. Sinica XVI (1973) 565-581. | MR | Zbl

[8] R. Tao, 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 | Zbl

[9] R. Tao, Finite Automata and Application to Cryptography. Springer Publishing Company, Incorporated (2009). | MR | Zbl

[10] R. Tao and S. Chen, A Finite Automaton Public Key Cryptosystem and Digital Signatures. Chinese J. Comput. 8 (1985) 401-409. (in Chinese). | MR | Zbl

[11] R. Tao and S. Chen, A Variant of the Public Key Cryptosystem FAPKC3. J. Netw. Comput. Appl. 20 (1997) 283-303.

[12] R. Tao and S. Chen, The Generalization of Public Key Cryptosystem FAPKC4. Chinese Sci. Bull. 44 (1999) 784-790. | MR | Zbl

[13] R. Tao, S. Chen and C. Xuemei, FAPKC3: A New Finite Automaton Public Key Cryptosystem. J. Comput. Sci. Techn. 12 (1997) 289-305. | MR

[14] G. Villard, Generalized subresultants for computing the Smith normal form of polynomial matrices. J. Symb. Comput. 20 (1995) 269-286. | MR | Zbl

[15] D. Zongduo and Y. Dingfengd, Weak Invertibility of Linear Finite Automata I, Classification and Enumeration of Transfer Functions. Sci. In China (Series A) 39 (1996) 613-623. | MR | Zbl

[16] D. Zongduo, Y. Dingfeng and K.Y. Lam, 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 | Zbl

[17] D. Zongduo, Y. Dingfengd, Z. Qibin and O. Haiwen, Classification and Enumeration of Matched Free Response Matrices of Linear Finite Automata. Acta Math. Sinica, New Ser. 13 (1997) 133-144. | MR | Zbl

Cité par Sources :