Geodesic
Problems in theory of cryptanalytical invertibility of finite automata
Prikladnaâ diskretnaâ matematika, no. 4 (2020), pp. 62-71.

Voir la notice de l'article provenant de la source Math-Net.Ru

The paper continues an investigation of the cryptanalytical invertibility concept of finite automata with a finite delay introduced by the author in his previous papers where he also gave a constructive set theory test for an automaton $A$ to be cryptanalytically invertible, 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$ known to cryptanalysts, defining a type of its invertibility and of its recovering functon. Here, we expound a test for that of another kind, namely some logical necessary and sufficient conditions for an automaton $A$ to have or not a recovering function $f$ of a certain type. Results related to specific types of automata invertibility (invertibility tests, inversion algorithms, synthesis of inverse automata and others) are subjects of further researching and publications.
Keywords: finite automata, information-lossless automata, automata invertibility, recovering function, cryptanalytical invertibility, cryptanalytical invertibility conditions. 
@article{PDM_2020_4_a3,
     author = {G. P. Agibalov},
     title = {Problems in theory of cryptanalytical invertibility of finite automata},
     journal = {Prikladna\^a diskretna\^a matematika},
     pages = {62--71},
     publisher = {mathdoc},
     number = {4},
     year = {2020},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/PDM_2020_4_a3/}
}
TY  - JOUR
AU  - G. P. Agibalov
TI  - Problems in theory of cryptanalytical invertibility of finite automata
JO  - Prikladnaâ diskretnaâ matematika
PY  - 2020
SP  - 62
EP  - 71
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/PDM_2020_4_a3/
LA  - en
ID  - PDM_2020_4_a3
ER  - 
%0 Journal Article
%A G. P. Agibalov
%T Problems in theory of cryptanalytical invertibility of finite automata
%J Prikladnaâ diskretnaâ matematika
%D 2020
%P 62-71
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/PDM_2020_4_a3/
%G en
%F PDM_2020_4_a3
G. P. Agibalov. Problems in theory of cryptanalytical invertibility of finite automata. Prikladnaâ diskretnaâ matematika, no. 4 (2020), pp. 62-71. http://geodesic.mathdoc.fr/item/PDM_2020_4_a3/

[1] D. A. Huffman, “Canonical forms for information-lossles finite-state logical machines”, IRE Trans. Circuit Theory, 6, spec. suppl. (1959), 41–59

[2] D. A. Huffman, “Notes on information-lossles finite-state automata”, Nuovo Cimento, 13, suppl. 2 (1959), 397–405

[3] A. Gill, Introduction to the Theory of Finite-State Machines, McGraw-Hill Book Company, N.Y., 1962, 300 pp.

[4] Sh. Even, “On information-lossles automata of finite order”, IEEE Trans. Electron. Comput., 14:4 (1965), 561–569

[5] A. A. Kurmit, Information Lossless Automata of Finite Order, John Wiley, N.Y., 1974

[6] A. D. Zakrevskiy, “The method for messages automatic encryption”, Prikladnaya Diskretnaya Matematika, 2009, no. 2 (4), 127–137 (in Russian)

[7] Z. D. Dai, D. F. Ye, K. Y. Lam, “Weak invertibility of finite automata and cryptanalysis on FAPKC”, LNCS, 1514, 1998, 227–241

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

[9] G. P. Agibalov, “Cryptanalytic concept of finite automaton invertibility with finite delay”, Prikladhaya Diskrethaya Matematika, 2019, no. 44, 34–42

[10] G. P. Agibalov, “Cryptanalytical finite automaton invertibility with finite delay”, Prikladnaya Diskretnaya Matematika, 2019, no. 46, 27–37