Cascade connection architectures of nonlinear feedback shift registers (NFSRs) have been widely used as the main components in the design of cryptographic algorithms, such as the Grain family of stream ciphers. It is known that the cascade connection of ann-stage NFSR into anm-stage NFSR is equivalent to an (n+m)-stage NFSR. However, the converse problem on decomposing an NFSR into the cascade connection of two smaller NFSRs has not been well addressed, which can be transformed to decomposing the characteristic functionhof the NFSR into the formh=f*gfor some nonlinearf,g, where “*” is a special composition of Boolean functions. In this paper, we present a complete and efficient method for such decomposition problem based on previous works. The framework of the decomposition consists of two steps. The first is to construct a candidate set forgas precise as possible, and the second is to verify each candidategand recover the correspondingf. We propose the notion of *-multiples of Boolean functions, and present three ways to take derivatives ofhto extract the low-degree *-multiples ofg, which are useful to determinegefficiently. Compared to existing methods, the new approach can provide a very small candidate set forgin most cases, with the size beingO(deg(h)), thereby achieving lower and more stable time costs in determining whetherhis *-reducible and enumerating all pairs (f,g) such thath=f*g(if it is *-reducible). Moreover, we show that the decomposition method also applies to shift-invariant maps, by establishing a connection between the *-product of Boolean functions and the composition of shift-invariant maps.

Nonlinear feedback shift registers (NFSRs) are an important building blocks in the design of stream ciphers over the past years. An NFSR is vulnerable to cryptanalysis if there are output sequences with low linear complexities. In this paper, we present a method to find output sequences of an NFSR with low linear complexities from a new perspective. Let f be the characteristic function of an NFSR, and let$f_{L}$be the linear part of f. First, we present some theoretical results in order to find sequences$\underline {a}\in G(f_{L})$such that$\underline {a}\in G(f)$. In particular, it is shown that if$f_{L}$has divisors of the form$g(x^{d})$, then$G(f)$is more likely to have linear sequences. Then, we introduce two kinds of isomorphisms of NFSRs which could be used to find more potential linear sequences in$G(f)$. Such isomorphisms induce a close relationship among the linear structures of NFSRs, whose realization relies on a type of decomposition of Boolean functions. As a generalization, we propose a framework to analyze the linear structure of a Galois NFSR. The idea is to focus on the Galois LFSR derived from the Galois NFSR by removing the nonlinear part, which can be transformed into an equivalent Fibonacci LFSR. Finally, we apply the results to some lightweight algorithms designed based on the cascade connections of NFSRs, and find several families of sequences generated by the main register of Lizard with linear complexities no more than 30.

Linear feedback shift registers (LFSRs) over integer residue rings are widely used to generate pseudorandom number, such as ZUC algorithm, truncated LCGs, truncated MRGs. Truncated Galois LFSRs are an important way to generate pseudorandom sequences. Methods to predict the whole sequences by the truncated sequences of the truncated Galois LFSRs are not only a crucial aspect of evaluating their security but also important concerns in their design. This paper studies the predictability of truncated Galois LFSRs. When the modulus and the state transition matrix are known, we first propose a lattice-based method to recover the initial state by the high-order truncated sequences, then discuss the condition that recovering the initial state by the low-order truncated sequences is meaningful, and finally solve the low-order case by transforming it into the high-order case. When the modulus and the state transition matrix are unknown, we generalize our recent work, using the resultant, the greatest common factor, and Kannan’s embedding technique in turn to recover the modulus, the characteristic polynomial, and the initial state. Moreover, we heuristically show that the state transition matrix can be successfully recovered only when all registers output sufficiently long truncated sequences. Experiments have verified the effectiveness of our methods.

In this paper, a new and efficient method for solving affine sub-families included in a family of nonlinear feedback shift register (NFSR) sequences is proposed. The linear case is focused on since the affine case is an analogy. Let f(x0,x1,...,xn) = x0⊕f1(x1,...,xn-1)⊕xnbe a characteristic function of an n-stage NFSR, where n is a positive integer. Let deg(f) = d > 1 and f[d]be the summation of all terms in the algebraic normal form of f whose degrees attain the maximum d. First, it is proved that every linear sub-family of G(f) is a sub-family of linear feedback shift register sequences generated by a characteristic polynomial of the form Σi∈Scixi, where ci∈ F2and S consists of all subscripts of variables appearing in f[d]. That is to say, every linear sub-family of G( f ) is a factor of some polynomial Σi∈Scixiover the finite field F2. This result is a well generalization of linear recurring sequences theory since it also holds if d = 1. Based on this result, a candidate set of linear sub-families could be obtained by polynomial factorizations over F2. Second, we propose a new method to verify a linear sub-family whose memory requirement and time complexity are clearer than the previous method. For instance, all affine sub-families of the 160-bit main register used in Grain v1 could be determined within two seconds by a PC using the new method in this paper, which is unobtainable for previous algorithms.

Grain-128 is a hardware oriented stream cipher based on the cascade connection of a 128-bit linear feedback shift register into a 128-bit quadratic nonlinear feedback shift register (NFSR). Its main register is in essence a quadratic NFSR, however its affine sub-families could not be solved by the previous methods. In this paper, it is shown that the family of sequences generated by the main register of Grain-128 includes no affine sub-families except a small one of order three. To achieve this goal, a new method is proposed for solving affine sub-families of general quadratic NFSRs. Let NFSR(f) be an NFSR with a quadratic characteristic function f . It is proved that the characteristic function of a linear sub-family of the NFSR(f) divides a linear combination of variables appearing in the quadratic terms of f , where the division can be seen as the univariate polynomial division over the finite field F2. This facilitates picking up a candidate set of linear sub-families through univariate polynomial factorization over F2. The affine case is an analogy. Besides, a useful new upper bound on the orders of affine sub-families of a quadratic NFSR is given.

This paper studies the distinctness of primitive sequences overZ/(M) modulo 2, whereMis an odd integer that is composite and square-free, andZ/(M) is the integer residue ring moduloM. A new sufficient condition is given for ensuring that primitive sequences generated by a primitive polynomialf(x) overZ/(M) are pairwise distinct modulo 2. Such result improves a recent result obtained in our previous paper, and consequently, the set of primitive sequences overZ/(M) that can be proven to be distinct modulo 2 is greatly enlarged.

LetMbe a square-free odd integer andZ/(M) the integer residue ring moduloM. This paper studies the distinctness of primitive sequences overZ/(M) modulo 2. Recently, for the case ofM=pq, a product of two distinct prime numberspandq, the problem has been almost completely solved. As for the case thatMis a product of more prime numbers, the problem has been quite resistant to proof. In this paper, a partial proof is given by showing that a class of primitive sequences of order 2n'+1 overZ/(M) is distinct modulo 2, wheren'is a positive integer. Besides as an independent interest, this paper also involves two distribution properties of primitive sequences overZ/(M), which are related closely to our main results.

Let p be an odd prime number, e an integer greater than 1, and Z/(pe) the integer residue ring modulo pe. In this paper, we obtain an improved result of the previous paper (IEEE Trans. Inf. Theory, 56(1) (2010) 555-563) on distribution properties of compressing sequences derived from primitive sequences over Z/(pe). It is shown that two primitive sequences α and b generated by a strongly primitive polynomial f(x) over Z/(pe) are the same, if there exist s∈ Z/(p) and k∈ Z(p)* such that the distribution of in their compressing sequences ae-1+η(a0,⋯.ae-2) and be-1+η(b0,⋯,be-2) is coincident at the positions t with α(t)=k, where η(x0,⋯,xe-2) is an (e-)-variable polynomial over Z/(p) with the coefficient of xe-2p-1⋯x1p-1x0p-1not equal to (-1)e· (p+1)/2 and α is an m-sequence over Z/(p)determined by f(x) and a. Compared with the previous result, this gives a more precise characterization on the positions of a compressing sequence, i.e., of the form ae-1+η(a0,⋯,ae-2), derived from a primitive sequence a over Z/(pe) that completely determines a. In particular, the result is also true for the highest level sequence ae-1by taking η(x0,⋯,xe-2)=0.

Let Z/(pe) be the integer residue ring with odd prime p and integer e ¿ 2. Any sequence a over Z/(pe) has a unique p-adic expansion a = a0+ a1· p + ··· + ae-1· pe-1, where aican be regarded as a sequence over Z/(p) for 0 ¿ i ¿ e - 1. Let f(x) be a strongly primitive polynomial over Z/(pe) and a, b be two primitive sequences generated by f(x) over Z/(pe). Assume ¿(x0,..., xe-1) = xe-1+ ¿(x0,..., xe-2) is an e-variable function over Z/(p) with the monomial (p+1)/2 xe-2p-1...x1p-1not pearing in the expression of ¿(x0,x1,..., xe-2). It is shown that if there exists an s ¿ Z/(p) such that ¿(a0(t),..., ae-1(t)) = s if and only if ¿(b0(t),..., be-1(t)) = s for all nonnegative t with ¿(i) ¿ 0, where ¿ is an m-sequence determined by f(x) and a0, then a = b. This implies that for compressing sequences derived from primitive sequences generated by f(x) over Z/(pe), single element distribution is unique on all positions t with ¿(t) ¿ 0. In particular, when ¿(x0,x1,..., xe-2) = 0, it is a completion of the former result on the uniqueness of distribution of element 0 in highest level sequences.