A New Method for Finding Affine Sub-Families of NFSR Sequences
Jiamin Zhang, Tian Tian, Wen‐Feng Qi, Qun-Xiong Zheng · IEEE Transactions on Information Theory · 2018
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.