Geodesic
Cryptanalytical finite automaton invertibility with finite delay
Prikladnaâ diskretnaâ matematika, no. 4 (2019), pp. 27-37
Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

The paper continues an investigation of the cryptanalytical invertibility concept with a finite delay introduced by the author for finite automata. Here, we expound an algorithmic test for an automaton $A$ to be cryptanalytically invertible with a finite delay, that is, to have a recovering function $f$ which allows to calculate a prefix of a length $m$ in an input sequence of the automaton $A$ by using its output sequence of a length $m+\tau$ and some additional information about $A$ defining a type of its invertibility and known to cryptanalysts. The test finds out whether the automaton $A$ has a recovering function $f$ or not and if it has, determines some or, may be, all of such functions. The test algorithm simulates a backtracking method for searching a possibility to transform a binary relation to a function by shortening its domain to a set corresponding to the invertibility type under consideration.
Keywords: finite automata, information-lossless automata, automata invertibility, cryptanalytical invertibility, cryptanalytical invertibility test. 
@article{PDM_2019_4_a2,
     author = {G. P. Agibalov},
     title = {Cryptanalytical finite~automaton invertibility with finite delay},
     journal = {Prikladna\^a diskretna\^a matematika},
     pages = {27--37},
     year = {2019},
     number = {4},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/PDM_2019_4_a2/}
}
TY  - JOUR
AU  - G. P. Agibalov
TI  - Cryptanalytical finite automaton invertibility with finite delay
JO  - Prikladnaâ diskretnaâ matematika
PY  - 2019
SP  - 27
EP  - 37
IS  - 4
UR  - http://geodesic.mathdoc.fr/item/PDM_2019_4_a2/
LA  - en
ID  - PDM_2019_4_a2
ER  - 
%0 Journal Article
%A G. P. Agibalov
%T Cryptanalytical finite automaton invertibility with finite delay
%J Prikladnaâ diskretnaâ matematika
%D 2019
%P 27-37
%N 4
%U http://geodesic.mathdoc.fr/item/PDM_2019_4_a2/
%G en
%F PDM_2019_4_a2
G. P. Agibalov. Cryptanalytical finite automaton invertibility with finite delay. Prikladnaâ diskretnaâ matematika, no. 4 (2019), pp. 27-37. http://geodesic.mathdoc.fr/item/PDM_2019_4_a2/

[1] Agibalov G. P., “Cryptanalytic concept of finite automaton invertibility with finite delay”, Prikladnaya Diskretnaya Matematika, 2019, no. 44, 34–42 | DOI | MR

[2] Rasiowa H., Introduction to Modern Mathematics, North-Holland Publishing Company, Amsterdam–London; PWN, Warszawa, 1973, 339 pp. | MR | Zbl

[3] Agibalov G. P., Belyaev V. A., Technology for Solving Combinatorial-Logical Problems by the Method of Shortened Search Tree Traversal, TSU Publ., Tomsk, 1981, 126 pp. (in Russian)

[4] Christofides H., Graph Theory. An algorithmic Approach., Academic Press, New York–London–San Francisco, 1975 | MR | Zbl

[5] Zakrevskij A., Pottosin Yu., Cheremisinova L., Combinatorial Algorithms of Discrete Mathematics, TUT Press, Tallinn, 2008, 193 pp.