Complexity measures for testing binary keystreams

The complexity measures that have been proposed to test binary keystreams for use in stream cipher cryptosystems fall into two categories. Measures in the first category determine the size of a specific tool required to produce the sequence, for example the Turing-Kolmogorov-Chaitin complexity, the linear complexity, and the maximum order complexity. Measures in the second category are related to patterns that appear in the sequence, for example the Ziv-Lempel complexity. As measures in the two categories have different motivations, they often react differently to sequences with special structure. We will review these measures and discuss their reaction to certain types of sequences.;We next present a new complexity measure called the pattern counting complexity measure. This new measure is also related to the patterns that appear in the sequence. However unlike the Ziv-Lempel complexity measure, the pattern counting complexity measure is easy to describe and is easy to understand intuitively. The new measure also possesses some desirable characteristics in terms of consistency. Like the Ziv-Lempel complexity and the maximum order complexity, the distribution of the complexity and the distribution of the jumps in the complexity profile of random sequences have been difficult to compute exactly for the new measure. We will present a function that approximates the distribution of the size of the jumps in the pattern counting complexity profile of a random sequence and demonstrate how this function can be used to approximate the expected value of the pattern counting complexity as well.;Finally we propose a method of approximating the distribution of the maximum order complexity of random sequences. We will then demonstrate how the approximation can be used to estimate the expected value and variance of the maximum order complexity of a random sequence, and the expected value of the number and size of jumps in the maximum order complexity profile. We will show that our approximations of the distribution of the jumps in the pattern counting complexity profile, and the distribution of the maximum order complexity are very close to the true distributions for random sequences.