Counting Equivalent Linear Finite Transducers Using a Canonical Form

• Tipo: Artigo em Livro de Atas de Conferência Internacional
• Data: 2014

Autores

Ivone Amorim (Autor) Outra; Antonio Machiavelo (Autor) FCUP; Rogerio Reis (Autor) FCUP

Ata de Conferência Internacional

Título: IMPLEMENTATION AND APPLICATION OF AUTOMATA, CIAA 2014

Páginas: 70-83

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

Giessen, GERMANY, JUL 30-AUG 02, 2014

Indexação

ISI Web of Knowledge - 1 Citação

Scopus - 0 Citações

Classificação Científica

FOS: Ciências exactas e naturais > Ciências da computação e da informação

Outras Informações

ID Authenticus: 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.

Idioma: Inglês

Tipo (Avaliação Docente): Científica

Nº de páginas: 14