# Generate degree-bound LFSR to approximate given sequence

Given an output sequence, $$S$$, we can use the Berlekamp-Massey algorithm to find the shortest LFSR, of order $$n \leq |S|$$, which exactly generates that sequence. Is it possible to efficiently compute an LFSR, in $$GF(2)$$, of order $$n \leq n_0 < |S|$$, which best approximates $$S$$? Best approximation means with the fewest possible errors, and by errors we consider the element-wise discrepancies (i.e. no insertions/deletions are allowed).

I searched for similar papers and the only relevant one I could find was Modified Berlekamp-Massey algorithm for approximating the k-error linear complexity of binary sequences. However, it is an exponential algorithm (and I don't quite understand it).

• I wonder if the approximate problem is related to Learning Parity with Noise.
– D.W.
Mar 15, 2022 at 21:53
• @D.W. I think it is $n <= |S|$. When the polynomial given by B-M has a degree $<= |S|/2$, it is unique. Take a look here embeddedrelated.com/showarticle/1099.php Mar 16, 2022 at 12:41

The measure you are interested in is usually called $$k-$$error linear complexity. See this review in Asiacrypt 2003 by Niederreiter. There are unpaywalled versions of this paper around. The cryptanalytic goal (first described in the book Stability Theory of Stream Ciphers by Ding et. al.) is to determine (given some fixed $$k>0$$) the shortest LFSR generating a sequence of length $$N.$$
There are various algorithms for computing it under various assumptions. For example if the sequence is assumed to have period $$p^n$$ and is over $$GF(p)$$ faster algorithms are possible. Keywords to look for include the Games-Chan algorithm (complexity $$O(n)$$ for sequence length $$2^n$$), Stamp and Martin algorithm (modification of Games-Chan). Look at Meidl's work hereaand elsewhere as well.
• I was aware of the measure, but it does not generate the LFSR itself, which is what I ultimately want. I found the paper "Computing the Error Linear Complexity Spectrum of a Binary Sequence of Period $2^n$" by Lauder and Paterson, which is quite close to what I want. The idea was to find the first $k$ in the spectrum for which the complexity is below $n_0$, then compute the error sequence $e$ (as described in the paper) to achieve that complexity and, finally, use Berlekamp-Massey's algorithm on the sequence $S \oplus e$ to get the desired LFSR. Mar 16, 2022 at 20:08
• Of course, Lauder-Paterson require sequences with a period of length $2^n$, which is restrictive. My solution to this is to append as many $0$s as necessary to complete a power of 2, and assign these bits a cost of 0. The only problem with this approach is that the Lauder-Paterson algorithm gives the complexity of the sequence $s^\infty$, where $s$ is a single period-sequence, whereas Berlekamp-Massey generates the LFSR for the given sequence with the aim of producing it only once. Is there any modification/correction I can make to overcome this discrepancy? Mar 16, 2022 at 20:13