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

Abstract

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

How to cite

top

Amorim, 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. [1] W. Diffie, The First Ten Years of Public-Key Cryptography. Proc. IEEE76 (1988) 560–577. 
  2. [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. [3] N. Jacobson, Basic Algebra I.W H Freeman & Co (1985). Zbl0557.16001MR780184
  4. [4] J.L. Massey and M.K. Slain, Inverses of Linear Sequential Circuits. IEEE Trans. Comput. C-17 (1968) 330–337. Zbl0169.01501
  5. [5] A. Nerode, Linear Automaton Transformations. Proc. Amer. Math. Soc.9 (1958) 541–544. Zbl0089.33403MR135681
  6. [6] M. Newman, Integral Matrices. Academic Press (1972). Zbl0254.15009MR340283
  7. [7] R. Tao, Invertible Linear Finite Automata. Sci. Sinica XVI (1973) 565–581. Zbl0341.94027MR439478
  8. [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. [9] R. Tao, Finite Automata and Application to Cryptography. Springer Publishing Company, Incorporated (2009). Zbl1157.68044MR2648095
  10. [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. [11] R. Tao and S. Chen, A Variant of the Public Key Cryptosystem FAPKC3. J. Netw. Comput. Appl.20 (1997) 283–303. 
  12. [12] R. Tao and S. Chen, The Generalization of Public Key Cryptosystem FAPKC4. Chinese Sci. Bull.44 (1999) 784–790. Zbl1020.68505MR1713625
  13. [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. [14] G. Villard, Generalized subresultants for computing the Smith normal form of polynomial matrices. J. Symb. Comput.20 (1995) 269–286. Zbl0851.68048MR1378100
  15. [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. [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. [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 ?

top

You must be logged in to post comments.

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.