# Size of nonlinear filter sequence to recover LFSR feedback polynomial

Let's suppose that there is a filter generator which based on $$n$$-size LFSR.

Denote a feedback polynomial as $$g(x_1, x_2, \dots, x_n)$$ and nonlinear filter function as $$f(x_1, x_2, \dots, x_n)$$.

Let $$a = a_1, a_2, \dots, a_k$$ be filter generator output sequence.

Attacker knows $$f$$ and $$a$$.

1. What are boundaries for $$k$$ to recover $$g(x_1, x_2, \dots, x_n)$$?
2. How to recover $$g(x_1, x_2, \dots, x_n)$$?
• Need more information. There are a number of nonlinear modifications to LFSR(s) with nonlinear filters or combination generators. Commented Feb 22, 2023 at 6:04
• Thanks you @kodlu for the answer and the description of the architectures of the generators. And, I apologize for the inaccurate wording, since I meant a non-linear filter generator. I'll add more info to the first post. Commented Feb 23, 2023 at 5:14
• Define it more precisely since usually what's in the answer is what's called filter generator. Edit your question with math specification. Commented Feb 23, 2023 at 5:43

For clarification, the linear complexity of a possibly nonlinear sequence is $$L,$$ then $$2L$$ bits are sufficient to determine the LFSR that will generate it, via the Berlekamp Massey algorithm. The list below examines some common types of nonlinear sequence generators.

Filter generator: (supply more details in question please)

The feedback function is linear (so an LFSR) but output is a nonlinear function applied to certain taps of the LFSR. There is a classical upper bound by Key, a lower bound due to Rueppel (Analysis and Design of Stream Ciphers book), as well as more recent results on the linear complexity of the output. The details can be quite technical to summarize, however.

Combination Generator:

Let there be $$k$$ LFSRs with pairwise relatively prime lengths $$L_i,$$ for $$i=1,\ldots,k$$ and feedback connections corresponding to primitive polynomials of degree $$L_i.$$ Then combine the outputs of these LFSRs, by means of a Boolean function $$f:\{0,1\}^k\rightarrow \{0,1\}$$ with nonlinearity $$r.$$ The nonlinearity of the function $$f(x_1,x_2,x_3)$$ is the highest degree of a monomial in its algebraic normal form. See my answer to this question for more on how to determine the nonlinearity.

Then, the linear complexity of the output sequence resulting from this combination generator is given by $$f(L_1,L_2,L_3)$$ where the function is evaluated over the integers. See the answer to this question for a specific example.

NLFSR:

The period and linear complexity of feedback registers with nonlinear boolean functions as feedback functions is unsolved in general but there are some partial results. There is a chapter "Nonlinear shift registers – A survey and challenges" by Tor Helleseth, in the book Algebraic Curves and Finite Fields, De Gruyter, eds Niederreiter et al. You can find a copy online if you search, but original is paywalled. Some of the methods there are closely related to deBruijn cycles.

Specific Designs:

There are some results on linear complexity of outputs of specific designs such as Trivium, Grain, Shrinking Generator (nonlinearity introduced by an algorithmic shrinking operation), Wikipedia is a good place to start.

• Thanks. I saw Key's result about filter generator in Algebraic Shift Register Sequences book by Goresky and Clapper. But I think formally it is another problem. Commented Feb 23, 2023 at 5:27