Definition 3.1 The linear complexity of a sequence is the minimum number of stages of an LFSR that generates the sequence.

We employ the notation s for a finite sequence of bits and (s) for the periodic sequence obtained by appending copies of s. The linear complexity of a periodic sequence (s) is just the "length" of the shortest linear recurrence which generates (s), i.e., the degree of the corresponding characteristic polynomial. Also, the linear complexity of a sequence (s) with period n is bounded above by n since the recurrence s_i = s_i-n (which has characteristic polynomial x_n + 1 ) will generate (s).

For example, consider the sequence in (2.1). This sequence has linear complexity four, since (s) is periodic and the degree of its characteristic polynomial is four.

There is an elegant and efficient method for determining the linear complexity of any finite or periodic sequence. This procedure is the well-known Berlekamp-Massey algorithm [7]. The Berlekamp-Massey algorithm requires only 2n consecutive bits to completely determine a sequence with linear complexity n. In the special case where (s) is binary with period 2ⁿ, the lesser-known Chan-Games algorithm [3] is more efficient. (The paper [12] contains an alternative derivation of the Chan-Games algorithm which yields a slightly more general result.)

It follows that anyone who obtains 2n consecutive bits of (s) (where n is the linear complexity) can efficiently recover the entire pseudo-random sequence, and hence---in the case of a stream cipher---the entire "secret" message can be recovered. Therefore, a cryptographically strong sequence must have a high linear complexity.

However, a high linear complexity does not insure that a sequence is cryptographically strong. For example, the sequence

    (3.2)

As we mentioned in the previous section, m-sequences are generally regarded as statistically random. However, an m-sequence would be a poor choice for use in a stream cipher. An m-sequence with a characteristic polynomial of degree n produces an output sequence with period 2ⁿ - 1, but only 2n out of the 2ⁿ - 1 bits are required in order to completely determine the sequence.

In the previous section it was shown that a high linear complexity is a necessary---but not sufficient---condition for a sequence to be cryptographically strong. Additional tests are therefore needed in order to determine "stronger" cryptographic sequences. Rueppel [9] has shown that the linear complexity profile is useful in this regard.

The linear complexity profile of (s) is obtained by plotting the linear complexity of s₀,s₁,...,s_n-1 against n, for n=1,2,.... For example, in Figure 1 the linear complexity profile of

Rueppel [9] states that a cryptographically strong sequence should have a linear complexity near the maximum possible, and its linear complexity profile should follow the n/2 line "closely but irregularly." The sequence (4.3) appears to satisfy these requirements.

We now propose a new measure of the complexity of periodic sequences which has application to the problem of identifying cryptographically strong pseudo-random sequences.

Definition 4.1 The k-error linear complexity of the periodic sequence

The k-error linear complexity can be interpreted as a worst-case measure of the linear complexity when k or fewer errors occur---and hence the terminology k-error linear complexity.

Observe that the 0-error linear complexity of any sequence is just the usual linear complexity. Also, the 1-error linear complexity of the sequence (3.2) is zero, since changing the final bit from 1 to 0 will produce the all-zero sequence, which has linear complexity zero (by definition).

The k-error linear complexity profile---i.e., the k-error linear complexity for k=0,1,2.... plotted against k---of the sequence (4.3) is shown in Figure 2. Above, we observed that (4.3) apparently passes the two tests given by Rueppel [9]. However, its k-error linear complexity profile is not reassuring, since an LFSR with just 7 stages correctly produces 30 out of every 32 bits of (s). Obviously, if we can recover such a high proportion of the sequence, a stream cipher employing (4.3) would be compromised. This example suggests that the k-error linear complexity may provide more information about the cryptographic strength of a pseudo-random sequence than other previously suggested methods.

The k-error linear complexity of any sequence could be found by repeated application of the Berlekamp-Massey algorithm [7] or, if appropriate, the Chan-Games algorithm [3]. But, to find the k-error linear complexity of (s) = (s₀,s₁,...,s_n-1) would require

We have found an efficient new algorithm for computing the k-error linear complexity in the case where (s) is a binary sequence with period 2ⁿ. This new algorithm---which appears in Figure 3---reduces to the Chan-Games algorithm [3] in the case k = 0. Next, we give a brief discussion of the Chan-Games algorithm before proving the validity of our new algorithm.

Given a binary sequence (s) with period 2ⁿ, let

a = s;  c = 0;  l = 2n;
cost[i] = 1, for i=0,1,...,l-1;
while l > 1 do
     l = l/2;  L = a0a1...al-1;  R = alal+1...a2l-1;
     b = L + R;  T = sum(bi ⋅ min(cost[i],cost[i+l]), for i=0 to l-1);
     if T ≤ k then
          k = k - T;
          for i = 0,1,...,l-1 do
               if bi = 1 then
                    if cost[i] ≤ cost[i+l] then
                         Li = Ri;  cost[i] = cost[i+l] - cost[i];
                    else
                         cost[i] = cost[i] - cost[i+l];
                    end if
               else
                    cost[i] = cost[i] + cost[i+l];
               end if
          next i 
          a = L;
     else
          c = c + l;
          a = b;
          cost[i] = min(cost[i],cost[i+l]), for i=0,1,...,l-1; 
     end if 
end while
if a0 = 1 and cost[0] > k then
     c = c + 1;
end if

We can now verify the k-error linear complexity algorithm in Figure 3.

Theorem 5.1 Let (s) be a binary sequence with period 2ⁿ and let 0 ≤ k ≤ 2ⁿ. Then the algorithm in Figure 3 computes c, the k-error linear complexity of (s), in n steps.

The vector of cost[i]'s is intended to measure the "cost"---in terms of the number of bit changes required in the original sequence s---of changing the current element a_i without disturbing the results of any previous steps. Now suppose that at some step j, the value of cost[i] correctly gives the cost of changing a_i. If b_i = 1, changing either L_i or R_i will force b_i = 0 and hence the cost of changing b_i is the minimum of the costs of changing L_i or R_i. Since the cost of changing L_i is cost[i] and the cost associated with R_i is cost[i + l] it follows that the variable T in Figure 3 correctly gives the total cost of forcing b = 0.

It remains to show that the cost[i]'s are correct at the end of step j. Consider the case where T ≤ k, b_i = 1, and cost[i] ≤ cost[i + l]. In this case we change L_i since it has the lower cost, thus forcing b_i = 0. Notice that at the end of this step we will let a = L (see the algorithm). Now if we change a_i in step j + 1 we have effectively restored L_i (in step j) to its previous value. In order to maintain b_i = 0 in step j, we must then change R_i (in step j) which has a net cost of cost[i + l] - cost[i], and hence cost[i] is computed correctly in this case. Other cases must be considered but they are similar; see [131 for details.

In Figure 4 our algorithm is applied to compute the 2-error linear complexity of