Title :
A statistical test for stream ciphers based on the maximum order complexity
Author_Institution :
Ciphertec cc, South Africa
Abstract :
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
Keywords :
binary sequences; circuit feedback; computational complexity; cryptography; gamma distribution; shift registers; statistical analysis; binary sequences; computationally efficient statistical test; gamma distribution; maximum order complexity; memoryless feedback function; non-linear feedback function; random sequence; secret key cryptography; shortest feedback shift register; statistical test; stream ciphers; Binary sequences; Delay; Distributed computing; Feedback; Public key; Public key cryptography; Random sequences; Security; Shift registers; Testing;
Conference_Titel :
Communications and Signal Processing, 1998. COMSIG '98. Proceedings of the 1998 South African Symposium on
Conference_Location :
Rondebosch
Print_ISBN :
0-7803-5054-5
DOI :
10.1109/COMSIG.1998.736951
