Abstract
Feedback shift registers (FSRs) are used as a fundamental component in electronics and confidential communication. A FSR is said to be reducible if all the output sequences of another FSR can also be generated by and the FSR costs less memory than . A FSR is said to be decomposable if it has the same set of output sequences as a cascade connection of two FSRs. Two polynomial-time computable transformations from Boolean circuits to FSRs are proposed such that the output FSR of the first (resp. second) transformation is irreducible (resp. indecomposable) if and only if the input Boolean circuit is satisfiable. Through the two transformations, it is proved that deciding irreducibility (indecomposability) of FSRs is -hard. Additionally, FSRs are constructed to show that there exist infinitely many irreducible (resp. indecomposable) FSRs which are decomposable (resp. reducible).
1. Introduction
Feedback shift registers (FSRs) are broadly used in spread spectrum radio, control engineering, and confidential digital communication. As a result, this subject has attracted comprehensive research over half a century. Particularly, FSRs play a significant role in the stream cipher finalists of the eSTREAM project [1].
As shown in Figure 1, an -stage FSR consists of -bit registers and an -input feedback logic . A vector is called a state of this FSR, and the values stored in bit registers update themselves along with clock impulses as follows:and the mapping defined by Equation (1) is called the state transformation of this FSR. As the stage and the feedback logic uniquely determine the FSR, we denote the FSR in Figure 1 by . Let denotes the set of sequences generated by , i.e.,where is the set of all binary sequences. The subscript in and is neglected if the stage is unambiguous or unnecessary in the context.
If , where , then is called a linear feedback shift register (LFSR), and is called its characteristic polynomial. This FSR is also denoted by . For the above linear function and , is said to be affine. A nonaffine FSR is called a nonlinear feedback shift register (NFSR).
For , if there exists , such that and , then is said to be reducible and is called a subFSR of . Otherwise, is said to be irreducible. Informally, the subFSR of costs less memory than and the sequences generated by can also be generated by .
The finite state machine in Figure 2 is called the cascade connection of into . The Grain family ciphers use the cascade connection of a LFSR into a NFSR [2] and such cascade is called the grain-like structure, and the lightweight stream cipher LIZARD employs the cascade connection of two NFSRs [3]. Green and Dimond [4] defined the product FSR (the product of FSRs is denoted by “.” in [4], while by “” in [5]. We follow the latter in order to avoid ambiguity with the period or conventional multiplication.) of and , denoted by , to be characterized by its feedback logic as follows:and showed that generates exactly the same set of sequences as the device in Figure 2. Given any , if there exist and satisfying , then is said to be decomposable and (resp. ) is called its left (resp. right) -factor [6]. Otherwise, is said to be indecomposable. It is known that decomposable FSRs outputting the zero sequence are also reducible [4].
It is appealing to decide whether a FSR is (ir)reducible or (in)decomposable for the following three reasons. First, it enables a new perspective on analysis of stream ciphers. A reducible/decomposable FSR in unaware use may undermine the claimed security of stream ciphers, e.g., causing inadequate period of the output sequences. Dependent on specific ciphers, the divide-and-conquer method [7, 8] possibly decreases the cost of a brute force attack on a product FSR . Moreover, note that all sequences generated by is also generated by if outputs the zero sequence; and if is particularly a LFSR in this case, then generates a family of linear recurring sequences, vulnerable to the Berlekamp–Massey algorithm [9, 10]. Second, deciding (ir)reducibility/(in)decomposability is applied for efficiently implementing FSRs. On the one hand, it costs less memory to replace a FSR with its large-stage subFSR (if there is one) while generating part of its output sequences. On the other hand, similar to the idea of Dubrova [11], implementing a decomposable FSR by its corresponding cascade connection as in Figure 2 possibly reduces the circuit depth of the feedback logics, in favor of less propagation time and higher data throughput. Third, an algorithm testing (ir)reducibility/(in)decomposability helps to design useful FSRs. Since the density of irreducible FSRs is lower-bounded by for [12], a great number of irreducible NFSRs can be found if deciding irreducibility of FSRs is feasible; a kind of FSRs generating maximal-length sequences were also constructed based on the inherent structure of decomposable FSRs [5].
1.1. Our Contribution
This correspondence addresses irreducibility and indecomposability of FSRs from the perspective of worst-case computational complexity. Instead of representing FSRs by ANFs of their characteristic functions, we use Boolean circuits to characterize feedback logics of FSRs and measure the size of a FSR by the number of gates in its corresponding Boolean circuit. PROBLEM: FSR IRREDUCIBILITY INSTANCE: A with its feedback logic as a Boolean circuit of size . QUESTION: Is irreducible? PROBLEM: FSR INDECOMPOSABILITY INSTANCE: A with its feedback logic as a Boolean circuit of size . QUESTION: Is indecomposable?
is the class of all problems computed by polynomial-time nondeterministic Turing machines. A problem is -hard if it is at least as hard as all problems. This paper gives two polynomial-time computable algorithms transforming Boolean circuits to FSRs such that the input Boolean circuit is satisfiable if and only if the output FSR is, respectively, irreducible and indecomposable. Because the Boolean circuit satisfiability problem is -complete, the two transformations derive the main results of this paper:
Theorem 1. The FSR IRREDUCIBILITY problem is -hard.
Theorem 2. The FSR INDECOMPOSABILITY problem is -hard.
It is broadly believed that -hard problems could not be solved by quantum algorithms in the polynomial time [25], partially supported by some evidence [26]. Under this hypothesis, even a quantum computer cannot efficiently decide whether any given FSR is irreducible (or indecomposable).
Additionally, infinitely many instances of FSRs are given to show that irreducible FSRs do not include all indecompsobale FSRs and vice versa.
1.2. Related Work
It is a hot topic to address security issues of FSRs and their cascade connections, and progress has been made in recent years. Until now it is unknown how difficult deciding irreducible FSRs is, and special algorithms were proposed to search linear/affine subFSRs of NFSRs [13]. By Jiang and Lin [14], if , where and any nonzero is of maximal period , then all affine subFSRs of are actually those of . Whether a LFSR is indecomposable is completely determined by its characteristic polynomial [4, 6, 15]. In contrast, decomposing NFSRs seems much more challenging. Ma et al. [16] proposed a decomposing algorithm for NFSRs with a linear right -factor using algebraic normal forms (ANFs) of Boolean functions, and Zhong and Lin [17] characterized several properties of general cascade connection using the language of state transition matrices of Boolean networks. Noteworthily, Tian et al. [6] proposed a method to find nonlinear left and right -factors of NFSRs, and their algorithm efficiently and successfully decomposed -stage NFSRs in their experiments. So far it remains open to determine the asymptotic computational complexity of the algorithm in [6]. Instead of considering general decomposition, a practical algorithm has been proposed to find -factors for the special case [18]. Zhong and Lin [19] gave strong results on uniqueness of cascade decomposition . Additionally, the periods of sequences generated by the grain-like structures are studied [20–24].
1.3. Organization
The rest of this paper is organized as follows: in Section 2, we prepare facts and results for our main theorems. Section 2.1 is some notations. Sections 2.2 and 2.3, respectively, present some basic facts on Boolean circuits and cycles of FSRs. Section 2.4 includes some results on the cascade connection into . In Section 2.5, we consider cycles and subFSRs of specific LFSRs. In Section 2.6, we use the cycle joining method to study subFSRs. Section 3 shows some relations between (ir)reducibility and (in)decomposability. -hardness of FSR irreducibility and FSR indecomposability is given in Sections 4 and 5, respectively. The last section includes a summary.
2. Preliminaries
2.1. Notations
Throughout this paper, let denote the set of integers, the binary field, the addition of integers, the exclusive-or (XOR), (resp. ) consecutive ’s (resp. ’s).
Vectors are written in bold and upright letters or digits.
For and , let denote the most significant bits of .
Let denote the dual of a bit , and this notation naturally extends to vectors, i.e., for , .
The conjugate of , denoted by , is .
Using the reverse lexicographic order, we take a vector as the nonnegative integer . In this way,if and only if .
Definition 1. For a Boolean logic , its associated logic is as follows:
Following from Definition 1, we have:
2.2. Boolean Circuits and Circuit Satisfiability Problem
An -input Boolean circuit is a directed acyclic graph with sources and one sink [25]. The value(s) of source(s) is(are) input(s) of the Boolean circuit. Any nonsource vertex, called a gate, is one of the logical operations OR(), AND (), and NOT(), where the fan-in of OR and AND is and that of NOT is . The value outputted from a gate is obtained by applying its logical operation on the value(s) inputted into it. The value outputted from the sink is the output of the Boolean circuit . The size of the circuit , denoted by , is the number of vertices in it. An -input Boolean circuit is satisfiable, if there exists such that . PROBLEM: CIRCUIT SATISFIABILITY INSTANCE: A Boolean circuit with its size . QUESTION: Is satisfiable?
A decision problem in class is -complete if it is not less difficult than any other problem.
Theorem 3 (see [25], Lemma 6.10). The CIRCUIT SATISFIABILITY problem is -complete.
A FSR is completely characterized by its feedback logic. We use Boolean circuits to characterize the feedback logic of FSRs for the following two reasons. First, FSRs are mostly implemented with silicon chips, and the Boolean circuit is an abstract model of the feedback logics of FSRs in silicon chips [25]. Second, the Boolean circuit is a generalization of Boolean formula [25]. For example, the Boolean function can be implemented by a Boolean circuit with gates, while expressing it with the ANF needs terms. Therefore, in this paper the size of a FSR is measured by the size of its feedback logic as a Boolean circuit.
2.3. Cycles of FSRs
Lemma 1 [27, 28]. The following three statements are equivalent:(i)The state transformation of is a bijection on .(ii)Any sequence generated by is periodic.(iii) for some Boolean logic .
If any of the statements in Lemma 1 holds, is said to be nonsingular. In the sequel, we only refer to nonsingular FSRs.
For vectors and , is said to precede if for all .
Definition 2. (In this paper, cycles are written in bold and italic letters while vectors in bold and upright letters or digits.) [29] A -cycle in is a ring sequence of distinct -bit vectors:such that precedes for all .
Cycles interpret the relation between FSRs and periodic binary sequences.
On the one hand, as in Figure 3, the first column lists the vectors ’s in the cycle ; the second column shows the most significant bits of ’s, representing a periodic sequence downwards in the boxes. Thus, the cycle in Figure 3 is also written as the ring bit sequence:
Two cycles represented by the same ring bit sequence are said to be equivalent, for they correspond to the same set of periodic sequences which are equivalent by shifting.
Example 1. The following two cycles:correspond to the same ring bit sequence , and are hence equivalent.
Without ambiguity in the context, we do not distinguish a cycle from its ring bit sequence. Whether or not, an -bit vector occurring (contained) in the cycle Equation (7) means that is consecutive bits in the ring bit sequence Equation (8). Let denote the number of distinct vectors in the cycle , i.e., the period of the binary sequence it represents.
On the other hand, if , with its state transformation denoted by , generates the periodic sequence Equation (8), then , . If so, is called a cycle of , and this is denoted by . Actually, the cycle is an orbit of the permutation acting on . In Figure 3, the second column is the bit outputted by and the third column shows the sequences which generates from the initial state ’s. Since all the cycles of a FSR uniquely determine its state transformation and hence its feedback logic, we also use to denote the set of all cycles of this FSR.
Example 2. Let and be cycles given in Example 1. ThenBoth and output the sequence of period , and it is unambiguous to write .
As explained above, cycles of a nonsingular FSR essentially characterize its periodic sequences, and the following statementsare equivalent. Immediately, we have
Lemma 2. is a subFSR of if and only if .
Since the state transformation of an -stage FSR is a permutation on , all its cycles exhaust once, and hence the lengths of its cycles sum to .
Lemma 3. It holds that .
Lemma 4. If both and its conjugate occur as -bit vectors in the same cycle , then for any , is not a cycle of any nonsingular -stage FSR.
Proof. Assume , . Note that the cycle contains two -bit vectors and . Since , the state transformation of satisfies:which is contradictory to Lemma 1. Thus, is not true.
For a cycle , let be the minimal -bit vector occurring in .
Definition 3. Let and be two cycles in . If there exists an -bit vector occurring in such that occurs in , then is said to be adjacent to (at ). If is adjacent to at , then is said to be min-adjacent to .
Lemma 5. Let and . If is min-adjacent to and , then .
Proof. Denote . By Statement (iii) of Lemma 1, the next states of and are and .
Recall that vectors are in the reverse lexicographic order. If , i.e., are not all , then since is the left shift of and .
Furthermore, since as in Definition 3, we conclude that is in the same cycle as (i.e., in ), implying
Corollary 1. Let . If , then is not min-adjacent to itself.
Proof. Let and be as in Lemma 5. Note that the proof of Lemma 5 also holds even if . If , then does not hold, and we conclude that is not min-adjacent to itself.
Furthermore, suppose . Then , the conjugate of , is not contained in . Thus, is not min-adjacent to itself.
Lemma 6. Let be a directed graph defined as follows: the vertices of are cycles of , and an arc is incident from to if is min-adjacent to and . Then is acyclic.
Proof. By Corollary 1, the only cycle min-adjacent to itself has as its minimal -bit vector. Hence, , as defined above, is loopless.
Now assume that is not acyclic. Then there is a cyclic walk of length in , i.e., there exist cycles ’s, such that is min-adjacent to at , .
As is defined, we have for any . Additionally, we also have for any . Otherwise, for some , then and is hence a sink instead of a vertex in the cyclic walk. Thus, by Lemma 5:which does not hold. Therefore, has no cyclic walk in it.
The cycle in Figure 3 is said to be even if (equivalently, ). Otherwise, is said to be odd [29].
For the cycle in (7), let denote the cycle . A cycle is said to be self-dual if [29]. The cycle in Equation (7) is said to be primitive if and have no -bit vector in common [29].
2.4. The -Morphism
For any , the -morphism [29] is a mapping as below:
Notice that if precedes , then also precedes . Hence, the -morphism is also a natural mapping on cycles.
Lempel [29] gave the following results on -morphism.
Theorem 4 ([29], Corollaries 1 and 2). There exists a one-to-one correspondence between the even -cycles in and the primitive pairs of dual -cycles and in under which . There exists a one-to-one correspondence between the odd -cycles in and the self-dual -cycles in under which .
The -morphism connects and its left -factor.
Corollary 2. Let . Then the following two statements hold: (i) for any cycle , is a cycle of ; (ii) for any odd (resp. even) cycle , its -morphic preimage(s) is (resp. are) cycle(s) of .
Proof. Substitute for in Figure 2. Let and be, respectively, the state transformations of and . As shown in the following commutative diagram
it follows from Equation (3) that for any . Thus, Statement (i) holds, and any is a -morphic preimage of . By Theorem 4, under the -morphism, a -cycle of has one -cycle as its preimage or two -cycles as its preimages. If does not include all -morphic preimages of cycles in , then the length of cycles of sum to less than , contradictory to Lemma 3. Therefore, Statement (ii) immediately follows.
Example 3. Let , , and . We have ,In Example 3, the even cycle has two -morphic preimages and , and the odd cycle has a unique -morphic preimage .
2.5. Cycles and Properties of Certain LFSRs
In the rest of this paper, we use the following polynomials over :where is a power of . For simplicity, let denote the associated logic of the feedback logic of , i.e., .
In all that follows, , , and , respectively, denote the state transformations of , , and as in Equation (20).
Cycles of LFSRs are well-understood.
Lemma 7. If is a power of , then the cycles of are and -cycles , ; the cycles of are the cycles of and their duals , ; the cycles of are the cycles of and -cycles.
Proof. Let . Since and , the roots of are exactly primitive -th roots of unity in the algebraic closure of . Furthermore, because , an extension of containing a primitive -th root of unity is of degree at least . Thus, the polynomial is irreducible over .
Then the cycles of , , and are given by Lidl and Niederreiter [15, Theorem 8.53, 8.55, 8.63].
In the rest of this paper, let denote the set of -cycles of .
In the rest of Section 2.5, we give some properties of and in Lemma 9, and study their subFSRs in Theorems 5 and 6.
Theorem 5. is an irreducible FSR.
Proof. As given in Lemma 7, exactly includes one -cycle and -cycles. Let .
Suppose to be a subFSR of , where . By Lemma 2, the cycles of are contained in . Then let have exactly -cycle and -cycles. Thus, by Lemma 3, the lengths of cycles in sum to , i.e.,where and . In Equation (21), letting results in the contradiction ; letting leads to , where , contradictory to the fact that is primitive in the residue ring , i.e., .
Hence, our supposition does not hold and has no subFSR.
It is well-known that LFSRs with irreducible characteristic polynomials are also described using finite fields [15, Theorem 8.24].
Lemma 8. Let be an irreducible polynomial of degree over , a root of in the finite field , and the state transformation of . Then there exists a linear-space isomorphism such that the diagram
is commutative.
Proof. Let be the trace function of and define a linear homomorphism:Since are a basis of over , is an isomorphism of linear spaces. Let to be the inverse of and the rest of proof is by direct computation similar to [15, Theorem 8.24].
By Equation (6) and Lemma 7, . In Figure 4, we sketch cycles of , , and , and a cycle in the (boxed) third row is the -morphic image of the two cycles of in the same column.
Lemma 9. Let be an irreducible polynomial of degree over . Denote the logic . Then the following statements hold:(i)Any cycle of is even and any cycle in is odd.(ii)The -morphism is a permutation on cycles of .(iii)For any pair of -bit conjugate vectors , one occurs in some cycle and the other occurs in some cycle .
Proof. As is irreducible and , then has no factor and hence . So, is the associated logic of the feedback logic of .
By Lemma 8, the states of a nonzero cycle in correspond to a coset of a multiplicative cyclic group, and hence summing them up yields , and is hence even. Furthermore, Equation (6) implies , and it is known that is odd for any [15]. Hence, any cycle of is odd. Statement (i) holds.
Summing a sequence generated by and its left-shift derives a sequence also generated by . Thus, the -morphism is a well-defined mapping on . As shown above, any is even and is odd. Then by Theorem 4, the -morphic preimages of are exactly one even cycle and its odd dual cycle , where . In other words, the -morphism is injective on and hence Statement (ii) holds.
For , is generated by (resp. ) if and only if . Then Statement (iii) holds.
Theorem 6. The subFSRs of are exactly , , and .
To prove Theorem 6, we prepare Lemma 10 and Corollary 3 below.
Lemma 10. Let be an irreducible polynomial of degree over , and the state transformation of . Then for any , there exist such that for any , .
Proof. Due to the isomorphism in Lemma 8, we consider the counterparts of ’s in the finite field . Denote , , and . Clearly, . Since is a linear basis of , for some . Let , . Then it is verified that .
Let , . Using the commutative diagram in Lemma 8, for any , we have:
Corollary 3. Let , where is an irreducible polynomial of degree over . Let be the set of -bit vectors in , . Then .
Proof. See that and choose any and . By Lemma 10, there exist such that for any , either or is in the same cycle as . Note that if and is in the same cycle as , then . Thus, there exist some such that and , implying .
Proof of Theorem 6. By Lemma 2, Figure 4 shows that , , and are subFSRs of . It remains to show that there exist no other subFSRs.
Let be a subFSR of .
First, Lemma 2 ensures . Due to Lemma 7, let (resp. ) be the number of -cycles (resp. -cycles) of . Lemma 3 derives the following integer equation:where , , and . Letting contradicts to . Because , where is a power of , Equation (24) holds only if (i) and , or (ii) and .
Case (i) and . The cycles of are exactly and , i.e., .
Case (ii) and . is of stage . Notice that if and only if . We only have to consider , i.e., has and -cycles. Let . Clearly, and is not empty.
Assume . As shown in Figure 5, cycles in are partitioned into and and cycles in are partitioned into and . LetOn the one hand, since a -stage FSR exhausts as its states:On the other hand, as the way is defined, we have:implying , i.e., , contradictory to derived by Corollary 3.
Therefore, the above assumption is not true, i.e., the -stage subFSR with the zero cycle is .
2.6. The Cycle Joining Method
Theorem 7 (see [27, 28]) and (see [29], Theorem 2). Let . Let be an -variable Boolean logic and . Then differs from only by interchanging the next-states of and . Specifically, as shown in Figure 6, if and are in the same cycle , then is split into two adjacent cycles of ; if and are in two distinct cycles , then and are joined into a single cycle of .
Definition 4. Given and a set , the associated graph, denoted by , is a directed graph defined as follows: the vertices are cycles of , and an arc is incident from to if and only if is adjacent to at .
Definition 5. is said to be a potential set of if the following two statements hold:(i)Any cycle of has at most one vector in ;(ii)The associated graph is acyclic.
Remark 1. In Definition 5, the acyclic associated graph implies that contains no pair of conjugate vectors.
Definition 6. Given a set , its characteristic function is:
Example 4. Let be nonsingular and . Each cycle of has a unique minimal -bit vector. Furthermore, by Lemma 6, the associated graph is acyclic. Thus, is a potential set of .
Note that for a subset , is a subgraph of . Hence, a subset of a potential set of is also potential for .
Theorem 8 is the key tool of this paper.
Theorem 8. Let be nonsingular, a potential set of , the characteristic function of , and . Then, the following statements hold:(i) is a nonsingular FSR.(ii)A cycle of is joined by cycles of which form a weakly connected component in .(iii)If is a subFSR of this , then any cycle of is equivalent to a cycle of such that contains no vectors in .
Proof. LetThen, the Boolean logic:is independent of the first coordinate of . Thus, by Lemma 1, since for some Boolean function , it characterizes a nonsingular FSR. Statement (i) of Theorem 8 is proved.
Due to Remark 1, we have:Algorithm 1 obtains cycles of from those of .
| ||||||||||||||||||||||||||||
Notice that, the Boolean logic differs from only at the vectors in and their conjugates. Use notations in Algorithm 1. On the one hand, cycles of other than ’s () are isolated vertices in , and are hence cycles both for and for . On the other hand, Algorithm 1 shows that each cycle of with a state in is joined by at least two cycles of . Specifically, those cycles in the set , in the list , or in are exactly cycles of , where the Boolean logic satisfies Equation (32). Notice that, occurs in and hence in for . In Lines 6–8, Algorithm 1 changes valuation at in the cycle (also in ), and at its conjugate , and hence derives from .
Because is acyclic and each vertex has at most one outdegree, is a forest and a weakly connected component in it is a tree. Furthermore, due to the topological ordering, only cycle joining is used in Algorithm 1 and no cycle splitting occurs; and each vector in causes a once joining. Thus, cycles forming a tree in is connected by arcs, and joinings compose them into a cycle in , i.e., a cycle of . Statement (ii) of Theorem 8 holds.
Furthermore, if a cycle is derived from joining more than one cycles of , then includes conjugate -vectors and is hence not a cycle of any subFSR of by Lemma 4. Therefore, Statement (iii) of Theorem 8 is proved.
Statement (iii) in Theorem 8 implies Corollary 4 below.
Corollary 4. Let and be defined as in Theorem 8. Then any subFSR of is also a subFSR of .
3. Some Relations between (Ir)Reducible and (In)Decomposable FSRs
Fisrt, we consider LFSRs. As for LFSRs, (note that in this paper LFSRs are defined to be homogeneous, i.e., their feedback logics in ANF do not have nonzero constant) reducibility is equivalent to decomposability. On the one hand, whether a LFSR is decomposable if and only if its characteristic polynomial is reducible [4, 6, 15]. On the other hand, if and only if [15]. Thus, deciding indecomposability of LFSRs completely converts to irreducibility of their chracteristic polynnomials.
Second, we consider FSRs with the zero cycle.
Figure 2 straightforwardly yields Proposition 1 below.
Proposition 1. If and , then is a subFSR of .
Proposition 2 (see [4]). Let be a decomposable FSR satisfying . Then there exist and for some such that and . Particularly, is a subFSR of and is reducible.
Proof. Assume for some . Denote . Then using Equation (3) yields:Thereafter we take and as follows:Immediately, we have .
Moreover, because [16, Lemma 1], it always holds that . The rest of proof is completed by Proposition 1.
The idea of Proposition 2 was given by Green and Dimond [4] and here we reinterpret it.
Third, note that there are infinitely many irreducible and indecomposable FSRs, and below we answer the question whether all irreducible (resp. indecomposable) FSRs are indecomposable (resp. irreducible).
Theorem 9. There exist infinitely many reducible and indecomposable FSRs.
Proof. We give a family of reducible and indecomposable FSRs as below.
Consider any even . Since the finite field has a cyclic multiplicative group , we choose to be the minimal polynomial of over , where is of order . LetIt is known that , where ’s are three -cycles [15]. Without loss of generality, assume that occurs in . Then in , precedes and precedes . By Theorem 7, in , is split to and a -cycle , and hence .
Consider subFSR(s) of . , and other possible subFSR(s) should be of stage sinceHowever, because the integer equation:where and , has no solution, by Lemma 3, has no subFSR of stage . Thus, is the unique subFSR of .
Assume that is decomposable. By Proposition 2, , where . Note that is an irreducible polynomial over . By Corollary 3, the cycle is not self-dual. Moreover, by Statement (i) of Lemma 9, the cycle is even. If so, by Corollary 2 and Theorem 4, is the dual of and , implying:contradictory to Corollary 3. Therefore, is indecomposable.
Theorem 10. There exist infinitely many decomposable and irreducible FSRs.
Proof. We construct a family of decomposable and irreducible FSRs as below.
Consider any . There exist outputting a de Bruijn sequence [27], i.e., has only one -cycle . Let . Clearly, is decomposable. Furthermore, by Theorem 4 and Corollary 2, has exactly two cycles and , implying that and do not occur in the same cycle. Since no FSR of stage less than generates or , neither nor defines a subFSR. Therefore, is irreducible.
4. -Hardness of Deciding Irreducible FSRs
This section proves Theorem 1. Above all, we sketch our idea. Our way is to give a polynomial-time Karp reduction (detailed in Algorithm 2) from the CIRCUIT SATISFIABILITY problem to the FSR IRREDUCIBILITY problem. Using the cycle joining method in Theorem 8, we choose and construct a potential set such that in the associated graph (i) all -cycles of are not isolated (by Lemma 15) and (ii) all cycles in are sources (by Lemma 14). The Boolean circuit (the input of the Karp reduction) is used to tune such that all cycles in are isolated in if and only if is unsatisfiable. The parameters are chosen such that there exists no subFSR of stage less than (by Theorem 5). Because a nonisolated cycle in does not admit a subFSR of (by Lemma 4), is the only possible subFSR of and it occurs if and only if is unsatisfiable (by Lemma 16). Additionally, the transformation itself is polynomial-time computable (detailed in Lemma 17). Below we give details of this proof.
In this section, for , denotes the unique cycle of containing .
Definition 7. Let denote the set of cycles of min-adjacent to a cycle of ; and let denote the set of cycles in such that any cycle in is not min-adjacent to . Formally,
Lemma 11 shows that in , a cycle is adjacent only to -cycles.
Lemma 11. Let . If is adjacent to and , then .
Proof. Let be a -bit vector in . Suppose . Note that is a -bit vector in . By Lemma 7, we have and . Since is a linear transformation and , we have , contradictory to the fact . Therefore, the above supposition does not hold and hence .
By Definition 7 and Lemma 11, we have .
Example 5. Let . For ,and includes only one cycle:
In this section, for a Boolean logic , , we define four subsets of :
Theorem 11. is a potential set of .
To prove Theorem 11, we need Lemmas 12–14.
To some extent, Lemma 12 describes the cycles in .
Lemma 12. If , thenwhere , , and .
Proof. As , we denotewhereNote that, the cycle contains . Then the -bit sequence of containing is:since is a linear transformation. By Lemma 7, If the sequence Equation (46) is generated by , then its period divides , and hence , , , , , , , and . Thus, we getDue to Equation (45), we have:and hence . Similarly, we have:and hence . Immediately, . The proof is complete.
Lemma 13 describes in which cycles the conjugates of vectors in are located.
Lemma 13. For any , is contained in a cycle in .
Proof. Let and . Since , is of the form Equation (43) given in Lemma 12. Then,and hence,For a -cycle ,is called an -sampling of , .
On the one hand, see that . Thus, by Lemma 7, .
On the other hand, by Lemma 12, occurs as an -sampling of any cycle in . However, as shown in (51), is not an -sampling of . Therefore, .
Lemma 14. The cycles of are sources in the associated graph , and is acyclic.
Proof. Recall that an arc is incident from to if is adjacent to at some .
First, consider cycles of . By Lemma 11, the successor of any cycle of in , if there is one, is a cycle in . Moreover, by Definition 7 and Lemma 13, no cycle in is adjacent to a cycle in at some . Thus, cycles of are sources in .
Second, consider cycles in . By Definition 7 (resp. Lemma 13), in there exists no arc incident from any cycle in (resp. in ) to a cycle in . Hence, due to Definition 4 and Equation (42), in , a cycle in is either a source or a successor of a cycle of . Therefore, in either case any is not a vertex in a cyclic walk in .
Thus, is acyclic if and only if is acyclic.
Because any is the nonzero minimal -vector in , is loopless by Corollary 1, and is furthermore acyclic by Lemma 6. The proof is complete.
Incorporating the proof of Lemma 14 and Definition 7, we present Figure 7 to show (possible) directions of arcs in .
Proof of Theorem 11. By (42) and , any cycle of has at most one vector in . By Lemma 14, is acyclic. Therefore, satisfies Statements (i) and (ii) in Definition 5.
Lemma 15. No cycle in is an isolated vertex in .
Proof. Note that . See Figure 7.
By Definition 4 and Equation (42), any cycle in is not isolated in .
Moreover, by Definition 7, for , there exists such that contains the conjugate of . Then by Definition 7, and hence . Thus, there exists min-adjacent to . Therefore, any cycle in is not isolated in .
Lemma 16. Let be defined in Equation (42) and its characteristic function. LetThen is irreducible if and only if the Boolean circuit is satisfiable.
Proof. By Theorem 11, is a potential set of .
By Theorem 8, is nonsingular and it is reducible if and only if there exists , , such that all its cycles essentially belong to and all -bit vectors generated by are not in . Furthermore, by Lemma 15, any cycle in has a state in , and hence we only have to consider such with its cycles in .
Suppose to be unsatisfiable. Then is empty as defined in Equation (42). By Definition 4 and Lemma 14, all cycles of are isolated vertices in . Therefore, is a subFSR of .
Suppose to be satisfiable. Since the nonzero cycles of exhaust all nonzero -bit vectors and , there exists at least one nonzero cycle containing a -bit vector such that . Then is not empty as defined in Equation (42). In this case, all cycles in and some cycle(s) of are not isolated vertices in . Thus, by Theorem 8, a subFSR of should be a subFSR of . Anyhow, has no subFSR by Theorem 5, and hence is irreducible.
| ||||||||||||
Lemma 17. There exists a polynomial-time algorithm for the transformation defined by Algorithm 2.
Proof. In Figure 8, the characteristic functions of , , and are given in peudocodes. Note that in , is equivalent to .
First, the linear transformations , and have complexity . Second, the subprocedure decides whether is a nonzero -bit vector and costs ; decides whether is the minimal vector in the sequence , where is the state transformation, and costs ; decides whether , and costs ; decides whether is evaluated at some -bit vector in the cycle containing , and costs . Thus, the time complexity of , , , and are, respectively, , , and . Third, Line 2 of Algorithm 2 costs , and ensures . Moreover, the fan-in is not greater than the circuit size, i.e., . Therefore, the time complexity of , and hence that of , is polynomial in .
Furthermore, incorporating Figure 9 we give a branchless interpretation of the logic via standard instructions and the input circuit . Additionally, the nesting depth of loop structures is not greater than three, and each loop structure has a controlling counter upper-bounded by , including implicit loops in , and . Thus, we conclude that Figures 8 and 9 enable to express the feedback logic as a straight-line program scaling up its size up to (essentially dependent on ), with at most instructions, where is a polynomial in . Moreover, the parameter is efficiently decided in Line 2 of Algorithm 2. Therefore, given a Boolean circuit , there exists a polynomial-time algorithm characterizing the above .
Proof of Theorem 1. By Theorem 3, Lemmas 16 and 17, Algorithm 2 gives a polynomial-time Karp reduction from the -complete problem CIRCUIT SATISFIABILITY to FSR IRREDUCIBILITY. Therefore, we conclude that FSR IRREDUCIBILITY is -hard.
5. NP-Hardness of Deciding Indecomposable FSRs
This section proves Theorem 2. Above all, we sketch our idea. Similar to the proof of Theorem 1, we give a Karp reduction (detailed in Algorithm 3) from the CIRCUIT SATISFIABILITY problem to the FSR INDECOMPOSABILITY problem. Using the cycle joining method in Theorem 8, we take and construct a potential set of in the following way. The potential set of defined in Example 4 is tuned by the Boolean circuit (the input of the Karp-reduction), and then includes their -morphic preimages generated by . If is unsatisfiable, is equivalent to . If is decomposable, a possible right -factor of is a subFSR of (by Proposition 2 and Corollary 4), which turns out to be either or (by Theorem 6). If is satisfiable, Theorem 8 ensures that is not a right -factor of , and Lemma 6 does not admit as a right -factor of (detailed in the proof of Lemma 19). That is, is indecomposable if and only if is satisfiable. Additionally, the transformation itself is polynomial-time computable (by Lemma 20). Below we give details of this proof.
In this section, for , denotes the unique cycle of containing .
For a Boolean logic , , we define a subset of :
Theorem 12. is a potential set of .
Proof. As Statement (ii) of Lemma 9, the -morphism is a permutation on , and hence . Note that any cycle of has a unique minimal -bit vector. Thus, is well-defined and its -morphic preimages are a pair of dual vectors. By Statement (i) of Lemma 9 and Theorem 4, as shown in Figure 4, one of the preimages occurs in a cycle of , and the other in a cycle of . Thus, the preimage in a cycle of is uniquely determined. Therefore, each nonzero cycle of has at most one -bit vector in , and any cycle of has no vector in .
By Definition 4, Equation (54) and Statement (iii) of Lemma 9, an arc in the associated graph always goes from a cycle in to a cycle in . Then is therefore acyclic.
In summary, satisfies Statements (i) and (ii) of Definition 5 and is hence a potential set of .
We define a directed graph as follows: the vertices of are cycles of , and an arc is incident from to if and only if is min-adjacent to at and in such that .
Lemma 18. is a contraction graph of , where for all , two vertices and of are identified as one vertex in .
Proof. The pair of vertices and contract to in , , and the pair of -cycles and contract to .
On the one hand, the same as in the proof of Theorem 12, if an arc in goes from some cycle in to some cycle in , then this arc is necessarily incident from to . By Definition 4 and Equation (54), an arc in is incident from a nonzero cycle to if and only if there exists satisfying the following four statements: (i) is -bit vector in ; (ii) is the minimal -bit vector in ; (iii) is evaluated at an -bit vector in ; and (iv) occurs in .
On the other hand, the vertices of are and ’s, , and an arc in is incident from the nonzero cycle to if and only if there exists satisfying the following three statements: (i) is the minimal -bit vector in ; (ii) is evaluated at an -bit vector in ; and (iii) occurs in .
Let . Then . Note that is a -bit vector generated by by Statement (iii) of Lemma 9. Considering , we conclude that is contained in if and only if is contained in . Therefore, the -morphism determines a one–one correspondence between ’s and ’s as above.
Thus, an arc in is incident from some cycle in to some cycle in if and only if an arc in is incident from the nonzero cycle to . Therefore, is a contraction of .
Lemma 19. Let be as in Equation (54) and its characteristic function. LetThen is indecomposable if and only if the Boolean circuit is satisfiable.
Proof. By Theorem 12, is a potential set of . By Theorem 8, is nonsingular.
Suppose to be unsatisfiable. Then is empty as defined in (54), and hence the Boolean function is constant zero. In this case, is equivalent to and is hence decomposable.
Now suppose to be satisfiable.
Since and the nonzero cycles of contain all -bit vectors, there exists at least one nonzero cycle such that contains an -bit vector such that . Then the -bit vector in with its -morphic image minimal in is a vector in . Thus, is not empty and has at least one arc.
Assume that is decomposable. Note that and then is an isolated vertex in , implying by Theorem 8. Then by Proposition 2, , where and . By Corollary 4, is also a subFSR of . Thus, by Theorem 6, is either or . Anyhow, as shown above, has at least one arc, i.e., at least one nonzero cycle of is not an isolated vertex in . Then it follows from Theorem 8 that is not a subFSR of . Therefore, below we only have to consider , i.e., .
First, we claim that each odd cycle (i.e. any cycle in ) has indegree at most . Otherwise, suppose that has indegree in . Let be the weakly connected component containing and denote the set of the dual cycles . On the one hand, recall that each even cycle (i.e., any cycle in ) has outdegree in . Hence, even cycles outnumber odd cycles in . On the other hand, by Theorem 4 and Corollary 2, since cycles in and those in have the same -morphic images, is also a weakly connected component in and its cycles are joined into one cycle of since we have assumed . However, odd cycles outnumber even cycles in , and cycles in are hence not weakly connected since each even cycle has outdegree at most , yielding contradiction. So, the claim is proved.
Second, we conclude that for any , and are in different weakly connected components. Otherwise, there is an undirected path connecting with . In , each cycle in has indegree and at most outdegree, and each cycle in has outdegree and at most indegree as in the above claim. Thus, the only possible undirected path from to is an arc from to . However, there exists no arc from to . Otherwise, in the contraction graph there is a self-loop of (see Figure 4), contradictory to Lemma 6. So, by Theorem 8, there are no self-dual cycles in .
Therefore, a weakly connected component in (as shown in Figure 4) is of the form with an arc incident from to , where and are distinct nonzero cycles of . Notice that,The same as above, because we assume , by Equation (56), Theorem 4 and Corollary 2, we conclude that and also join into one cycle of , i.e., there is an arc from to . Consider the contraction graph . If so, in , an arc goes from to and another from to , implying that is not acyclic, contradictory to Lemma 6.
Thus, our assumption does not hold and is indecomposable.
| ||||||||||||
Lemma 20. There exists a polynomial-time algorithm for the transformation defined by Algorithm 3.
Note that occurs in a cycle of if and only if . Then Figure 10 presents the peudocode of the characteristic function of . The proof of Lemma 20 is similar to that of Lemma 17, and we omit it here.
Proof of Theorem 2. By Theorem 3, Lemmas 19 and 20, Algorithm 3 gives a polynomial-time Karp-reduction from the -complete problem CIRCUIT SATISFIABILITY to FSR INDECOMPOSABILITY. Therefore, we conclude that FSR INDECOMPOSABILITY is -hard.
6. Conclusion
Deciding irreducibility/indecomposability of FSRs is interesting for sophisticated circuit implementation and security analysis of stream ciphers. We studied both problems from the standing point of the worst-case computational complexity, and by now have proved that both the decision problems are -hard. Constructive examples are also given to show that there exist infinitely many irreducible (resp. indecomposable) FSRs that are decomposable (resp. reducible). We hope that this theoretical work serves as an inspiration to further explore the underlying obstacles to generally finding subFSRs or decomposing FSRs. To find subFSRs and -factors of FSRs with no help of groundbreaking computing, it is therefore recommended to make good use of their specific feedback logics. Additionally, it is also interesting and challenging to study the average-case computational complexity of irreducibility and indecomposability of FSRs in future.
Data Availability
The data used to support the findings of this study are included within the article.
Disclosure
A preprint of this paper has previously been published [30]. Differing from the earlier version, this paper gives a new proof of Theorem 2 using the language of graph theory, and also shows that irreducible (resp. indecomposable) FSRs do not exclude decomposable (resp. reducible) FSRs.
Conflicts of Interest
The author declares that he has no known competing financial interests or personal relationships that could have appeared to influence the work reported in this paper.
Acknowledgments
The author would like to express sincere gratitude to Prof. Dr. Klaus Pommerening for his invaluable and encouraging suggestions to improve the manuscript. This work is supported by the National Key R&D Program of China (Grant No. 2021YFB3100200) and the National Natural Science Foundation of China (Grant No. 61502441).