Cryptanalytic invertibility with finite delay of finite automata

G. P. Agibalov

Prikladnaya Diskretnaya Matematika. Supplement, no. 12 (2019), pp. 84-86.

Résumé

This conference paper is a review of the author's paper from the journal PDM, 2019, no.44 where the cryptanalytical concept of the automaton invertibility with a finite delay $\tau$ is first introduced and where some first mathematical results related to this concept are presented. The notion of cryptanalytical automaton invertibility means the theoretical possibility for recreating, under some limitations (so called clause), the prefix of a length $n$ in an unknown input sequence of an automaton, knowing its output sequence of the length $n+\tau$ and perhaps an additional information such as initial, intermediate or final state of the automaton and the suffix of a length $\tau$ in its input sequence. The limitations imposed on the recreating action may require for the initial state and for the suffix in the input sequence to be arbitrary or existent. As for prefix under recreating, it is not restricted and can be just arbitrary. So, the 208 different types of the automaton invertibility are defined at all. The early known types, (strong) invertibility and weak invertibility, are among them. Each type of the automaton invertibility with a fixed delay defines a class of all the finite automata invertible of this type. It is shown that the set of all these classes partially ordered by the inclusion relation is the union of twenty nine lattices. A constructive necessary condition for an automaton to be invertible of any invertibility type with a finite delay is established. In the case of universal invertibility type where initial state and input suffix are arbitrary, this condition is a constructive test of invertibility, that is, it is both necessary and sufficient condition for an automaton to be invertible of universal type.

Détail

Keywords: finite-state automata, information-lossless automata, automaton invertibility, cryptanalytical invertibility.

Bibliographie

[1] Agibalov G. P., “Cryptanalytic concept of finite automaton invertibility with finite delay”, Prikladnaya diskretnaya matematika, 2019, no. 44, 34–42

[2] Agibalov G. P., “Konechnye avtomaty v kriptografii”, Prikladnaya diskretnaya matematika. Prilozhenie, 2009, no. 2, 43–73

[3] Tao R., Finite Automata and Application to Cryptography, Springer, N.Y., 2009, 406 pp. | MR