Structural Properties of Cryptographic Sequences - Computational Intelligence in Security for Information Systems - page 133

Sketch of proof: The result follows from the fact that those generalized self-

shrinking sequences involve primary sequences i for A i =0with i in the range

2 L− 2 i< 2 L− 1 , that is precisely the range of values of their corresponding

linear complexity.

≤

4 Generation of Cryptographic Sequences in Terms of

Primary Sequences

From the previous section, it can be deduced that the bit-wise addition of correct
primary sequences (or equivalently a correct choice of the p -tuple ( A 0 ,A 1 ,A 2 ,
...,A p− 1 )) results in the generation of sequences with controllable period and
linear complexity. Nevertheless, from a cryptographic point of view balancedness
must be taken into account.
In this sense, it must be noticed that the complementation of the last bit of
a generalized self-shrinking sequence with period 2 L− 1 means that the resulting
sequence includes the primary sequence
n
2 L− 1

2 L− 1

( n ≥ − 1) (15)

− 1

That is the identically null sequence except for the last element that is 1.
This implies that the obtained sequence will have period T =2 L− 1 ,maximum
linear complexity LC =2 L− 1 and quasi-balancedness as the difference between
the number of 1's and 0's will be just one. For a cryptographic range L = 128,
this difference is negligible. In brief, the selection of coecients A i allows one to
control period, linear complexity and balancedness of the solution sequences.

5 Conclusions

In this work, it is shown that generalized self-shrinking sequences are particular
solutions of homogeneous linear difference equations with binary coecients.
At the same time, there are other many solution sequences not included in the
previous class that can be used for cryptographic purposes. The choice of the
p -tuple ( A 0 ,A 1 ,A 2 ,...,A p− 1 ) of binary coecients allows one:

1. To get all the solutions of the above linear difference equation (12), among
them there are sequences with application in stream cipher.
2. To obtain sequences with controllable period, linear complexity and bal-
ancedness.

It must be noticed that, although generalized self-shrinking sequences and self-
shrinking sequences are generated from LFSRs by irregular decimation, in prac-
tice they are simple solutions of linear equations. Thus, the solutions of linear
difference equations with binary coecients appear as excellent binary sequences
with cryptographic application. An ecient computation of such sequences seems
to be a good tool for the generation of keystream sequences in stream ciphers.