1
$\begingroup$

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).

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ I wonder if the approximate problem is related to Learning Parity with Noise. $\endgroup$
    – D.W. ♦
    Mar 15, 2022 at 21:53
  • 1
    $\begingroup$ @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 $\endgroup$
    – Alex P
    Mar 16, 2022 at 12:41

1 Answer 1

Reset to default
2
$\begingroup$

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.

You can simply search the papers citing Niederreiter's review paper and find out more.

Edit: The OP has clarified the problem which I had slightly misunderstood. Indeed the paper by Lauder and Paterson is the way to go in this case.

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ 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. $\endgroup$
    – Alex P
    Mar 16, 2022 at 20:08
  • $\begingroup$ 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? $\endgroup$
    – Alex P
    Mar 16, 2022 at 20:13
  • $\begingroup$ To the best of my knowledge, one cannot overcome this discrepancy in any meaningful fashion $\endgroup$
    – kodlu
    Mar 17, 2022 at 15:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.