Information Technology Reference
In-Depth Information
Without the seed, the attacker must not be able to make any predictions about
the output bits, even when all details of the generator is known.
A theoretical proof for the randomness of a generator is impossible to give,
therefore statistical inference based on observed sample sequences produced by
the generator seems to be the best option. Considering the properties of binary
random sequences, various statistical tests can be designed to evaluate the as-
sertion that the sequence is generated by a perfectly random source. Test suites
[1,2,3,4,5] define a collection of tests to evaluate randomness of generators ex-
tensively.
One important attribute of test suites is the variety or coverage of tests that
they include. Coverage can be defined as the sequences that fail any of the tests
in the suite for a pre-specified type I error. A generator may behave randomly
based on a number of tests, and fail when it is evaluated by another test. So,
to have more confidence in the randomness of generators, coverage of test suite
should be as high as possible.
Test suites produce many
p
-values while evaluating a random number gen-
erator. Interpretation of these
p
-values is sometimes complicated and requires
careful attention. According to the NIST test suite, these
p
-values are evaluated
based on (i) their uniformity and (ii) the proportion of
p
-values that are less than
a predefined threshold value which is typically 0.01 [1]. As Soto stated in [6] to
achieve reliable results, the statistical tests in a suite should be independent, in
other words the results of the tests should be uncorrelated. In [7], the relation
between
approximate entropy, overlapping serial and universal test
is analyzed
and highly correlated results are obtained using defective sources.
There is a strong relation between the coverage of the suite and indepen-
dence of tests. In this paper, we study the independence of some commonly used
randomness tests and present some theoretical and experimental results. More-
over, we define the concept of sensitivity, the effect of some transformations to
sequences on test results. We propose to add the composition of the transfor-
mation and the test to the suite, whenever the effect of the transformation is
significant.
The organization of the paper is as follows. In the next section, basic back-
ground information about randomness tests and test suites are presented. In
Sect. 3, theoretical and experimental results on the independence of randomness
tests are presented for a subset of tests. In Sect. 4, the concept of sensitivity
is defined and effects of some basic transformations are presented. In the last
section, we give some concluding remarks and possible future work directions.
2 Randomness Tests
=2
n
.Astatisticaltest
T
is a deterministic algorithm that takes a sample sequence and produces a
decision regarding the randomness of a sequence, as
T
:
L
Let
L
be the set of
n
bit binary sequences, trivially
|
L
|
.
Therefore,
T
divides the set
L
of binary sequences
S
n
=(
s
1
,s
2
,...,s
n
)oflength
n
into two sets;
→{
accept
,
reject
}
