Technical Report: DCC-2014-03

On the Number of Non-Equivalent Linear Transducers

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

DCC & FCUP, Centro de Matemática da Universidade do Porto
R. Campo Alegre 687, 4169-007 Porto, Portugal
e-mail: ivone.amorim@dcc.fc.up.pt,ajmachia@fc.up.pt,rvr@dcc.fc.up.pt
March 2014

Abstract

The notion of Linear finite transducer (LFT) play 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 conducted towards the counting and enumeration of these transducers, which is essential to verify if the size of the key space, of the aforementioned systems, is large enough to prevent a 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 begin by giving a method to verify if two LFTs are equivalent, and prove that every LFT has exactly one equivalent canonical transducer. 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, and deduce a recurrence relation to count the number of equivalence classes.