Counting Equivalent Linear Finite Transducers Using a Canonical Form

• Type: Article in International Conference Proceedings Book
• Date: 2014

Authors

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

Conference proceedings International

Title: IMPLEMENTATION AND APPLICATION OF AUTOMATA, CIAA 2014

Pages: 70-83

19th International Conference on Implementation and Application of Automata (CIAA)

Giessen, GERMANY, JUL 30-AUG 02, 2014

Indexing

ISI Web of Knowledge - 1 Citation

Scopus - 0 Citations

Scientific classification

FOS: Natural sciences > Computer and information sciences

Other information

Authenticus ID: P-009-PNQ

DOI: 10.1007/978-3-319-08846-4_5

Abstract (EN): The notion of linear finite transducer (LFT) plays a crucial role in a family of cryptosystems introduced in the 80's and 90's. However, as far as we know, no study was ever conducted to count and enumerate these transducers, which is essential to verify if the size of the key space, of the aforementioned systems, is large enough to prevent an exhaustive search attack. In this paper, we determine the cardinal of the equivalence classes on the set of the LFTs with a given size. This result is sufficient to get an approximate value, by random sampling, for the number of non-equivalent injective LFTs, and subsequently for the size of the key space. We introduce a notion of canonical LFT, give a method to verify if two LFTs are equivalent, and prove that every LFT has exactly one equivalent canonical LFT. We then show how this canonical LFT allows us to calculate the size of each equivalence class on the set of the LFTs with the same number of states.

Language: English

Type (Professor's evaluation): Scientific

No. of pages: 14