Keystream Generators Based on Irregular Decimation

Abstract

In this chapter, we study the definition and the principal characteristics of the main keystream generators based on irregular decimation: the shrinking generator, the self-shrinking generator, the modified self-shrinking generator and the generalized self-shrinking generator.

In this chapter, we study the definition and the principal characteristics of the main keystream generators based on irregular decimation: the shrinking generator, the self-shrinking generator, the modified self-shrinking generator and the generalized self-shrinking generator.

First of all, we need to recall the concept of decimation. Let {v _i}, i = 0, 1, 2, …, be a linear recursive sequence over a finite field. The decimation of this sequence by distance d is a new sequence {v _d⋅i}, i = 0, 1, 2, …, obtained by taking every dth term of {v _i} (see [22]).

FormalPara Example 2.1

Consider the LFSR of length 3 with characteristic polynomial p(x) = 1 + x + x ³. If we consider the initial state {1 0 0}, the PN-sequence generated is the following:

$$\displaystyle \begin{aligned} \{a_i\}=\{1\ 0\ 0\ 1\ 0\ 1\ 1\ \ldots \}. \end{aligned}$$

Since p(x) is primitive, {a _i} has maximum-period equal to 7. Now, if we denote by {b _i} the sequence obtained decimating {a _i} by distance 2:

$$\displaystyle \begin{aligned} \begin{array}{cccccccc} b_0&b_4& b_2 &b_5 &b_3&b_6&&\\ \uparrow & \uparrow & \uparrow& \uparrow& \uparrow& \uparrow&\\ 1 & 0 & 0 &1 &0 &1 &1 &\ldots\\ \end{array} \end{aligned}$$

this sequence has the form {b _i} = {a _2i} = {1 0 0 1 0 1 1 …}. Notice that {b _i} is the same PN-sequence {a _i}. This is due to the fact that the period of the PN-sequence and the distance of decimation are relatively primes, that is, $\gcd (7,2)=1$ [41]. $\blacksquare$

2.1 Shrinking Generator

In this section we present the main characteristics of the first generator based on irregular decimation, the shrinking generator.

2.1.1 Definition and Basic Features

The shrinking generator (SG) was introduced by Coppersmith, Krawczyk and Mansour in [15]. This generator was very attractive in that moment, due to its conceptual simplicity, since it combines two binary maximum-length LFSRs in a simple way. The output sequence of the generator is produced by shrinking the output sequence of one LFSR under the control of the other. In other words, the PN-sequence {a _i}, i = 0, 1, 2, …, produced by one of the registers, denoted by R ₁, decimates the PN-sequence {b _i}, i = 0, 1, 2, …, produced by the other register, denoted by R ₂. Let L ₁ and L ₂, with $\gcd (L_1, L_2)=1$, be the number of stages (or length) of R ₁ and R ₂ and $p_1(x), p_2(x)\in \mathbb {F}_2[x]$ their characteristic polynomials, respectively. We consider these polynomials to be primitive, to assure the output sequences are maximum-period or PN-sequences. We will denote by {s _j}, j = 0, 1, 2, …, the output sequence of the generator and we will call it the shrunken sequence. The decimation rule is very simple:

$$\displaystyle \begin{aligned}\begin{cases} \text{If } a_i=1,\text{ then } s_j=b_i.\\ \text{If } a_i=0, \text{ then }b_i \text{ is discarded},\\ \end{cases}\end{aligned}$$

that is, the output bit of R ₂ is taken if the current bit of R ₁ is 1, otherwise it is discarded.

The key of the generator is the initial states of both registers and the characteristic polynomials, which are recommended to be part of the key.

When $\gcd (L_1, L_2)=1$, the period of the shrunken sequence is

$$\displaystyle \begin{aligned}T=2^{L_1-1}\left(2^{L_2}-1\right),\end{aligned}$$

and its linear complexity, denoted by LC, satisfies $L_22^{L_1-2} < LC \leq L_2 2^{L_1-1}.$ Furthermore, the shrunken sequence is balanced and has other good cryptographic properties [15]. Therefore, this scheme is supposed to be suitable for practical implementation in encryption procedures.

Let us see an illustrative example of this generator.

Example 2.2

Consider R ₁ the LFSR with characteristic polynomial p ₁(x) = 1 + x + x ² and initial state {1 0}. The PN-sequence generated by R ₁, in this case, is {a _i} = {1 0 1 …} . Consider also R ₂ the LFSR with characteristic polynomial p ₂(x) = 1 + x + x ³ and initial state {1 0 0}. The PN-sequence produced is {b _i} = {1 0 0 1 0 1 1…}. Then, the shrunken sequence can be computed in the following way:

The shrunken sequence {s _j} has period 14 and, thanks to the Berlekamp–Massey algorithm [63], it is not difficult to check that its characteristic polynomial is $p(x)^2=\left (1+x^2+x^3\right )^2$, consequently its linear complexity equals 6. $\blacksquare$

Despite its simplicity, there are currently no known attacks better than exhaustive search of the initial states of the registers, when the characteristic polynomials are secret.

It is worth noticing that there may be multiple initial states that produce the same keystream sequence (equivalent keys). For example, let us consider the registers used in Example 2.2. If we consider initial states {0 1} and {0 1 1}, respectively, we obtain the following shrunken sequence:

On the other hand, if we consider initial states {1 1} and {1 1 1}, respectively, we obtain the following shrunken sequence:

which is the same as before. Due to leading 0s in the first two PN-sequences, both keys generate the same shrunken sequence. For this reason, we always consider initial states that start with 1. Thus, the effective key size is smaller than the key space.

From now on, we consider two registers R ₁ and R ₂, with primitive characteristic polynomials $p_1(x), p_2(x)\in \mathbb {F}_2[x]$, lengths L ₁ and L ₂ and $\gcd (L_1,L_2)=1$, respectively. Besides, the PN-sequences generated by both registers are denoted by {a _i} and {b _i} and have periods $T_1=2^{L_1}-1$ and $T_2=2^{L_2}-1$, respectively. We assume without loss of generality that a ₀ = 1.

2.1.2 Characteristic Polynomial and Interleaved PN-Sequences

In this section, we will see that the shrunken sequence is constructed interleaving one unique PN-sequence and the form of its characteristic polynomial.

Theorem 2.1 ([9])

The $2^{L_1-1}$ sequences obtained decimating the shrunken sequence by distance $2^{L_1-1}$ starting in positions 0, 1, 2, … , $2^{L_1-1}-1$ , respectively, are PN-sequences with characteristic polynomial

$$\displaystyle \begin{aligned} p(x)=\left(x+\alpha^{T_1}\right)\left(x+\alpha^{2T_1}\right)\left(x+\alpha^{4T_1}\right)\cdots \left(x+\alpha^{2^{L_2-1}T_1}\right), \end{aligned}$$

where $\alpha \in {\mathbb {F}_{2}^{L_{2}}}$ is a root of the polynomial p ₂(x) and $T_1=2^{L_1}-1$ is the period of the PN-sequence generated by R ₁.

All the interleaved PN-sequences of the shrunken sequence are generated by the same characteristic polynomial, this means that all of them are shifted versions of the same PN-sequence.

It is worth remarking that, since α is a primitive element of the field ${\mathbb {F}_{2}^{L_{2}}},\ p_2(x)$ needs to be primitive.

Example 2.3

Consider two registers, R ₁ and R ₂, with characteristic polynomials p ₁(x) = 1 + x + x ³ and p ₂(x) = 1 + x + x ⁴ and initial states {1 0 0} and {1 0 0 0}, respectively. Denote by {a _i} and {b _i} the PN-sequences generated by R ₁ and R ₂, respectively. The shrunken sequence generated by these registers has period T = 60 and is given by

$$\displaystyle \begin{aligned} \{s_j\}=\{1 0 0 0 1 1 1 1 1 0 1 0 0 0 0 1 1 0 0 1 0 1 1 0 1 1 0 0 1 1 0 1 0 1 0 0 0 0 1 0 1 1 1 0 0 0 1 1 0 1 1 1 0 1 0 1 1 0 1 1 \ldots\}. \end{aligned} $$

If we decimate the shrunken sequence {s _j} by distance $2^{L_1-1}=4$ starting in positions 0, 1, 2 and 3, respectively, we obtain four interleaved PN-sequences:

(2.1)

According to Theorem 2.1, the characteristic polynomial of the interleaved PN-sequences is given by

$$\displaystyle \begin{aligned} p(x)=\left(x+\alpha^{7}\right)\left(x+\alpha^{14}\right)\left(x+\alpha^{28}\right) \left(x+\alpha^{56}\right)=1+x^3+x^4, \end{aligned}$$

where $\alpha \in \mathbb {F}_{{2}^{4}}$ is a root of p ₂(x). Therefore, the four interleaved PN-sequences are shifted versions of the same PN-sequence generated by p(x). In expression (2.1), we can check that the bits , and in the PN-sequence {s _4j} represent the starting points of the sequences {s _4j+i} (1 ≤ i ≤ 3), respectively. $\blacksquare$

Corollary 2.1 ([9, Corollary 1])

If L ₂ = L ₁ + 1, then the polynomial p(x), given in Theorem 2.1 , is the reciprocal polynomial of p ₂(x).

It is worth reminding that the reciprocal polynomial of the polynomial r(x) = r ₀ + r ₁ x + ⋯ + r _l−1 x ^l−1 + r _l x ^l is of the form r ^∗(x) = r _l + r _l−1 x + ⋯ + r ₁ x ^l−1 + r ₀ x ^l.

Now, we introduce the form of the characteristic polynomial of the shrunken sequence.

Theorem 2.2 ([28])

The characteristic polynomial of the shrunken sequence has the form p(x)^m , for $2^{L_1-2}<m\leq 2^{L_1-1}$ with p(x) as in Theorem 2.1.

Notice that $p(x)^{2^{L_1-1}}$ always generates the shrunken sequence, but sometimes this polynomial might not be the characteristic polynomial of lowest degree. For instance, consider again the shrunken sequence generated in Example 2.3. In this case, we computed the polynomial p(x) = 1 + x ³ + x ⁴. Now, we know that $p(x)^4=\left (1+x^3+x^4\right )^4$ generates the shrunken sequence and, since p(x)³ does not generate it, we can assume that p(x)⁴ is its characteristic polynomial.

Example 2.4

Consider the registers with characteristic polynomials p ₁(x) = 1 + x ² + x ⁵ and p ₂(x) = 1 + x + x ² + x ³ + x ⁴ + x ⁵ + x ⁷, respectively. Consider the shrunken sequence generated by these two registers, which has period T = 2⁴(2⁷ − 1) = 2032. According to Theorem 2.1, the polynomial p(x) can be computed as:

$$\displaystyle \begin{aligned} p(x)&=\left(x+\alpha^{31}\right)\left(x+\alpha^{62}\right)\left(x+\alpha^{124}\right)\left(x+\alpha^{248}\right)\left(x+\alpha^{496}\right)\\ &\quad \left(x+\alpha^{992}\right)\left(x+\alpha^{1984}\right)\\ &=1+x+x^3+x^6+x^7,\end{aligned} $$

where $\alpha \in \mathbb {F}_{2^{7}}$ is a root of p ₂(x). In this case, we know that p(x)¹⁶ generates the shrunken sequence. However, it is easy to check that p(x)¹⁵ is the characteristic polynomial.$\blacksquare$

Interestingly, p(x) only depends on p ₂(x) and L ₁. This means that if we fix a primitive polynomial p ₂(x) and we consider any primitive polynomial with degree L ₁ we always obtain the same p(x).

2.1.3 Shrunken Sequences and Difference Equations

In this section, we show that the shrunken sequence is a solution of a difference equation.

The characteristic polynomial p(x) (with degree L) of an arbitrary sequence {a _i} specifies its linear recurrence relationship. This means that the element a _i can be written as a linear combination of the previous elements:

$$\displaystyle \begin{aligned} a_i\oplus\sum_{j=1}^{L}c_ja_{i-j}=0, \quad i\geq L. \end{aligned}$$

The linear recursion can be expressed as a linear difference equation:

$$\displaystyle \begin{aligned} \left[ E^L\oplus \sum_{j=1}^{L}c_jE^{L-j} \right] a_i=0, \quad i\geq 0, \end{aligned} $$

(2.2)

with E being the one-sided shift operator that acts on the sequence terms:

$$\displaystyle \begin{aligned} \begin{array}{c} E a_i=a_{i+1}, \\ E^ka_i=a_{i+k} .\\ \end{array} \end{aligned} $$

(2.3)

If the characteristic polynomial p(x) is primitive and α is one of its roots, then α,α ²,$\alpha ^{2^2}$, … , $\alpha ^{2^{L-1}}$ are the L different roots of such a polynomial as well as primitive elements of $\mathbb {F}_{2^{L}}$ [59]. Now, if the characteristic polynomial of an arbitrary sequence {s _j} is of the form p(x)^m, then its roots will be the same as those of p(x) but each one with multiplicity m. The corresponding difference equation is given by

$$\displaystyle \begin{aligned} \left[ E^L\oplus \sum_{k=1}^{L}E^{L-k} \right]^m s_j=0, \end{aligned}$$

and its solutions are of the form $s_j=\sum _{i=0}^{L-1}\sum _{k=0}^{m-1}\binom {j}{k}A^{2^{i}}_{k}\alpha ^{2^{i}j}$, where A _k is an arbitrary element in $\mathbb {F}_{2^{L}}$. Different choices of A _k give rise to different sequences {s _j}. A particular choice of A _k provides the shrunken sequence generated by p(x)^m.

2.1.4 Obtaining the Second PN-Sequence from the Shrunken Sequence

Given the shrunken sequence {s _j} generated by two registers, R ₁ and R ₂, it is possible to compute the PN-sequences generated by both registers. In this section, we explain how to obtain the PN-sequence {b _i} produced by R ₂.

Proposition 2.1 ([11, Proposition 1])

Let δ ∈{1, 2, 3, …, T ₂ − 1} be such that T ₁ δ = 1 mod T ₂ . If the first PN-interleaved sequence is decimated by distance δ, then the resultant sequence is {b _i}.

Example 2.5

Consider again the shrunken sequence obtained in Example 2.3 and consider the interleaved PN-sequences given in expression (2.1). Since L ₁ = 3 and L ₂ = 4, the unique value for δ such that 7δ = 1 mod 15 is δ = 13. This means that if we decimate the first interleaved sequence {s _4j} by distance 13, according to Proposition 2.1, we obtain {b _i}, the PN-sequence generated by p ₂(x) = 1 + x + x ⁴:

$$\displaystyle \begin{aligned} \begin{array}{cccccccccccccccc} &b_0 & b_7 & b_{14} & b_6 & b_{13} & b_{5} & b_{12} & b_4 & b_{11} & b_3 & b_{10} & b_2 & b_{9} & b_1 & b_8\\ &\uparrow &\uparrow &\uparrow &\uparrow &\uparrow &\uparrow &\uparrow &\uparrow &\uparrow &\uparrow &\uparrow &\uparrow &\uparrow &\uparrow &\uparrow\\ \{s_{4j}\}: &1 & 1 & 1 & 0 & 1 & 0 & 1 & 1 & 0 & 0 & 1 & 0 & 0 & 0 & 1\\ \{s_{4j+1}\}: &0 & 1 & 0 & 0 & 0 & 1 & 1 & 1 & 1 & 0 & 1 & 0 & 1 & 1 & 0\\ \{s_{4j+2}\}: &0 & 1 & 1 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 1 & 1 & 1 & 0 & 1\\ \{s_{4j+3}\}: &0 & 1 & 0 & 1 & 1 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 1 & 1 & 1\\ \end{array} \end{aligned}$$

In this case {b _i} = {1 0 0 0 1 0 0 1 1 0 1 0 1 1 1…}. $\blacksquare$

The previous proposition leads us to the following two results.

Corollary 2.2 ([11, Corollary 2])

If the polynomials p ₁(x), $p_2(x)\in \mathbb {F}_2[x]$ have degrees L ₁ and L ₁ + 1, respectively, then δ = T ₂ − 2.

In Example 2.5, we had that L ₂ = L ₁ + 1 = 4, then it was not necessary to solve the equation given in Proposition 2.1, it was enough to compute δ = T ₂ − 2 = 13.

Theorem 2.3 ([11, Corollary 1])

If the shrunken sequence is decimated by distance $2^{L_1-1}\delta$ , then the obtained sequence is the PN-sequence {b _i}.

Example 2.6

Consider again the shrunken sequence obtained in Example 2.2. In this example we had that L ₁ = 2 and L ₂ = 3, then according to Corollary 2.2, δ = 5. Now, according to Theorem 2.3, we know that if we decimate the shrunken sequence by distance 10:

$$\displaystyle \begin{aligned} \begin{array}{ccccccccccccccc} b_0&&b_3&&b_6 & &b_2&&b_5&&b_1&&b_4&\\ \uparrow& &\uparrow& &\uparrow& &\uparrow&&\uparrow&&\uparrow& &\uparrow& &\\ 1&0&1&1&1&0&0&0&1&1&0&1&0&1&\ldots\\ \end{array} \end{aligned}$$

then we obtain again the PN-sequence generated by the second register, R ₂:

$$\displaystyle \begin{aligned} \{b_i\}=\{1\ 0\ 0\ 1\ 0\ 1\ 1\ \ldots\}.\end{aligned} $$

$\blacksquare$

2.1.5 Obtaining the First PN-Sequence from the Shrunken Sequence

In this section, we analyse how to recover the PN-sequence {a _i} produced by R ₁ from the shrunken sequence {s _j}.

Assume the first interleaved PN-sequence of {s _j} is denoted by {v _i}. Since the other interleaved sequences are shifted versions of the same PN-sequence, it means they are shifted versions of {v _i}. Then, we assume they have the form $\left \{v_{d_1+i}\right \}, \left \{v_{d_2+i}\right \}, \ldots , \left \{v_{d_{2^{L_1-1}-1}+i}\right \}$, for some positions $d_i\in \left \{0, 1, 2, \ldots , 2^{L_2-2}\right \}$:

In order to illustrate this idea, consider again Example 2.3. We had four interleaved PN-sequences that correspond to:

$$\displaystyle \begin{aligned} \{s_{4j}\}=\{v_i\}, \quad \{s_{4j+1}\}=\{v_{d_1+i}\}, \quad \{s_{4j+2}\}=\{v_{d_2+i}\} \quad \text{and} \quad \{s_{4j+3}\}=\{v_{d_3+i}\}. \end{aligned}$$

In this case, the positions are d ₁ = 9, d ₂ = 5 and d ₃ = 3:

(2.4)

Before introducing the next result, it is worth reminding that a maximum-length LFSR of L stages produces a PN-sequence with 2^L−1 ones in its first period [41].

Example 2.7

Consider the LFSR with characteristic polynomial p(x) = 1 + x + x ⁴ and initial state {1 1 1 1}. The PN-sequence generated by this register is given by

$$\displaystyle \begin{aligned}\{ 1 \ 1 \ 1 \ 1 \ 0\ 0 \ 0\ 1\ 0\ 0\ 1\ 1\ 0\ 1\ 0\ \ldots \}. \end{aligned}$$

Notice that this PN-sequence has 2³ ones in its period, that is, in its first 15 bits. $\blacksquare$

Theorem 2.4 ([11, Proposition 2])

If $\{0,i_1, i_2, \ldots , i_{2^{L_1-1}-1}\}$ is the set of indices of the 1s in the PN-sequence {a _i} in its first period, then $d_k=\delta \cdot i_k\ \mathit{\text{mod}}\ \left (2^{L_1-1}-1\right )$ , for $k=1, 2,\ldots , 2^{L_1-1}-1$ , where δ has the form given in Proposition 2.1.

In Example 2.3, we had four interleaved PN-sequences {v _i}, $\{v_{i+d_1}\}$, $\{v_{i+d_2}\}$ and $\{v_{i+d_3}\}$ and δ = 13. We know that d ₁ = 9, d ₂ = 5 and d ₃ = 3 (see expression (2.4)). Then, according to Theorem 2.4, we can compute the indices {0, i ₁, i ₂, i ₃} of the four 1s in the first period of {a _i} (i ₀ = 0, without loss of generality) solving the following system:

$$\displaystyle \begin{aligned}\begin{cases} 13\cdot i_1 = 9 \text{ mod } 15 \\ 13\cdot i_2 = 5 \text{ mod } 15 \\ 13\cdot i_3 = 3 \text{ mod } 15. \end{cases}\end{aligned} $$

Therefore, the set of indices is given by {0, 3, 5, 6} and then the PN-sequence produced by R ₁ is given by {a _i} = {1 0 0 1 0 1 1…}.

2.2 Self-Shrinking Generator

The self-shrinking generator (SSG) was introduced by Meier and Staffelbach in [67]. They presented a simple structure using only one maximal-length LFSR, whose output sequence {a _i} is self-decimated. The key consists of the initial state of the register and the characteristic polynomial is again recommended as part of the key.

Let L be the length and $p(x)\in \mathbb {F}_2[x]$ the characteristic polynomial of the register. We consider again p(x) primitive, to assure the output sequence has maximum-period. We will denote by {s _j}, j = 0, 1, 2, …, the output sequence of the generator and we will call it, the self-shrunken sequence (SS-sequence). The decimation rule is very simple,

$$\displaystyle \begin{aligned}\begin{cases} \text{If } a_{2i}=1,\text{ then } s_j=a_{2i+1}.\\ \text{If } a_{2i}=0, \text{ then }a_{2i+1} \text{ is discarded},\\ \end{cases}\end{aligned} $$

that is, pairs of bits are considered: if a pair happens to take the value 10 or 11, this pair is taken to produce the bit 0 or 1, depending on the second bit of the pair. On the other hand, if a pair happens to be 01 or 00, it will be discarded.

Example 2.8

Consider the LFSR of L = 3 stages with characteristic polynomial p ₁(x) = 1 + x ² + x ³ and initial state {1 0 0}. The corresponding PN-sequence is given by {1 0 0 1 1 1 0 …}. Now the self-shrunken sequence can be computed in the following way:

$$\displaystyle \begin{aligned} R: \underbrace{1\quad \pmb{0}}_{\pmb{0}} \quad 0 \quad 1 \quad \underbrace{ 1 \quad \pmb{1}}_{\pmb{1}} \quad 0 \quad 1 \quad 0 \quad 0 \quad \underbrace{1 \quad \pmb{1}}_{\pmb{1}} \quad \underbrace{1 \quad \pmb{0}}_{\pmb{0}} \quad \ \ \ldots\end{aligned} $$

The corresponding self-shrunken sequence is given by {s _j} = {0 1 1 0 …}. $\blacksquare$

The period T of a self-shrunken sequence [67] produced by a maximal-length LFSR of L stages satisfies

$$\displaystyle \begin{aligned}T \geq 2^{\lfloor \frac{L}{2}\rfloor}.\end{aligned}$$

Due to experimental observations, we claim that the period of the self-shrunken sequences is always T = 2^L−1, when L > 3 and p(x) is primitive. However, no proof has been found yet. We encourage the reader to prove this claim.

According to Meier and Staffelbach [67] and Blackburn [5], we can say that the linear complexity satisfies

$$\displaystyle \begin{aligned}2^{\lfloor\frac{L}{2}\rfloor}<LC\leq 2^{L-1}-(L-2).\end{aligned}$$

Again, due to experimental observations, we claim that the lower bound for the linear complexity can be improved to: LC > 2^L−2. However, no proof has been found so far. Actually, this is also a natural consequence of T = 2^L−1. We let the reader think about this open problem.

Proposition 2.2 ([33])

The characteristic polynomial of the self-shrunken sequences has the following form: p _LC(x) = (1 + x)^LC , where LC is the linear complexity of such a sequence.

For instance, consider Example 2.8. We had the self-shrunken sequence {s _j} = {0 1 1 0 …} produced by p(x) = 1 + x ² + x ³. It is possible to check that the self-shrunken sequence has period T = 2³⁻¹ and its characteristic polynomial is p ₃(x) = (1 + x)³ (see Berlekamp–Massey algorithm [63]). Consequently, the linear complexity of {s _j} is LC = 3.

2.3 Modified Self-Shrinking Generator

In [53] Kanso introduced a variant of the self-shrinking generator called the modified self-shrinking generator (MSSG). This generator, intended for hardware implementation, uses an extended selection rule based on the XORed value of a pair of bits in the PN-sequence. The resultant sequences are balanced and have good statistical properties.

The decimation rule is very simple and can be described as follows: given three consecutive bits {a _3i, a _3i+1, a _3i+2}, i = 0, 1, 2, …, of a PN-sequence {a _i}, the output sequence {s _j} is computed as

$$\displaystyle \begin{aligned}\begin{cases} \text{If } a_{3i}+a_{3i+1}=1 \text{ then } s_j=a_{3i+2},\\ \text{If } a_{3i}+a_{3i+1}=0 \text{ then } a_{3i+2} \text{ is discarded}. \end{cases}\end{aligned}$$

The output sequence {s _j} is known as the modified self-shrunken sequence (MSS-sequence).

Example 2.9

Let us consider the LFSR of three stages with characteristic polynomial q(x) = 1 + x ² + x ³ and initial state {1 1 1}. The PN-sequence generated by this register is given by {1 1 1 0 1 0 0 …}. In this case, the modified self-shrunken sequence can be computed as follows:

The sequence {s _j} = {0 1 1 0 …} (encircled bits) is the MSS-sequence generated by q(x). $\blacksquare$

Now, we are ready to study the properties of this generator. According to [53], if we consider a maximal-length LFSR of L (odd) stages, then:

• 1. The period T of the MSS-sequence satisfies

  $$\displaystyle \begin{aligned} 2^{\lfloor \frac{L}{3} \rfloor} \leq T \leq 2^{L-1}. \end{aligned}$$

• 2. The linear complexity LC of the MSS-sequence satisfies

  $$\displaystyle \begin{aligned} 2^{\lfloor \frac{L}{3} \rfloor -1} \leq T \leq 2^{L-1}-(L-2). \end{aligned}$$

Although the MSS-sequences seem to have lower bounds on the period and linear complexity than those of the SSG, Kanso claimed that these sequences provide a higher level of security against several well-known attacks. Besides, Kanso demonstrated that the MSS-sequences possess better randomness properties than those of the SSG. In next section, we will see that both sequences belong to the family of generalized self-shrunken sequences.

2.4 Generalized Self-Shrinking Generator

In [46] Hu and Xiao introduced a specialization of the shrinking generator and a generalization of the self-shrinking generator. This new generator, known as generalized self-shrinking generator (GSSG), produces a family of sequences that has group structure. These sequences are also balanced and have quite good correlation.

2.4.1 Definition and Features

Let {a _i}, i = 0, 1, 2, …, be a PN-sequence produced by an LFSR of L stages. Now, consider the binary vector

$$\displaystyle \begin{aligned} G=\left[g_0, g_1, \ldots, g_{L-1}\right]\in \mathbb{F}_{2}^{L} \end{aligned}$$

and the sequence {v _i}, i = 0, 1, 2, …, sometimes denoted by v(G), such that

$$\displaystyle \begin{aligned} v_i=g_0a_i+g_1a_{i-1}+\dots+g_{L-1}a_{i-L+1}. \end{aligned}$$

Consider the following decimation rule:

$$\displaystyle \begin{aligned}\begin{cases} \text{If } a_i=1, \text{ then } s_j=v_i.\\ \text{If } a_i=0, \text{then } v_i \text{ is discarded}.\\ \end{cases}\end{aligned}$$

This means that the PN-sequence {a _i} decimates the sequence {v _i}, for each value of G.

We denote the sequence {s _j}, j = 0, 1, 2, …, by s(v) or s(G) and call it generalized self-shrunken sequence (GSS-sequence). The family of GSS-sequences $s(a)=\{s(G) {\ | \ } G\in \mathbb {F}_{2}^{L}\}$ is the family of self-shrunken sequences based on the PN-sequence {a _i}.

It is worth noticing that the family of sequences

$$\displaystyle \begin{aligned}\left\{\{v_i\}_{i\geq 0}, {\ | \ } v_i=g_0a_i+g_1a_{i-1}+\dots+g_{L-1}a_{i-L+1}, G\in\mathbb{F}_{2}^{L}, G\neq 0\right\}\end{aligned}$$

includes all the 2^L − 1 shifts sequences of {a _i}. Then, the PN-sequence {a _i} decimates shift versions of itself.

For simplicity, we refer G as the decimal representation of the vector G.

Example 2.10

Consider the PN-sequence

$$\displaystyle \begin{aligned}\{a_i\}= \{1\ 1\ 1\ 0\ 0\ 1\ 0\ldots \}\end{aligned}$$

generated by the primitive polynomial p(x) = 1 + x + x ³. Since {a _i} has period equal to 7, then we get 7 generalized self-shrunken sequences based on {a _i} plus the identically zero sequence (see Table 2.1). $\blacksquare$

Table 2.1 GSS-sequences generated by 1 + x + x ³

The family s(a) is an L-dimensional linear space on $\mathbb {F}_2$, so it is an Abelian group with neutral element {0 0 … 0 0} [46]. Then, $\left |s(a)\right |=2^L$.

The following results evidence the relation between some values of G and the generated sequences.

Theorem 2.5 ([46, Theorem 1])

• 1. s(G) = {0 0 0 …} if and only if G = [0, 0, …, 0].

• 2. s(G) = {1 1 1 …} if and only if G = [1, 0, …, 0].

• 3. s(G) is balanced otherwise.

Theorem 2.6 ([46, Theorem 5])

• 1. There are two sequences from s(G) with period equal to 2, which are {1 0 1 0…} and {0 1 0 1 …}.

• 2. There are two sequences from s(G) with period equal to 1, which are {0 0 0 0…} and {1 1 1 1 …}.

This means that the identically 0 sequence, the identically 1 sequence and the sequences that alternate 0 and 1 belong to every family of GSS-sequences. Furthermore, the sequences different from the identically 0 sequence and the identically 1 sequence are balanced.

Theorem 2.7 ([10, Theorem 5])

The characteristic polynomial of the GSS-sequences generated by a PN-sequence is p _LC(x) = (1 + x)^LC , where LC is the linear complexity of the considered GSS-sequence.

Example 2.11

Consider the family of GSS-sequences obtained from the LFSR with characteristic polynomial p(x) = 1 + x + x ³ in Example 2.10. There are four different sequences (the others are shifted versions of these four) and it is possible to check, via the Berlekamp–Massey algorithm, that their corresponding characteristic polynomials are given by

$$\displaystyle \begin{aligned} \{0\}:& \ 0\ 0 \ 0\ 0 \rightarrow p_0(x) = 1\\ \{4\}:& \ 1\ 1 \ 1\ 1 \rightarrow p_1(x) = (1+x)\\ \{1,5\}:& \ 1\ 0 \ 1\ 0 \rightarrow p_2(x) = (1+x)^2\\ \{2,3,6,7\}:&\ 0\ 1 \ 1\ 0 \rightarrow p_3(x) = (1+x)^3. \end{aligned} $$

$\blacksquare$

The generalized self-shrinking generator has hardly been studied. For example, there are no works on the period nor the complexity of the sequences. Since any PN-sequence possesses 2^L−1 ones in its first period [41], it seems evident that the period of the sequences s(G) is a power of 2, that is, 2^t with t ≤ L − 1. Again, due to experimental observations, we can claim that the period of the sequences different from the sequences mentioned in Theorem 2.6 is always 2^L−1. Furthermore, the linear complexity of these sequences seems to satisfy:

$$\displaystyle \begin{aligned}2^{L-2} < LC\leq 2^{L-1}-(L-2).\end{aligned}$$

The upper bound can be obtained adapting the proof given by Blackburn for the self-shrunken sequence in [5] . None of the other bounds has been proven yet. We encourage the reader to think about it.

Given a primitive polynomial p(x) of degree L, the 2^L−1 GSS-sequences generated are divided into L − 1 different groups depending on their LC:

• 1 sequence of LC = 0, the identically 0 sequence.

• 1 sequence of LC = 1, the identically 1 sequence.

• 2 sequences of LC = 2, sequences {0 1 0 1 …} and {1 0 1 0 …}.

• 2ⁱ⁺¹ sequences of linear complexity LC _i, with 2^L−2 < LC _i ≤ 2^L−1 − (L − 2), for i = 1, 2, …, L − 2, and L ₁ < L ₂ < ⋯ < L _L−2.

Example 2.12

In Table 2.2, we can find the 32 GSS-sequences generated by p(x) = 1 + x ² + x ³ + x ⁴ + x ⁵. There are:

Table 2.2 GSS-sequences generated by p(x) = 1 + x ² + x ³ + x ⁴ + x ⁵

• 1 sequence with LC = 0, the identically 0 sequence.

• 1 sequence with LC = 1, the identically 1 sequence.

• 2 sequences with LC = 2, sequences {0 1 0 1 …} and {1 0 1 0 …}.

• 4 sequences with LC = 10.

• 8 sequences with LC = 12.

• 16 sequences with LC = 13.

$\blacksquare$

2.4.2 Generalized Self-Shrunken Sequences and Difference Equations

In this section we present the GSS-sequences as solutions of linear difference equations.

According to Theorem 2.7 and other results seen in the previous section, we know that the characteristic polynomial of the GSS-sequence generated by a maximal-length LSFR is of the form:

$$\displaystyle \begin{aligned} p_t(x)=(1+x)^t, \quad t\leq 2^{L-1}-(L-2). \end{aligned}$$

This implies a linear recurrence relationship of the form:

$$\displaystyle \begin{aligned} (E+1)^t s_j=0, \end{aligned} $$

(2.5)

with E being the one-sided shift introduced in expression (2.3). Expression (2.5) represents a linear binary constant coefficient difference equation whose characteristic polynomial p _t(x) has a unique root λ = 1 with multiplicity t. The solutions of this equation are binary sequences {s _j} whose generic term is given by

$$\displaystyle \begin{aligned} s_j= {{j}\choose{0}}c_0+\binom{j}{1}c_1+\cdots+\binom{j}{t-1}c_{t-1}, \end{aligned}$$

with $c_j\in \mathbb {F}_2$ and ${{j}\choose {i}}$ as binomial coefficients modulo 2, for i = 0, 1, …, t − 1 [59]. In fact, each binomial coefficient defines a succession of binary values with constant period T _j. Table 2.3 depicts the first binomial coefficients with their corresponding binary sequences and periods. The 2^t possible choices of c _i, i = 0, 1, …, t − 1, provide the different binary sequences {s _j} that satisfy expression (2.5). Particular choices of c _i give rise to the generalized self-shrunken sequences generated by an LFSR of L stages (including the SS-sequence and the MSS-sequence). Interestingly, all the solutions of expression (2.5) are the bit-wise sum of the basic sequences coming from the binomial coefficients (see Table 2.3) and weighted by c _i, i = 0, 1, …, t − 1.

Table 2.3 Binomial coefficients reduced modulo 2, binary sequences and periods

2.4.3 Relationship with the Modified Self-Shrinking Generator

In this section, we see how the MSS-sequence generated by a primitive polynomial q(x) of degree L can be obtained as one of the GSS-sequences generated by another primitive polynomial of the same degree.

Theorem 2.8 ([10, Theorems 1–2])

The MSS-sequence obtained by self-decimating a PN-sequence with characteristic polynomial q(x) of degree L, with L odd, can be computed as one of the GSS-sequences using another primitive polynomial p(x) of degree L given by

$$\displaystyle \begin{aligned} p(x)=\left(x+\alpha^{3}\right)\left(x+\alpha^{6}\right)\left(x+\alpha^{12}\right)\cdots \left(x+\alpha^{3\cdot 2^{L-1}}\right), \end{aligned}$$

where $\alpha \in \mathbb {F}_{{2}^{L}}$ is a root of q(x).

Notice that the self-shrunken sequence is also a generalized self-shrunken sequence [107]. When the PN-sequence {v _i} is shifted 2^L−1 bits regarding the PN-sequence {a _i}, then the generated sequence is the self-shrunken sequence.

Example 2.13

Given the LSFR with characteristic polynomial q(x) = 1 + x ² + x ⁵ and the initial state {1 1 1 1}, we can obtain the following MSS-sequence:

$$\displaystyle \begin{aligned} \{1 \ 1\ 0\ 0\ 1\ 0\ 0\ 1\ 0\ 1\ 1\ 1\ 0\ 0\ 1\ 0\ \ldots\}. \end{aligned}$$

According to Theorem 2.8, this sequence can be also obtained using the GSSG with primitive polynomial

where $\alpha \in \mathbb {F}_{{2}^{5}}$ is a root of q(x). In Table 2.2 we can find the 32 GSS-sequences generated by p(x) using the different values of G. For G = 5 (G = [1 0 1 0 0]), the generated GSS-sequence is a shifted version of the MSS-sequence generated by q(x).

The self-shrunken sequence generated by p(x) = 1 + x ² + x ³ + x ⁴ + x ⁵ is also a GSS-sequence. For instance, consider the initial state {1 1 1 1 1}, we generate the following SS-sequence:

$$\displaystyle \begin{aligned}\{ 1\ 1\ 0\ 1\ 0\ 0\ 0\ 1\ 1\ 0\ 1\ 1\ 1\ 0\ 0\ 0\ \ldots \},\end{aligned}$$

which is exactly the GSS-sequence corresponding to G = 3 (G = [0 0 0 1 1]) (see Table 2.2). $\blacksquare$

Now, in order to know which GSS-sequence is the MSS-sequence, we need to recall the definition of Zech logarithm. Zech logarithms are named after Julius Zech who published in 1849 a table of this type logarithms (which he called addition logarithms) for doing arithmetic in $\mathbb {Z}_p$. These logarithms are also called as Jacobi logarithms after C.G.J. Jacobi who used them for number theoretic investigations [48].

Definition 2.1

Let $\mathbb {F}_q$ be the Galois field of q elements and $\alpha \in \mathbb {F}_{q}$ a primitive element. The Zech logarithm with basis α is the application ${\mathcal {Z}}_{\alpha }:\mathbb {Z}_{q} \rightarrow \mathbb {Z}_{q}^*\cup \{ \infty \}$, such that each element $t\in \mathbb {Z}_{q}$ corresponds to ${\mathcal {Z}}_{\alpha }(t)$, attaining $1+\alpha ^t=\alpha ^{{\mathcal {Z}}_{\alpha }(t)}$.

Now we are ready to compute the value of G that produces a MSS-sequence as a GSS-sequence.

Theorem 2.9 ([10, Theorem 3])

The MSS-sequence generated from a PN-sequence with primitive characteristic polynomial q(x) is also a GSS-sequence obtained from a PN-sequence generated by a primitive polynomial p(x) (see Theorem 2.8) that decimates a shifted version of itself with shift (D − 2)3⁻¹ mod (2^L − 1), where $D={\mathcal {Z}}_{\alpha }(1)$ , $\alpha \in \mathbb {F}_{{2}^{L}}$ is a root of p(x) and L is the degree of p(x) and q(x).

Assume {a _i} is a PN-sequence generated by a primitive polynomial and assume $\{b_i\}=\{a_{i+(D-2)3^{-1}}\}$ is the shifted version of {a _i} that is decimated by {a _i} in order to obtain the MSS-sequence (see Theorem 2.9). According to the definition of GSSG, to find the value of G = [g ₀, g ₁, …, g _L−1] that generates {b _i} from {a _i}, we have to know L bits of {a _i} and 2L − 1 bits of {b _i} to solve the following system:

(2.6)

The exact necessary bits of each sequence are $\{a_i\}_{i=0}^{L-1}$ and $\{b_i\}_{i=0}^{L-1}\cup \{b_i\}_{i=2^{L}-L}^{2^L-2}$, respectively.

Let us see a clarifying example.

Example 2.14

Consider the MSS-sequence generated in Example 2.13:

$$\displaystyle \begin{aligned} \{s_j\}=\{1\ 1\ 0\ 0\ 1\ 0\ 0\ 1\ \underline{\pmb{0}}\ 1\ 1\ 1\ 0\ 0\ 1\ 0 \ \ldots \}. \end{aligned} $$

(2.7)

According to Theorem 2.8, {s _j} can be generated as a GSS-sequence using the primitive polynomial p(x) = 1 + x ² + x ³ + x ⁴ + x ⁵. Given the PN-sequence {a _i} generated by p(x), we consider the PN-sequence {b _i} = {a _i+k} which is a shifted version of {a _i}, with shift $k=(\mathcal {Z}_{\alpha }({1})-2)\cdot 3^{-1}\bmod {31}$, α root of q(x). This means that {b _i} = {a _i+26}.

Taking the initial state {1 1 1 1 1}, we can generate the PN-sequence

$$\displaystyle \begin{aligned}\{a_i\}=\{1\ 1\ 1\ 1\ 1\ 0\ 1\ 1\ 1\ 0\ 0\ 0\ 1\ 0\ 1\ 0\ 1\ 1\ 0\ 1\ 0\ 0\ 0\ 0\ 1\ 1\ 0\ 0\ 1\ 0\ 0 \ \ldots \}\end{aligned}$$

that decimates a shifted version of itself,

$$\displaystyle \begin{aligned}\{b_i\}=\{\mathbf{0}\ \mathbf{1}\ \mathbf{1}\ \mathbf{1}\ \mathbf{0}\ 0\ \mathbf{0}\ \mathbf{1}\ \mathbf{0}\ 1\ 0\ 1\ \mathbf{1}\ 0\ \mathbf{1}\ 0\ \mathbf{0}\ \mathbf{0}\ 0\ \mathbf{1}\ 1\ 0\ 0\ 1\ \mathbf{0}\ \mathbf{0}\ 1\ 1\ \mathbf{1}\ 1\ 1\},\end{aligned}$$

with shift equal to 26. Thus, we obtain the output sequence

$$\displaystyle \begin{aligned} \{ 0 \ 1\ 1\ 1\ 0\ 0\ 1\ 0\ 1\ 1\ 0\ 0\ 1\ 0\ 0\ 1\ \ldots \},\end{aligned}$$

which is a shifted version of the MSS-sequence {s _j} starting at the underlined position (see expression (2.7)).

Now, in order to obtain the value of G = [g ₀, g ₁, g ₂, g ₃, g ₄], we have to solve the system given in (2.6). In this case we have

$$\displaystyle \begin{aligned} \{a_i\}_{i=0}^4 =\{0\ 1\ 1\ 1\ 0\},\quad \{b_i\}_{i=0}^4 =\{1\ 1\ 1\ 1\ 1\} \quad \text{and} \quad \{b_i\}_{i=27}^{30} =\{0\ 1 \ 0 \ 0 \}. \end{aligned} $$

Therefore, system (2.6) has the following form:

$$\displaystyle \begin{aligned}\begin{cases} 0=g_0+g_3\\ 1=g_0+g_1+g_4 \\ 1=g_0+g_1+g_2\\ 1=g_0+g_1+g_2+g_3\\ 0=g_0+g_1+g_2+g_3+g_4, \end{cases}\end{aligned}$$

whose solution is G = [0 0 1 0 1] (G = 5). Then, the GSSG with primitive polynomial p(x) = 1 + x ² + x ³ + x ⁴ + x ⁵ produces the MSS-sequence {s _j} for G = 5 (G = [0 0 1 0 1]) for any given initial state. For example, in Table 2.4, we can see that the GSS-sequence produced with G = 5 using three different initial states provides shifted versions of the same sequence, the MSS-sequence $\left \{1\ 1\ 0\ 0\ 1\ 0\ 0\ 1\ 0\ 1\ 1\ 1\ 0\ 0\ 1\ 0\right \}$. $\blacksquare$

Table 2.4 GSS-sequences obtained with G = 5