Randomness Tests for Binary Sequences

Cryptography is vital in securing sensitive information and maintaining privacy in the today’s digital world. Though sometimes underestimated, randomness plays a key role in cryptography, generating unpredictable keys and other related material. Hence, high-quality random number generators are a crucial element in building a secure cryptographic system. In dealing with randomness, two key capabilities are essential. First, creating strong random generators, that is, systems able to produce unpredictable and statistically independent numbers. Second, constructing validation systems to verify the quality of the generators. In this dissertation, we focus on the second capability, specifically analyzing the concept of hypothesis test, a statistical inference model representing a basic tool for the statistical characterization of random processes. In the hypothesis testing framework, a central idea is the p-value, a numerical measure assigned to each sample generated from the random process under analysis, allowing to assess the plausibility of a hypothesis, usually referred to as the null hypothesis, about the random process on the basis of the observed data. P-values are determined by the probability distribution associated with the null hypothesis. In the context of random number generators, this distribution is inherently discrete but in the literature it is commonly approximated by continuous distributions for ease of handling. However, analyzing in detail the discrete setting, we show that the mentioned approximation can lead to errors. As an example, we thoroughly examine the testing strategy for random number generators proposed by the National Institute of Standards and Technology (NIST) and demonstrate some inaccuracies in the suggested approach. Motivated by this finding, we define a new simple hypothesis test as a use case to propose and validate a methodology for assessing the definition and implementation correctness of hypothesis tests. Additionally, we present an abstract analysis of the hypothesis test model, which proves valuable in providing a more accurate conceptual framework within the discrete setting. We believe that the results presented in this dissertation can contribute to a better understanding of how hypothesis tests operate in discrete cases, such as analyzing random number generators. In the demanding field of cryptography, even slight discrepancies between the expected and actual behavior of random generators can, in fact, have significant implications for data security.