Evaluation Of Statistical Tests For Randomness

Random sequences are widely used in various felds of computer sci-ence, especially cryptography, where its applications have high require-ments for randomness of sequences. In practice, random sequences aregenerated by pseudorandom number generators, which are in fact deter-ministic algorithms. The regularities in the sequences generated by pseu-dorandom number generators may lead to security risks. Theoretical testsand statistical tests can be used to analyze the randomness of a sequence.Since it is very difcult to develop a theoretical test, we usually use statis-tical tests to do the analysis.Inrecentyears,computerscientistshavedevelopedanumberofstatis-ticaltests. Somepopulartestsincludethe15testsinthetestsuiteproposedby NIST (National Institute of Standards and Technology), several tests inthe DIEHARD test suite developed by Marsaglia, and other classical tests.These tests focus on diferent aspects of a sequence, and it is important toknow the relations between these tests. Soto proposed two open questions,i.e. the independence of the tests and the coverage or span of tests. Thisdissertation focuses on a number of statistical tests, and their correlationand coverage using conditional entropy method, in order to answer the twoquestions proposed by Soto. Some statistical tests are adapted for testingshort sequences if necessary while preserving the original ideas of tests. Finally, theevaluationresultisanalyzedandseveralconclusionsaredrawnand a new test suite with larger coverage than NIST’s is proposed.