Statistical tests suites analysis methods. Cryptographic recommendations

Abstract

In many applications, it is necessary to work with long sequences of random numbers, or at least those that behave as such (pseudo-random numbers). For this purpose, it is essential to verify the goodness of the sequences under study, e.g., to verify whether the sequences meet the properties of randomness, uniformity, and, in the case of cryptographic applications, unpredictability. To verify these properties, hypothesis tests are used, which are usually grouped into sets of tests known as batteries or suites. The design of these suites is a task of vital importance, and some rules must be followed. On the one hand, the coverage of a suite must be broad; it must check the properties of the sequences from different points of view. On the other hand, a suite with a very large number of tests is not uncommonly expensive in terms of execution time and computational performance. However, this consideration is ignored in most of the test suites in use. There are approximately 50 randomization tests in the literature, and each test suite collects many of them without performing any further analysis on the suite construction. It is important to perform an analysis of the possible relationships between the tests that constitute a suite to eliminate, if necessary, those tests that are redundant and that would slow down the performance of the suite. This paper reviews all of the methods that have been used in the literature to analyze statistical test suites and establishes recommendations for their use in cryptography.

Keywords:

• hypothesis test
• pseudo-random number
• random numbers
• (statistical) test suite

Acknowledgements

I would like to thank the reviewers for their valuable advice on how to improve this paper.

Disclosure statement

The author reports there are no competing interests to declare.

Notes

1 Coverage can be defined as the sequences that fail any of the tests in the suite for a pre-specified type I error (Turan, Doğanaksoy, and Boztas 2008).

2 Let $X=(X_1,\dots ,X_n)$ be a n-dimensional continuous random vector with (joint) density function $f_X(x_1,\dots ,x_n).$ Let us suppose that (a) the equalities $u_k=g_k(x_1,\dots ,x_n),\hspace{0.17em}k=1,\dots ,n,$ define a one-to-one mapping of ${\mathbb{R}}^n$ to ${\mathbb{R}}^n,$ i.e. there is the reverse mapping $x_k=h_k(u_1,\dots ,u_n),\hspace{0.17em}k=1,\dots ,n$ and it is defined over the range of the transformation. (b) The direct and inverse transformations are continuous. (c) Partial derivatives $\frac{\partial x_i}{\partial u_j}$ for all $1\le i,j\le n,$ exist and are continuous. (d) The Jacobian J of the inverse transformation is non-zero for any point $(u_1,\dots ,u_n)$ in the range of the transformation. Then the random vector $U=(U_1,\dots ,U_n)$ has an absolute continuous distribution and its density function is: $f_U(u_1,\dots ,u_n)=f_X(h_1(u_1,\dots ,u_n),\dots ,h_n(u_1,\dots ,u_n))\left|J\right|$

3 See Definition 4.1.

Additional information

Notes on contributors

Elena Almaraz Luengo

Elena Almaraz Luengo received a Mathematics degree from the University Complutense of Madrid in 2005, a Statistical Sciences and Techniques degree from the University Complutense of Madrid in 2007, and a Business and Administration degree from the National Distance Education University in 2015. She earned Doctorate in Mathematics from the University Complutense of Madrid in 2009 and a Master’s Degree in Advanced Mathematics with a specialization in Statistics and Operations Research, from the National Distance Education University in 2010. She is currently an Assistant Professor in the Department of Statistics and Operational Research in the Faculty of Mathematical Science, Universidad Complutense de Madrid (UCM), Spain. Her main interests are Statistical Techniques, Probability, Information Security, and Applications.