A trapdoor cipher is a cipher whose algorithm contains some hidden structure (a trapdoor) providing the existence of a subliminal information channel. In cryptographic practice, there could be situations when a constructed cipher may contain some critical defect (a trapdoor) whose identification can significantly weaken the cryptographic strength of this cipher. In this paper, we propose and analyze one of such defects in terms of automata-theoretic approach. An operation of the cipher with this defect is modeled by a finite automaton under the so-called effective observation. The existence of effective observation for a finite automaton qualitatively reflects the presence of a trapdoor which allows one to determine the information on automaton input words by observations over the corresponding output words. We prove the criterion of finding an automaton under effective observation and specify the classes of automata under effective observation and the classes of automata for which there is no effective observation. Possible applications of the results for protecting ciphers from side channel attacks are formulated.
The analysis of ciphers in terms of automata theory is now becoming quite common. This approach allows one to formulate and solve cryptographic problems for different cipher classes. In cryptographic practice related to the synthesis (construction) of ciphers, there could be situations when one consciously builds a trapdoor cipher, i.e., a cipher whose algorithm contains some hidden structure (a trapdoor) providing the existence of a subliminal information channel. Except for this case, ciphers are usually built without such forethought defects. However, a constructed cipher may contain some critical defect (a trapdoor) whose identification can significantly weaken the cryptographic strength of this cipher. One of such defects is proposed and analyzed in this paper in terms of automata-theoretic approach. This defect presents in a cipher whose operation is modeled by a finite automaton under the so-called effective observation.
Let A=(X,S,Y,h,f) be a finite automaton with an input alphabet X, a set of states S, an output alphabet Y, a transition function h:SХS, and an output function f:SХY. Denote by A(s,P) an output word of the automaton A resulting from the initial state s when the input word is P=x1x2…xk.
The problem. It is required to find functions Uk, Фk such that Uk(P)=Фk(A(s,P)) for any pair (s,P)∈SХk, Uk≠const, Фk≠const. An automaton that satisfies this condition for some k is called an automaton under effective observation. This paper is organized as follows. In section 2, we justify the need for the setting of the presented problem and list possible areas of cryptographic information security where this problem and the results of its solution are of interest. In Section 3, we introduce the basic notions and notations by which automata-theoretic model of the problem is formulated. In this model, the examples of possible problem formulations are presented. Then we prove the criterion of finding an automaton under effective observation, i.e., the criterion of possible determining the information on key elements of a cipher or the information on a plaintext by the given observable information. This section also contains some previous results on the subject obtained by the author. The main results are in Section 5. It is devoted to finding the classes of automata for which, within the given mathematical model, it is impossible to determine the information on an automaton input word by the corresponding output word. We also consider the question whether this problem is algorithmically solvable in the class of all automata. The paper is concluded in Section 6. 2
Let us clarify in which areas of IT technologies it is useful to apply the description of automata under effective observation and the automata for which there is no effective observation. First of all, we are talking about devices and programs that are modeled by finite automata.
An information channel is called covert if it is not specifically designed and was not
originally supposed to transfer information in electronic data processing system. A
covert channel is called subliminal if it can be used only by the holder of the
corresponding secret information. The idea of subliminal information channels was
first introduced in the works of Simmons [1-3], by the example of a covert channel in
the digital signature system with a public key. In [
The device embedded in a computer and modeled by a finite automaton under effective observation provides you with an automatic retrieval of the input device information.
A trapdoor cipher is a cipher whose algorithm contains some hidden structure (trapdoor) providing the existence of a subliminal information channel; knowledge of this structure allows one to obtain sensitive information (such as secret keys). Without the trapdoor knowledge, the cipher seems to be secure.
One of the most important types of trapdoors that can be embedded in cryptographic
algorithms is the so-called SETUP (Secretly Embedded Trapdoor with Universal
Protection) mechanism [
The main known results for embedding trapdoors in ciphers are obtained for public-key cryptosystems, in particular, for the little-known public-key encryption algorithm based on finite automata and called FAPKC (Finite Automaton Public Key Cryptosystem).
Our proposed method for constructing a trapdoor cipher is different from the known ones. It is based on the choice of the automata-theoretic model for the cipher under effective observation. Its principal features are described in the section 5 «On reconstruction of information on an automaton input word by the corresponding output word».
Side-channel attacks (SCA) are a type of cryptographic attacks which exploit
information leaked from side channels [
In the works of Claude Shannon [
It is obvious that any plaintext i can be encrypted into the ciphertext z under the appropriate choice of the key γ. Thus the plaintext reconstruction based on the knowledge of a ciphertext is impossible. But if the cipher is not theoretically unbreakable, the known ciphertext sometimes allows one to reconstruct a subset Ii,z of the set IL that contains the desired plaintext. In this case, it is convenient to talk about the information on the plaintext i extracted from its corresponding ciphertext z. The smaller cardinality of this subset, the more extracted information on the desired plaintext. The subset Ii,z can be defined by its characteristic function F1. In cryptographic practice, there could be situations when the ciphertext z is fully unknown. In the introduced notation, this means we know a subset Zz of the ciphertext set Z that contains the given z, or equivalently the value of the characteristic function F2 of this subset.
The cipher for which the desired plaintext can be uniquely determined by its ciphertext is obviously the worst cipher. Not the best cipher would be the cipher for which information on the desired plaintext can be extracted from the observed data of the ciphertext. The above gives rise to the following novel setting of a cryptographic problem. Is it possible, for a given cipher with a plaintext set W, a ciphertext set Z, a set of keys K, and an encryption equation f(w,k)=z, to find nonconstant functions F1 and F2 that satisfy the condition F1(w)=F2(f(w,k)) for any wϵW, kϵK. The conditions under which such functions do not exist are of value for the synthesis of ciphers.
This problem will be solved below using the automata-theoretic approach. It should be noted that by now the automata-theoretic approach to the analysis and synthesis of ciphers has become the natural and traditional direction of cryptanalysis. This is because many encryption systems are mathematically modeled by finite automata. For example, one can imagine that a plaintext is supplied to an input of an encryption device, while the corresponding ciphertext is generated as an output, and the encryption device sequentially changes its state. Note that for a number of classical ciphers, one often imposes the requirement of reversibility which, in the case of decryption error detection, allows one to return to the previous decrypted text and correct the error. In terms of the automata-theoretic approach, the latter is achieved by the use of the so-called permutation automata. Block ciphers are usually also represented by permutation automata, for which reason it is interesting to solve the problem of extracting information on round keys (on an input automaton sequence) from the pairs of input and the corresponding output units (from the pairs of initial and final automaton states). 3
We will use the following notation: A=(X,S,Y,h,f) is a finite automaton with an input alphabet X, a set of states S, an output alphabet Y, a transition function h:SХS, and an output function f:SХY; hx:SS is a partial transition function corresponding to the input symbol xX, hxs=h(s,x); hPs hxk ...hx2 hx1 s
is a final state of the automaton A resulting from the initial state s when the input word is P=x1x2…xk; A(s,P) is an output word of the automaton A resulting from the initial state s when the input word is P.
The cardinality of a set M is denoted by |M|.
For a finite automaton A=(X,S,Y,h,f) and a natural number k, denote by Rk, Тk some finite sets. Consider the surjective mappings Нk:SХkТk, Пk:SХkRk.
Suppose that the automaton A with initial states s from S receives the input words РХk. The pairs (s,Р)SХk for which the automaton operates are unknown. However, for each pair (s,Р)SХk, we know the element t=Нk(s,P) called an observation element.
The problem. Identify the information on the element r=Пk(s,P), where r is the value of the desired operation parameter of the automaton A with initial state s and input word P. By the information on the unknown element r, we mean the identification of a proper subset R` of the set Rk that contains r. Conventionally speaking, we suppose that some function Uk on Rk is given and its value Uk(r)=j defines the subset R`={r`: r`Rk, Uk(r`)=j} (lumped state). It is also supposed that j (or the subset R`) can be defined by the known observation element t=Нk(s,P). Formally, we mean that there is a function Фk whose value Фk(t) defines j. Thus we have (Fig.1): k is a natural number indicating the length of automaton input words; Пk:SХkRk is an objective function; r=Пk(s,Р) is the value of the parameter under study for the triple (k,А,(s,Р)), (s,Р)SХk; Нk:SХkТk is an observation function; t=Нk(s,P) is an observation element for the triple (k,А,(s,Р)), (s,Р)SХk; Фk is an observation information function;
The family of introduced objects (k,Тk,Rk,Нk,Пk) is called the observation over the automaton A.
P s
A(s,P)
Нk(s,P) Definition 1. An automaton A=(X,S,Y,h,f) is said to be under the effective observation (k,Тk,Rk,Нk,Пk) if there exist nonconstant functions Фk on Тk and Uk on Rk such that
Uk(Пk(s,P))=Фk(Hk(s,P))
(1) for any pair (s,P)SXk.
The property of effective observation can be interpreted as the ability of automatic extraction of the information on the desired parameter r=Пk(s,Р) from the observation parameter t=Нk(s,P) during the automaton operation process. Note that if the functions Фk, Uk are constant, equation (1) does not provide any useful information on the value of the parameter r for the observation t. Definition 2. For the sequence of observations (k,Тk,Rk,Нk,Пk), k∈{1,2,…} over an automaton A, denote by D(A) the minimum k for which the automaton A is under effective observation. We call D(A) the depth of the automaton observation. If there is no such k, we set D(А)=.
Definition 3. An automaton A is said to be under effective observation if the depth of its sequence of observations is finite.
Definition 4. The functions Фk and Uk for k=D(А) are called the main functions for the automaton A under the observation (k,Тk,Rk,Нk,Пk).
Example 1. Diagnostic experiment with the automaton A [
Homing experiment with the automaton A [
observation (k,Тk,Rk,Нk,Пk) For brevity, we introduce the following notation: means “if and only if”; means “then”; means “exists”; means “for all”; PQ is a concatenation of words P and Q (in particular, (P)k is a concatenation of k copies of the word P). Let M be a finite set, σ a reflexive (mσm mM) symmetric binary relation on M, σ* the transitive closure of σ, and rang σ* the number of equivalence classes under the binary relation σ*. The binary relation σ is said to be transitive if rang σ*=1. The functions Нk, Пk induce the partitions of the set SXk defined by the binary equivalence relations Н*=Н*k, П*=П*k on SXk. Namely, (s,P)Н*(s`,P`) Нk(s,P)=Нk(s`,P`), (s,P)П*(s`,P`) Пk(s,P)=Пk(s`,P`).
The classes under the equivalence relations Н*k, П*k will be denoted by the letters t and r of the corresponding sets Тk, Rk, i.e, the letter t can also denote Нk-1(t), the preimage of t, and similarly for the letter r. The context will make it clear whether t and r stand for elements or classes. In particular, Тk, Rk will refer, if necessary, to the sets of the classes under the equivalence relations Н*k, П*k, respectively. Denote by t[s,P] the class comprising (s,P) under the equivalence relation Н*k and by r[s,P] the class comprising (s,P) under the equivalence relation П*k. Let us introduce the binary equivalence relations Тk/П*k on Тk and Rk/Н*k on Rk. For this purpose, we use the auxiliary binary relations ~ on Тk and ~ on Rk. The same symbol ~ is used for simplicity. The elements t, r of the sets Тk, Rk are simultaneously considered as the classes t[s,P], r[s,P], t~t` (s,P)t, (s`,P`)t`, rRk:
(s,P)r, (s`,P`)r.
The equivalence relation Тk/П*k is the transitive closure of the binary relation ~, i.e., t1 Тk/П*k tL t2,…,tL-1Tk: t1~t2~…~tL-1~tL.
r~r` (s,P)r, (s`,P`)r`, tTk:
(s,P)t, (s`,P`)t, and Rk/Н*k is the transitive closure of the binary relation ~ on Rk.
tTk, rRk: t~t, r~r, t Тk/П*k t, r Rk/Н*k r.
Define the binary equivalence relation Н*kП*k on SXk by the auxiliary binary relation on SXk, i.e., (s,P), (s`,P`)t or (s,P), (s`,P`)r. To specify the relation (s,P) (s`,P`) tTk, rRk:
(s,P), (s`,P`)tr, (s,P) (s`,P`), (s,P), (s`,P`)tr, (s,P) Н*k (s`,P`) tTk:
(s,P), (s`,P`)t (s,P) П*k (s`,P`) rRk:
(s,P), (s`,P`)r. we write and Denote by Н*kП*k the transitive closure of the binary relation . The equivalence relations Тk/П*k on Тk and Rk/Н*k on Rk induce the equivalence relations (Тk/Пk)*, (Rk/Нk)* on SXk,
t[s,P] Тk/П*k t[s`,P`], (s,P) (Rk/Нk)* (s`,P`)
r[s,P] Rk/Н*k r[s`,P`].
Denote by Н*kП*k[s,P], (Тk/Пk)*[s,P], (Rk/Нk)*[s,P] the classes comprising (s,P) under the equivalence relations Н*kП*k, (Тk/Пk)*, (Rk/Нk)* on SXk, respectively.
Theorem 1. For the binary equivalence relations on SXk there holds the equality Н*kП*k=(Тk/Пk)*=(Rk/Нk)*.
Proof. Let us show that (Тk/Пk)*=Н*kП*k. The equality (Rk/Нk)*=Н*kП*k can be proved similarly. Suppose (s,P) (Тk/Пk)* (s`,P`). Then t1[s,P] Тk/П*k tL[s`,P`]
t2,…,tL-1Tk: t1[s,P]~t2~…~tL-1~tL[s`,P`]
tj~tj+1, j{1,2,…,L-1} (sj,Pj)tj, (s`j,P`j)tj+1, rjRk: (sj,Pj), (s`j,P`j)rj (s,P)Н*k(s1,P1)П*k(s`1,P`1)Н*k(s2,
P2)П*k(s`2,P`2)…(s`,P`)
(s,P) Н*kП*k (s`,P`).
(s1,P1) Н*kП*k (sL,PL) (s2,P2),…,(sL-1,PL-1), (1),(2),…,(L-1){Н*k, П*k}: (s1,P1)(1)(s2,P2)(2),…, (sL-1,PL-1)(L-1)(sL,PL).
In the above chain of binary relations, choose the chain of minimum length L. In this case, (j)(j+1) for any j{1,2,…,L-2} and we have
t[sj,Pj]=t[sj+1,Pj+1] if (j)=Н*k, Hence,
t[sj,Pj]~t[sj+1,Pj+1] if (j)=П*k. t2,…,tL`: t[s1,P1]~t2,~…~tL`~t[sL,PL] t[s1,P1] Тk/П*k t[sL,PL] (s1,P1) (Тk/Пk)* (sL,PL). □ Corollary 1. For the number of classes under the equivalence relations Н*kП*k on SXk, Тk/П*k on Тk, and Rk/Н*k on Rk, it follows that rang Н*kП*k=rang Тk/П*k =rang Rk/Н*k.
Proof. In view of Theorem 1, it suffices to show that
rang Тk/П*k=rang (Тk/Пk)*.
from whence it follows that (s,P) (Тk/Пk)* (s`,P`) t[s,P] Тk/П*k t[s`,P`], (Тk/Пk)*[s,P]=tj[sj,Pj] for any (s,P)SXk, where the union is taken over all the classes tjТk/П*k[t[s,P]]. The required statement follows directly from the above equation. □ Theorem 2. The automaton А=(Х,S,Y,h,f) is under the effective observation (k,Тk,Rk,Нk,Пk) if and only if rang Н*kП*k2. Moreover, the values of the functions ФkHk, UkПk on SXk are the same and constant on the classes Н*kП*k, while the values of the functions Фk, Uk are constant on the classes Тk/П*k and Rk/Н*k, respectively.
Proof. Suppose that some functions Фk, Uk satisfy the following:
Фk(Hk(s,P))=Uk(Пk(s,P)) for any (s,P)SXk.
Consider two elements (s1,P1), (sL,PL) from the same class under the equivalence relation Н*kП*k. Then (1), (2), …, (L-1){Н*k, П*k}, (s2,P2),…,(sL-1,PL-1)SXk:
(s1,P1)(1)(s2,P2)(2)… (L-1)(sL,PL).
For (j)=Н*k, we obtain Фk(Hk(sj,Pj))=Фk(Hk(sj+1,Pj+1)) and hence For (j)=П*k, we obtain Uk(Пk(sj,Pj))=Uk(Пk(sj+1,Pj+1)) and hence Uk(Пk(sj,Pj))=Uk(Пk(sj+1,Pj+1)).
Фk(Hk(sj,Pj))=Фk(Hk(sj+1,Pj+1)).
Thus the functions ФkHk, UkПk on SXk take the same and constant values on the classes Н*kП*k. By Theorem 1,
Н*kП*k=(Тk/Пk)*=(Rk/Нk)*, and hence the functions ФkHk, UkПk are constant on the classes under the equivalence relations (Тk/Пk)*, (Rk/Нk)*.
For any pair (s,P)SXk, (Тk/Пk)*[s,P]=
t j[s j , Pj ] , tj rj where the union is taken over all tjTk/П*k[t[s,P]]. Similarly,
(Rk/Hk)*[s,P]= rj[s j , Pj ] , where the union is taken over all rjRk/Н*k[r[s,P]]. Therefore, Фk and Uk are constant on the classes Тk/П*k and Rk/H*k, respectively. It is clear that Фk and Uk are nonconstant if and only if rang Н*kП*k=rang Тk/П*k= rang Rk/Н*k≥2. □ Corollary 2. The depth D(A) of the observation over the automaton А for the sequence of observations (k,Тk,Rk,Нk,Пk), k∈{1,2,…} coincides with the minimum k for which rang Н*kП*k=rang Тk/П*k=rang Rk/Н*k≥2. If there is no such k, then D(А)=.
Reconstruction of information on the first input symbol of an automaton input word by the corresponding initial state and output sequence [27]: Rk=Х, Тk=(SYk), k{1,2,…};
Пk(s,x1x2…xk)=x1, Нk(s,x1,x2,…,xk)=(s,А(s,x1,x2,…,xk)).
Reconstruction of information on an input word in a permutation automaton by the corresponding initial state and output sequence [27]:.
Rк=Хк, Пк:ХкSХк, Пк(х1,х2,…,хк,s)=х1,х2,…,хк, Тк=SYк, Нк:ХкSSYк, Нк(х1,х2,…,хк,s)=(s,A(s,х1,х2,…,хк)).
Reconstruction of information on an automaton input word by the corresponding final state and output sequence [27]: Rк=Хк, Пк:ХкSХк, Пк(х(1)х(2)…х(к),s)=(х(1)х(2)…х(к)), Тк=SYк, Нк:XкSSYк, Нк(х(1)х(2)…х(к),s)=(h(s,х(1)х(2)…х(к)), A(s,х(1)х(2)…х(к))).
Reconstruction of information on an input word in a permutation automaton given initial and final states [28].
For a word Р=х(1)х(2)…х(k) in Хk, set hР=hх(k)hх(k-1)…hх(1). Denote by hРs the image of s under hР and by S(L) the set of all subsets of S with cardinality L, L≥1. Define the function Hk,L on Xk×S(L) as follows. For s(L)={sj(1),sj(2),…,sj(L)} in S(L) and P=x(1)x(2)…x(k) in Xk, set
Hk,L(P,s(L))=(s(L);hPs(L))= {(sj(1),hРsj(1)),(sj(2),hРsj(2)),…,(sj(L),hРsj(L))}.
This expression can be considered as a partial permutation on S (L transitions are defined for the permutation hР). Denote by Hk,L(Xk×S(L)) the image of Hk,L. We say that k-length input words of an automaton A can be approximately reconstructed given L initial and final states if there exist nonconstant functions Φk,L and Uk,L, defined on Hk,L(Xk×S(L)) and Xk, respectively, such that for any PXk and s(L)S(L) we have
Uk,L(P)=Φk,L(s(L),hPs(L)).
In what follows, we refer to this fact by saying that the automaton A possesses the (Хk,s,hPs,L)-reconstruction property.
The problem of describing automata with the (Xk,s,hPs,L)-reconstruction property is close to the following problems: experimental designs for automata (see [24], [30]), where an unknown input word is used for testing, with initial and final states being observed as experimental results; local reconstruction of information on an input word (see [29], [30]) given initial and final states; description of information-lossless automata [24]. A number of results concerning the problem under consideration are presented by the author in [31-35].
word by the corresponding output word
In what follows, Тk is the set of all k-length output words A(s,Р) of the automaton A corresponding to the input word PXk and the initial state sS, Rk=Xk, Нk(s,Р)=A(s,Р), Пk(s,Р)=Р.
Such an observation depends on the parameter k. From a cryptographic point of view, this naturally gives rise to the question whether there exists a natural k for which the given automaton А=(Х,S,Y,h,f) is under the observation (k,Тk,Rk,Нk,Пk). In the case of positive answer to this question, one naturally comes to the further problem of the upper estimate for such a minimum k. If there is no such k, then the cipher that is modeled by such an automaton is particularly valuable.
In order to describe the classes of automata under the effective observation (k,Тk,Rk,Нk,Пk)=(Rk=Xk,Пk(s,Р)=Р, Нk(s,Р)=A(s,Р)) and the automata for which there is no effective observation, we introduce the following notions and notation. Denote by X* the set of all finite-length words over the alphabet X and by X∞ the set of all infinite words over the alphabet X. For the concatenation of words PXn, P”Xm, we write РP”, where Р is an initial subword of РP”. If n=0, then any word from Xn is considered to be empty and РP”=P”. For the subwords of P=x1,x2,..., we use the notation: P1=P; Pn=xnxn+1... P]m=x1x2...xm Pn]m=xnxn+1...,xm n≤m; (P)k=PP…P k times.
Define a number of binary relations on the sets X∞ and XL, L{1,2,…}.
PσLP” s,s”S: A(s,P)=A(s”,P”). Pσ∞P” s,s”S: A(s,P)=A(s”,P”).
P1σ∞]LP2 P,P”X∞: Pσ∞P”, P]L=P1, P”]L=P2.
Denote by (σ∞)*, (σ∞]L)*, (σL)* the transitive closures of the binary relations σ∞, σ∞]L, σL. For the binary relation τ{(σ∞), (σ∞]L), (σL)}, denote by rang τ the number of equivalence classes under the binary equivalence relation τ*and by t(τ) the minimum L for which rang(σL)*>1
(rang(σ∞]L)*>1).
Otherwise, set t((σL)*)=∞ (t((σ∞]L)*)=∞). The introduced parameters are called the degrees of the transitive binary relations σL, σ∞]L, respectively.
Proposition 1. The automaton A is under the effective observation (k, Rk=Xk, Пk(s,Р)=Р, Нk(s,Р)=A(s,Р)) if and only if rang(σk)>1.
The class of automata with the loss of information (B1 type) and without effective observation. Now let us turn to the description of the automaton classes for which the observation (k, Rk=Xk, Пk(s,Р)=Р, Нk(s,Р)=A(s,Р)) is not effective for any k.
Definition 5. An automaton А=(Х,S,Y,h,f) is said to be an automaton with the loss of information B1 if for L | S | (| 2S | 1) 1 there exists a binary relation ε on the set X with the following properties:
1) For each pair (x,x”) from ε there exist P,P” from XL and sS such that A(s,xP)=A(s,x”P”);
Theorem 3. If a permutation automaton A is an automaton with the loss of information (B1 type), then its observation (k, Rk=Xk, Пk(s,Р)=Р, Нk(s,Р)=A(s,Р)) is not effective for any k.
Proof. Suppose the conditions of the theorem are satisfied. Let us first prove that the theorem conditions imply the following: for any pair (x,x”)ε and any word PX* there exist Q, Q”X∞ such that PxQσ∞Px”Q”. Indeed, suppose there is a pair (x,x”)ε. Then there exist automaton input words P=p1p2…pL, P”=p”1p”2…p”L and an initial state sS such that A(s,xP)=A(s,x”P”). In the transition graph of the automaton, the words P, P” are represented as the paths from the initial state sS passing through the states s, hp1 s, hp2 hp1 s,..., hpL ...hp2 hp1 s and s, hp"1 s, hp"2 hp"1 s,..., hp"L ...hp"2 hp"1 s , respectively. The two following cases are possible: 1) there exists a pair of states (hp j ...hp2 hp1 s, hp"j ...hp"2 hp"1 s) such that hp j ...hp2 hp1 s hp"j ...hp"2 hp"1 s , 2) the states in each pair of states (hp j ...hp2 hp1 s, hp"j ...hp"2 hp"1 s) , j{1,2,…L} are different. By standard methods of graph theory, it can be shown that in each of the cases 1), 2)
Pxσ∞]k+1Px” for any k{0,1,…}, PXk, and (x,x”)ε.
In particular, xσ∞]1x”. Hence, rang(σ∞]1)*=1. Thus we obtain rang (σ1)*=1 on X1. Assume that for some K, rang(σ∞]K)*=1. Then let us prove that rang(σ∞]K+1)*=1. By the assumption, it follows that there exists a chain of binary relations
P1σ∞]KP2σ∞]KP3…σ∞]KPN, N≥|X|K that contains all the words from XK.
From the definition of the binary relation σ∞]K on XK it follows that
∃αj,βjX: Pjαj σ∞]K+1 Pj+1βj, j{1,2,…,N}.
To complete the proof of transitivity of the binary relation σ∞]K on XK for any K, we introduce the binary relation ε(Q) on the set of words {Qx: xX}, where Q is an arbitrary finite word of length K over the alphabet X. Let ε(Q) be a subset of the set (XK)2 that consists of all the pairs (Qx,Qx”), where (x,x”)ε.
Lemma 1. The binary relation ε(Q) on the set of words {Qx: xX}, where QXK, is transitive.
Proof. For the automaton A, fix all the triples (s,x,x”) with the property: for each pair (x,x”) from ε there exist P, P” from X∞ and sS such that A(s,xP)=A(s,x”P”). Since the automaton A is a permutation automaton, it follows that for any triple (s,x,x”) and any automaton input word Q there exists a state sQ such that hQsQ=s. It is obvious that A(sQ,Qx)=A(sQ,Qx”). For this reason, and by virtue of transitivity of the binary relation ε, the binary relation ε(Q) is transitive. Thus Lemma 1 is proved.
Since the set of words XK+1 is divided into disjoint subsets ε(Q), QXK, on each of which the binary relation ε is transitive, and the subsets are related by (2), the induction step is carried out. We now note that the transitivity of the binary relation σ∞]K+1 on XK+1 implies the transitivity of the binary relation σK+1 on XK+1. □
The class of automata with the loss of information (B2 type) and without effective observation.
Definition 6. An automaton А=(Х,S,Y,h,f) is said to be an automaton with the loss of information (B2 type) if for L | S | (| 2S | 1) | S | there exists a binary relation ε on the set X with the following properties: 1) For each pair (x’,x”) from ε there exist P’,P” from XL and s, s”S such that
A(s,P’x)=A(s”,P”x”), hP ' x 's hP"x"s" .
Theorem 4. If an automaton А=(Х,S,Y,h,f) is an automaton with the loss of information (B2 type), then its observation (k, Rk=Xk, Пk(s,Р)=Р, Нk(s,Р)=A(s,Р)) is not effective for any k.
Proof. Suppose that for L=0, XL consists of an empty word. We will use the previously introduced notation σL of the binary relation on XL. Denote by (L) the new binary relation on XL,
P’ (L) P”
words P1’, P1” X N1 , P2’, P2” X N2 , where N1=N1(P’,P”)≥1, N2=N2(P’,P”)≥0: k≥1 it follows that (P1’)kP2’P’ kN1N2 L (P1”)kP2”P”.
Lemma 2. If А=(Х,S,Y,h,f) is an automaton with the loss of information (B2 type), then x’,x”ε, PXL, L{0,1,2,…}: x’P (L 1) x”P.
A(s,P’x)=A(s”,P”x”), hP ' x 's hP"x"s" .
6
We note the universality of the approach to the study of useful (key) information of a finite automaton based on its possible observation. In this connection, the range of topical problems of finding information about the automaton of interest to the researcher can be significantly expanded. The question of existence of an algorithm recognizing the effective observation (k, Rk=Xk, Пk(s,Р)=Р, Нk(s,Р)=A(s,Р)) in the class of all automata remains opened. 7
In this paper, we have introduced some novel notions of the automata-theoretic approach: observation over an automaton and an automaton under effective observation. The latter qualitatively reflects the presence of an automaton trapdoor for determining the information on an automaton input word by the observable information. For a given observation, we have proved the criterion of finding an automaton under effective observation. Also we have specified the classes of automata under effective observation and the classes of automata for which there is no effective observation. 22. Huffman D A. Canonical forms for information-lossless finite-state logical machines.
IRE Trans. Circuit Theory, 6, Spec. Suppl., 1959, 41-59. 23. Huffman D A. Notes on information-lossless finite-state automata. Nuovo cimento, 13, Suppl. 2, 1959, 397-405. 24. Even Sh. On information-lossless automata of finite order. IEEE Trans. Electronic
Comput., 14, 1965, 4, 561-569. 25. Even Sh. Ob avtomatah konechnogo poryadka bez poteri informacii. Trudi mejdunarodnogo simpoziuma po teorii releinih ustroistv i konechnih avtomatov (On information-lossless automata of finite order. Proceedings of the International Symposium on the theory of relay devices and finite automata.). Moscow: Nauka, 1965, 269-279. 26. Kurmit A. A. Avtomati bez poteri informacii konechnogo poryadka (On information-lossless automata of finite order). Riga: Zinatne, 1972, 264. 27. Babash A. V. Ob eksperimentah po raspoznavaniyu informacii o vhodnom slove avtomata (On experiments on recognition of information on an automaton input word). Proceeding on Discrete Mathematics, v.8., Moscow: FIZMATLIT, 2004, pp.7-24. 28. Babash A. V. On Reconstruction of Information on an Input Word in a Medvedev Permutation Automaton Given Initial and Final States. Problems of Information Transmission, 2007, Vol. 43, No. 2, pp.132–142. 29. Bogomolov A.M., Barashko A.S., and Grunskii I.S., Eksperimenty s avtomatami (Experiments with Automata), Kiev: Naukova Dumka, 1973. 30. Tverdokhlebov V.A., Logicheskie eksperimenty s avtomatami (Logical Experiments with Automata), Saratov: Izd. Sarat. Univ., 1988. 31. Babash A. V. Neotlichimost sostoyanii konechnogo avtomata otnositelno funkcii, zadannoi na ego vhodnih i vihodnih slovah (Indistinguishability of finite automaton states for the function defined on its input and output words). Obozr. Prikl. Prom.
Mat., 2001, vol. 8, no. 1, pp.94–95. 32. Babash A. V. On Some Invariants of a Finite Automaton. Obozr. Prikl. Prom. Mat., 2000, vol. 7, no. 1, pp.86–87. 33. Babash A. V., Local Reconstruction of Input Words of Automata Given the Initial and Final States. In Proc. 2nd All-Russian Symp. on Applied and Industrial Mathematics, Samara, 2001, pp.93–94. 34. Glukhov M. M., On Numerical Parameters Associated with the Definition of Finite Groups by Systems of Generating Elements. In Trudy po diskretnoi matematike (Proceedings in Discrete Mathematics), vol. 1, Moscow: TVP, 1997, pp.43–66. 35. Krapeˇz A., On a Generalization of Fermat’s Theorem in the Theory of Groups, Publ.
Inst. Math.(Beograd) (N.S.), 1974, vol. 17(31): 77–81.