On Linear Finite Automata and Cryptography

✍ Scribed by Amorim I., Machiavelo A., Reis R.

• Tongue: English
• Leaves: 15
• Category: Library

✦ Synopsis

Доклад. Technical Report Series: DCC-2011-
11. Departamento de Ciencia de Computadores.

Finite automata public-key cryptosystems rely upon characterizations of some types of invertible finite automata, and methods of obtain them as well as their respective inverses. In this paper we provide a much needed clarification of Tao’s formalization and basic results on the subject, as well as a new condition for a linear finite automata with memory to be weakly invertible with delay τ . This last result, employing an approach with formal series, uses the Smith’s normal form of a polynomial matrix. The proof of the results presented here provides a new way to construct an inverse with delay τ of an invertible linear finite automata.

✦ Subjects

Информатика и вычислительная техника;Информационная безопасность;Криптология и криптография