Back to Search
Start Over
A New Method for Finding Affine Sub-Families of NFSR Sequences.
- Source :
- IEEE Transactions on Information Theory; Feb2019, Vol. 65 Issue 2, p1249-1257, 9p
- Publication Year :
- 2019
-
Abstract
- 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(x<subscript>0</subscript>, x<subscript>1</subscript>,...,x<subscript>n</subscript>) = x<subscript>0</subscript>⊕f<subscript>1</subscript>(x<subscript>1</subscript>,...,x<subscript>n-1</subscript>)⊕x<subscript>n</subscript> be a characteristic function of an n-stage NFSR, where n is a positive integer. Let deg(f) = d > 1 and f<subscript>[d]</subscript> 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 Σ<subscript>i∈S</subscript>c<subscript>i</subscript> x<superscript>i</superscript>, where c<subscript>i</subscript> ∈ F<subscript>2</subscript> and S consists of all subscripts of variables appearing in f<subscript>[d]</subscript>. That is to say, every linear sub-family of G(f) is a factor of some polynomial Σ<subscript>i∈S</subscript>c <subscript>i</subscript>x<superscript>i</superscript> over the finite field F<subscript>2</subscript>. 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 F<subscript>2</subscript>. 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. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 00189448
- Volume :
- 65
- Issue :
- 2
- Database :
- Complementary Index
- Journal :
- IEEE Transactions on Information Theory
- Publication Type :
- Academic Journal
- Accession number :
- 134231208
- Full Text :
- https://doi.org/10.1109/TIT.2018.2858769