Overview

The one-to-one correspondences among sequences, polynomial functions, and boolean functions serve as bridges for connections between sequence design with good correlation and constructions of boolean functions with strong cryptographic properties. These materials will be discussed in this chapter. It is worth pointing out that the cryptographic properties of boolean functions discussed in the literature are related to the Hadamard transform of functions (fundamental theory of linear cryptanalysis) and the convolution of functions (fundamental theory of differential cryptanalysis).

To construct pseudorandom sequences with large linear span, a natural way is to apply boolean functions to a set of LFSRs (these LFSRs may be equal). The resulting sequences are called filtering function sequences if the LFSRs are equal or combinatorial function sequences if they are distinct. From the one-to-one correspondence between boolean functions in n variables and polynomial functions from to , as introduced in Section 10.1 of Chapter 10, the known constructions, including GMW sequences (all four types), Gold-pair sequences, Kasami and generalized Kasami sequences, and bent function sequences can be considered special cases of this general construction.

For cryptographic applications, from known pairs of plaintext and ciphertext, one can obtain segments of the output sequences of the filtering/combinatorial generators. Given this fact, an attacker tries to find initial states of these LFSRs by computing various correlations of the output sequences in order to get the entire output sequences. To prevent this type of attack, one of the effective ways is to employ boolean functions with certain low...