# On the invertibility of finite linear transducers

Ivone Amorim; António Machiavelo; Rogério Reis

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications (2014)

- Volume: 48, Issue: 1, page 107-125
- ISSN: 0988-3754

## Access Full Article

top## Abstract

top## How to cite

topAmorim, Ivone, Machiavelo, António, and Reis, Rogério. "On the invertibility of finite linear transducers." RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications 48.1 (2014): 107-125. <http://eudml.org/doc/273027>.

@article{Amorim2014,

abstract = {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.},

author = {Amorim, Ivone, Machiavelo, António, Reis, Rogério},

journal = {RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications},

keywords = {linear transducers; invertibility of transducers; automata based cryptography; transducer injectivity with delay},

language = {eng},

number = {1},

pages = {107-125},

publisher = {EDP-Sciences},

title = {On the invertibility of finite linear transducers},

url = {http://eudml.org/doc/273027},

volume = {48},

year = {2014},

}

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

PB - EDP-Sciences

VL - 48

IS - 1

SP - 107

EP - 125

AB - 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.

LA - eng

KW - linear transducers; invertibility of transducers; automata based cryptography; transducer injectivity with delay

UR - http://eudml.org/doc/273027

ER -

## References

top- [1] W. Diffie, The First Ten Years of Public-Key Cryptography. Proc. IEEE76 (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. Zbl0921.68061MR1694161
- [3] N. Jacobson, Basic Algebra I.W H Freeman & Co (1985). Zbl0557.16001MR780184
- [4] J.L. Massey and M.K. Slain, Inverses of Linear Sequential Circuits. IEEE Trans. Comput. C-17 (1968) 330–337. Zbl0169.01501
- [5] A. Nerode, Linear Automaton Transformations. Proc. Amer. Math. Soc.9 (1958) 541–544. Zbl0089.33403MR135681
- [6] M. Newman, Integral Matrices. Academic Press (1972). Zbl0254.15009MR340283
- [7] R. Tao, Invertible Linear Finite Automata. Sci. Sinica XVI (1973) 565–581. Zbl0341.94027MR439478
- [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. Zbl0654.68055MR1023656
- [9] R. Tao, Finite Automata and Application to Cryptography. Springer Publishing Company, Incorporated (2009). Zbl1157.68044MR2648095
- [10] R. Tao and S. Chen, A Finite Automaton Public Key Cryptosystem and Digital Signatures. Chinese J. Comput. 8 (1985) 401–409. (in Chinese). Zbl0956.94011MR829320
- [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. Zbl1020.68505MR1713625
- [13] R. Tao, S. Chen and C. Xuemei, FAPKC3: A New Finite Automaton Public Key Cryptosystem. J. Comput. Sci. Techn.12 (1997) 289–305. MR1464072
- [14] G. Villard, Generalized subresultants for computing the Smith normal form of polynomial matrices. J. Symb. Comput.20 (1995) 269–286. Zbl0851.68048MR1378100
- [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. Zbl0855.68063MR1409105
- [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. Zbl0930.94035MR1727920
- [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. Zbl0881.68080MR1465544

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.