Information Technology Reference
In-Depth Information
On Independence and Sensitivity of Statistical
Randomness Tests
Meltem Sonmez Turan
1
,AliDoganaksoy
1
, and Serdar Boztas
2
1
Institute of Applied Mathematics
Middle East Technical University, Ankara, Turkey
{
msonmez,aldoks
}
@metu.edu.tr
2
School of Mathematical and Geospatial Sciences, RMIT University, Australia
serdar.boztas@ems.rmit.edu.au
Abstract.
Statistical randomness testing has significant importance in
analyzing the quality of random number generators. In this study, we
focus on the independence of randomness tests and its effect on the cov-
erage of test suites. We experimentally observe that frequency, overlap-
ping template, longest run of ones, random walk height and maximum
order complexity tests are correlated for short sequences. We also pro-
posed the concept of sensitivity, where we analyze the effect of simple
transformations on output
p
-values. We claim that whenever the effect
is significant, the composition of the transformation and the test may be
included to the suite as a new test.
Keywords:
Randomness testing, Coverage, Independence.
1
Introduction
Random numbers are widely used in many applications such as statistical sam-
pling, Monte Carlo simulation, numerical analysis, game theory, cryptography,
etc. In cryptography, the need for random numbers arises in key generation, au-
thentication protocols, digital signature schemes, zero-knowledge protocols, etc.
Using weak random numbers may result in an adversary ability to break the
whole cryptosystem. However, for many simulation applications strong random
numbers are not required, in other words, different applications may require
different levels of randomness.
Generating high quality random numbers is a very serious problem-and is
very dicult if deterministic methods are used. The best way to generate unpre-
dictable random numbers is to use physical processes such as radioactive decay,
thermal noise or sound samples from a noisy environment. However, generating
random numbers using these physical processes is extremely inecient. There-
fore, most systems use Pseudo Random Number Generators (PRNGs) based on
deterministic algorithms. Desired properties of PRNGs are (i) good randomness
properties of the output sequence, (ii) reproducibility, (iii) speed or eciency and
(iv) large period. The unpredictability of random sequences is established using
a random
seed
that is obtained by a physical source like timings of keystrokes.
