Information Technology Reference
In-Depth Information
L
A
=
{
S
n
∈
L
:
T
(
S
n
) = accept
}⊆
L
L
R
=
{
S
n
∈
L
:
T
(
S
n
) = reject
}⊆
L
The size of these two sets is determined by the type I error
α
, i.e.
=
α
.
The most commonly used test is probably the
frequency test
[1] that evaluates
the randomness of a given sequence based on the number of ones (that is, the
weight
w
) of the sequence. A trivial extension of the frequency test can be
given as the
equidistribution test
that focuses on the frequencies of
k
-bit tuples
throughout the sequence.
Overlapping
and
Non-overlapping template matching
tests
[1] only consider the number of occurrences of pre-specified templates in
the sequence.
Another commonly used statistics in randomness testing is about the changes
from 1 to 0 or visa versa, which is called a
run
. Runs test [1] focuses on the
number of runs in the sequence which is expected to be around
(
n
+1)
|
L
R
|
/
|
L
|
2
for a
random sequence of length
n
. Alternatively, there are tests that concentrate on
length of runs, particularly
length of the longest run of ones
[1] in the sequence.
Especially in cryptographic applications, the complexity of sequences -the
ability to reproduce the sequence- is of interest. Sequences with low complexity
measures can be easily generated with alternative machines. Some examples of
randomness tests based on complexity measures can be given as
linear complexity
[1],
Lempel-Ziv
[8] and
maximum order complexity
[9].
Classification of Tests.
While selecting a subset of randomness tests to be
included in a test suite, it is necessary to understand what exactly the test
measures. Tests that focus on similar properties should not be included in the
test suite, but one of such a class should be chosen.
In [10], two important properties of random sequences are emphasized. The
first is about the appearance of the sequence which is related to the
ability of the
attacker to guess the next bit better than random guessing
. The second property
is about the
ability to reproduce the sequence
, i.e., the complexity of the sequence.
Considering these properties, we give a rough classification of randomness tests
into two categories:
Tests based on
k
-tuple pattern frequencies
aim to detect the biases in the
appearance of the sequences. Weaknesses in the appearance of sequences can
be considered as the deviations in the frequencies of
k
-tuples (1
log
2
n
)
which are expected to occur nearly equally many times throughout the sequence.
An example for this category with
k
= 1 is the most commonly used frequency
test. A trivial extension of the frequency test is the equidistribution test with
k
=2
,
3
,...
. Other examples can be given as runs, overlapping template, serial,
coupon collectors, etc.
Tests based on ordering of
k
-tuples
aim to detect weaknesses based on the
reproducibility of sequences. Most of the test statistics in this category are re-
lated to the size of simpler systems that generate the sequence. If the size of
these machines are less than expected, it is possible to use these machines to
≤
k
≤
