Cryptanalytic concept of finite automaton invertibility with finite delay | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2019. № 44. DOI: 10.17223/20710410/44/3

The automaton invertibility with a finite delay plays a very important analysis and synthesis of finite automata cryptographic systems. The cryptanalitic invertibility with a finite delay т is studied in the paper. cryptanalyst's point of view, this notion means the theoretical possibility for recove ring, under some conditions, a prefix a of a length n in an unknown input sequence a6 of an automaton from its output sequence y of the length n + т and perhaps an additional information such as parameters т and n, initial (q), intermediate (0) or final (t) state of the automaton or the suffix 6 of the length т in the input sequence. The conditions imposed on the recovering algorithm require for prefix a to be arbitrary and may require for the initial state q and suffix 6 to be arbitrary or existent, that is, the variable a is always bound by the universal quantifier and each of variables q and 6 may be bound by any of quantifiers - universal (V) or existential (3) one. The variety of information, which can be known to a cryptanalyst, provides many different types of the automaton invertibility and, respectively, many different classes of invertible automata. Thus, in the paper, an invertibility with a finite delay т of a finite automaton A is the ability of this automaton to resist recovering or, on the contrary, to allow precise determining any input word a of a length n for the output word y being the result of transforming by the automaton A in its initial state q the input word a6 with the 6 of length т and with the known n, т, A, y and и C {6, q, 0, t} where q and 6 may be arbitrary or some elements in their sets and 0 and t are respectively intermediate and final states of A into which A comes from q under acting of input words a and a6 respectively. According to this, the automaton A is called invertible with a delay т if there exists a function f (y,u) and a triplet of quantifiers к 6 {Q1x1Q2x2Q3x3 : Qixi 6 {Vq, 3q, Va, V6, 36}, i = j x, = Xj} such that K[f(y,u) = a]; in this case f is called a recovering function, (к,и) - an invertibility type, к - an invertibility degree, u - an invertibility order of the automaton A and 3f K[f (y, u) = a] - an invertibility condition of type (к, u) for the automaton A. So, 208 different types of the automaton A invertibility are defined at all. The well known types of (strong) invertibility and weak invertibility described for finite automata earlier by scientists (D. A. Huffman, A. Gill, Sh. Even, A. A. Kurmit, Z. D. Dai, D. F. Ye, K. Y. Lam, R. Tao and many others) in our theory belong to types (VqVaV6, 0) and (VqVaV6, {q}) respectively. For every invertibility type, we have defined a class of automata with this type of invertibility and described the inclusion relation on the set of all these classes. It has turned out that the graph of this relation is the union of twenty nine lattices with thirteen of them each containing sixteen classes and sixteen lattices each containing thirteen classes. To solve the scientific problems (invertability tests, synthesis of inverse automata and so on) related to the different and concrete invertibility classes, we hope to continue these investigations.
Download file
Counter downloads: 134
  • Title Cryptanalytic concept of finite automaton invertibility with finite delay
  • Headline Cryptanalytic concept of finite automaton invertibility with finite delay
  • Publesher Tomask State UniversityTomsk State University
  • Issue Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics 44
  • Date:
  • DOI 10.17223/20710410/44/3
Keywords
finite automata, information-lossless automata, automata invertibility, cryptanalytic invertibility, конечные автоматы, автоматы без потери информации, обратимость автоматов, криптаналитическая обратимость
Authors
References
Huffman D. A. Canonical forms for information-lossless finite-state logical machines. IRE Trans. Circuit Theory, 1959, vol. 6, Spec. Suppl., pp. 41-59
Huffman D. A. Notes on information-lossless finite-state automata. Nuovo Cimento, 1959, vol. 13, Suppl. 2, pp. 397-405
Gill A. Introduction to the Theory of Finite-State Machines. N.Y., McGraw-Hill Book Company, 1962. 300 p
Even Sh. On information-lossless automata of finite order. IEEE Trans. Electron. Comput., 1965, vol. 14, no. 4, pp. 561-569
Kurmit A. A. Information Lossless Automata of Finite Order. N.Y., John Wiley Publ., 1974
Zakrevskiy A. D. Metod avtomaticheskoy shifratsii soobshcheniy [The method for messages automatic encryption]. Prikladnaya Diskretnaya Matematika, 2009, no. 2(4), pp. 127-137. (in Russian)
Agibalov G. P. Konechnye avtomati v kriptografii [Finite automata in cryptography]. Prikladnaya Diskretnaya Matematika. Prilojenie, 2009, no. 2, pp. 43-73. (in Russian)
Dai Z. D., Ye D. F., and Lam K. Y. Weak invertibility of finite automata and cryptanalysis on FAPKC. LNCS, 1998, vol. 1514, pp. 227-241
Tao R. Finite Automata and Application to Cryptography. N.Y., Springer, 2009. 406 p
 Cryptanalytic concept of finite automaton invertibility with finite delay | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2019. № 44. DOI: 10.17223/20710410/44/3
Cryptanalytic concept of finite automaton invertibility with finite delay | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2019. № 44. DOI: 10.17223/20710410/44/3
Download full-text version
Counter downloads: 365