ON THE INVERTIBILITY OF FINITE LINEAR TRANSDUCERS

• Type: Article in International Scientific Journal
• Date: 2014

Authors

Ivone Amorim (Author) Other; Antonio Machiavelo (Author) FCUP; Rogerio Reis (Author) FCUP

Journal

Title: RAIRO - Theoretical Informatics and Applications

Vol. 48

Pages: 107-125

ISSN: 0988-3754

Publisher: EDP Sciences

Indexing

ISI Web of Knowledge - 3 Citations

Scopus - 3 Citations

Scientific classification

FOS: Natural sciences > Computer and information sciences

Other information

Authenticus ID: P-009-8JN

DOI: 10.1051/ita/2014004

Abstract (EN): 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.

Language: English

Type (Professor's evaluation): Scientific

No. of pages: 19