Berlekamp-Massey algorithm: case when sequence length is less than double the length of the LFSR

Question

Suppose that we have a sequence of $N$ digits which is produced by a Linear Feedback Shift Register (LFSR) and the shortest such LFSR is of length $L$. A very important tool in cryptanalysis of stream ciphers (among many other things) is the Berlekamp-Massey algorithm; if $2L\leq N$, this algorithm will produce the unique shortest LFSR of length $L$ that generates the given sequence.

I just knew this as a fact but never really gave a look at the algorithm. Now I'm reading the paper by Massey that presents the algorithm and I was kind of surprised to realize that the algorithm returns a desired LFSR in any case, even if $2L>N$, however in that case we don't have a unique LFSR that generates the sequence, but $2L-N$ of them (in the binary case).

So why do we always refer to the Berlekamp-Massey algorithm only for the case when $2L\leq N$? Practically speaking, what kind of lengths $L$ do we use in cryptosystems, and can the algorithm be used when $2L>N$ and $N$ is "reasonably" close to $2L$? Or is the algorithm useless in that case regardless?

Answer 1

The Berlekamp-Massey algorithm find the shortest LFSR that can produce the given sequence. Formally, if the sequence has $n$ elements $S_0, S_1, \ldots, S_{n-1}$, then the algorithm finds $\lambda_1, \lambda_2, \ldots, \lambda_t$ such that for $i = t, t+1, \ldots, {n-1}$, the following equation holds: $$ S_{i} +S_{i-1}\lambda_{1} + S_{i-2}\lambda_2 + \cdots + S_{i-t}\lambda_t = 0, \tag{1} $$ that is, $$S_i = -\bigr(S_{i-1}\lambda_{1} + S_{i-2}\lambda_2 + \cdots + S_{i-t}\lambda_t \bigr). \tag{2}$$ Note that for $i=t$, we have $$S_{t} = -\bigr(S_{t-1}\lambda_{1} + S_{t-2}\lambda_2 + \cdots + S_{0}\lambda_t \bigr)\tag{3}$$ The idea is that the initial loading of the LFSR is $(S_0, S_1, \ldots, S_{t-1})$, and the weighted sum of the LFSR contents stated in $(3)$ is fed back into the right end of the shift register as the LFSR contents shift one place to the left. Thus, the new state of the LFSR is $(S_1, S_2,\ldots, S_{t-1}, S_t)$. In later clock cycles, the LFSR will contain $(S_{i-t}, S_{i-t+1},\ldots, S_{i-1})$, the feedback will compute $S_i$ as given in $(2)$ and so the new state of the LFSR is $(S_{i-t+1}, S_{i-t+2},\ldots, S_{i-1}, S_i)$. The output of the LFSR is the symbol falling off the left end and is thus $S_0, S_1, \ldots, S_{n-1}$.

The dsp.SE reader will recognize that if we define polynomials $$S(z) = S_0 +S_1z + \cdots + S_{n-1}z^{n-1}, ~~ \Lambda(z) = 1 + \lambda_1z + \cdots + \lambda_tz^t,$$ then the left side of $(1)$ is the coefficient of $z^i$ in the product $S(z)\Lambda(z)$. Thus, the product $S(z)\Lambda(z)$ contains no terms of degree $t, t+1, \ldots, n-1$.

Turning to the problem at hand, if the given sequence can in fact, generated by a LFSR of length $L$ (where $L$ is the length of the shortest LFSR capable of generating $S(z)$), and if $n \geq 2L$, then the Berlekamp-Massey algorithm will find the feedback coefficients $\lambda_1, \lambda_2, \lambda_L$ of the unknown LFSR as soon as it has examined the first $2L$ terms $S_0, S_1, \ldots, S_{2L-1}$ of the given sequence. It will then process the remaining terms $S_{2L}, S_{2L+1}, \ldots, S_{n-1}$ of the sequence, and will discover that the same LFSR that it has already found will generate these remaining terms as well.

It is important to remember that the Berlekamp-Massey algorithm will find the shortest LFSR that will generate $(S_0, S_1, \ldots, S_{n-1})$, and this LFSR might not be the same one that was actually used to generate $(S_0, S_1, \ldots, S_{n-1})$. Any sequence that can be generated via a LFSR with feedback polynomial $\Lambda(z)$ can also be generated via a (longer) LFSR with feedback polynomial $\Lambda(z)\Psi(z)$, and the Berlekamp-Massey algorithm will find the shortest shift register that works.

What if $L$ is such that $2L > N$, then the Berlekamp-Massey algorithm will find the shortest LFSR that will generate $(S_0, S_1, \ldots, S_{n-1})$. The length of this LFSR will generally not be $L$ and its feedback coefficients will in general not be the same as those of the actual LFSR that was used to generate the sequence. If at a later time, the terms $S_{n}, S_{n+1}, \ldots, S_{2L-1}$ become known, the algorithm will extend the LFSR and ultimately come up with the right answer, but for now, it will simply find the shortest LFSR that will generate $(S_0, S_1, \ldots, S_{n-1})$.

---

In broad terms, the Kolmogorov-Chaitin theory of complexity of a sequence says that for almost all sequences of length $n$, the shortest program that can print out the sequence has length $n+c$ where $c$ is a constant. In other words, for most sequences, one can do little better than simply store the sequence in memory and print it out: there are no computational methods that will allow you to generate the sequence via calculations. Thus, given an arbitrary sequence of length $n$, the Berlekamp-Massey algorithm will typically find an LFSR of length $n-1$ that stores the first $n-1$ symbols and then calculates $S_{n-1}$ via $(2)$ with $t = i = n-1$.

The answer to the OP's question

"...can the algorithm be used when $2L>N$ and $N$ is "reasonably" close to $2L$?"

is that the algorithm can be used, and it will find the shortest LFSR that will generate $(S_0, S_1, \ldots, S_{n-1})$, but this LFSR will typically not be of length $L$ and the feedback polynomial will typically differ from that of the LFSR of length $L$ that is known to generate $(S_0, S_1, \ldots, S_{n-1})$.

Answer 2

@Sarwate gave a clear answer. I'm just following with an example to demonstrate his answer for the potential benefit of other readers:

Consider the sequence with minimal polynomial $\Lambda(z)=z^6+z^5+z^4+z+1$. With initial state $100111$ this starts as $1001110110000011\dots$ and repeats every $63$ bits ($63$ is its period). So here $L=6$.

• If we try Berlekamp-Massey with the first 12 ($=2L$) or more digits we do get the correct minimal polynomial $\Lambda(Z)$, as expected;
• If we input $10$ digits $1001110110$ we are lucky; we get the output $0z^6+z^5+z^3+z+1,\,z^6+z^5+z^2+z+1,\,z^6+z^5+z^4+z+1$. We don't get a unique polynomial because the linear span of $1001110110$ happens to be $6$ and $2\cdot 6 > 10$. However it happens (again, because we are lucky) that we get the correct answer among them. The zero leading coefficient in the first one means that the output bit of the corresponding LFSR is not tapped;
• If we input $11$ digits $10011101100$ then the situation is similar and we get the output $0z^6+z^5+z^3+z+1,\,z^6+z^5+z^2+z+1$. Although the linear span is again $6$, we are not lucky this time and we do not get $\Lambda(z)$ among the output polynomials;
• If we input less than $10$ digits, we don't even get polynomials of degree $6$ so there is no chance we are obtaining $\Lambda(z)$.

So indeed, if we input less than $2L$ terms of the secret sequence, we will not generally obtain the correct linear span or polynomial, although that may happen out of luck.