A statistical test for stream ciphers based on the maximum order complexity

The maximum order complexity determines the shortest feedback shift register which can generate a given sequence utilising a memoryless, possibly non-linear, feedback function. The maximum order complexity of a sequence is a potentially useful measure of the randomness of 8 sequence. In this paper a statistical test based on the maximum order complexity is proposed. The proposed test requires that the distribution of the maximum order complexity of a random sequence of arbitrary length is known. Erdmann and Murphy (1997) derived an expression which approximates the distribution of the maximum order complexity. Evaluating this expression is computationally expensive and an alternative approximation to the distribution of the maximum order complexity is proposed. The alternative approximation is then used to construct a computationally efficient statistical test which may be used to evaluate the randomness of a sequence. The proposed test is specifically concerned with binary sequences and the distribution of the maximum order complexity of binary sequences