arXiv:2403.18716 · Entropy

Statistical Testing of Random Number Generators and Their Improvement Using Randomness Extraction

Cameron Foreman, Richie Wai Kit Yeung, Florian J. Curchod

Published Dec 4, 2024• 22 citations

Abstract

Random number generators (RNGs) are notoriously challenging to build and test, especially for cryptographic applications. While statistical tests cannot definitively guarantee an RNG's output quality, they are a powerful verification tool and the only universally applicable testing method. In this work, we design, implement, and present various post-processing methods, using randomness extractors, to improve the RNG output quality and compare them through statistical testing. We begin by performing intensive tests on three RNGs-the 32-bit linear feedback shift register (LFSR), Intel's 'RDSEED,' and IDQuantique's 'Quantis'-and compare their performance. Next, we apply the different post-processing methods to each RNG and conduct further intensive testing on the processed output. To facilitate this, we introduce a comprehensive statistical testing environment, based on existing test suites, that can be parametrised for lightweight (fast) to intensive testing.

DOI: 10.3390/e26121053

Related papers

True randomness from realistic quantum devices

Daniela Frauchiger, Renato Renner, Matthias Troyer

Even if the output of a Random Number Generator (RNG) is perfectly uniformly distributed, it may be correlated to pre-existing information and therefore be predictable. Statistical tests are thus not sufficient to guarantee that an RNG is usable for applications, e.g., in cryptography or gambling, where unpredictability is important. To enable such applications a stronger notion of randomness, termed "true randomness", is required, which includes independence from prior information. Quantum systems are particularly suitable for true randomness generation, as their unpredictability can be proved based on physical principles. Practical implementations of Quantum RNGs (QRNGs) are however always subject to noise, i.e., influences which are not fully controlled. This reduces the quality of the raw randomness generated by the device, making it necessary to post-process it. Here we provide a framework to analyse realistic QRNGs and to determine the post-processing that is necessary to turn their raw output into true randomness.

arXiv:1311.4547Nov 18, 201346 citations

Enhancing the operational efficiency of quantum random number generators

Botond L. Márton, Dóra Istenes, László Bacsárdi

Random numbers are of vital importance in today’s world and used for example in many cryptographical protocols to secure the communication over the internet. The generators producing these numbers are Pseudo Random Number Generators (PRNGs) or True Random Number Generators (TRNGs). A subclass of TRNGs are the Quantum based Random Number Generators (QRNGs) whose generation processes are based on quantum phenomena. However, the achievable quality of the numbers generated from a practical implementation can differ from the theoretically possible. To ease this negative effect post-processing can be used, which contains the use of extractors. They extract as much entropy as possible from the original source and produce a new output with better properties. The quality and the different properties of a given output can be measured with the help of statistical tests. In our work we examined the effect of different extractors on two QRNG outputs and found that witg the right extractor we can improve their quality.

Híradástechnika/Infocommunications journalJan 1, 20215 citations

A Novel Hybrid Method for Randomness Extraction

Maksim Iavich, Роман Сергійович Одарченко

Randomness is widely used in various fields, including encryption, statistical analysis, and numerical simulations. Randomness is also a fundamental resource in science and engineering. For such applications, we usually need to provide unbiased and independent random bits. This raises the issue of where to get these supposed random bits. Quantum random number generators (QRNGs) generate real random numbers based on the inherent randomness of quantum measurements. In practice, unfortunately, quantum randomness is inevitably mixed with classical randomness due to classical noise. Also, randomness is often correlated and biased. It is necessary to process the resulting raw bits sequence and convert them to good-quality output values that are as close to uniform distribution as possible. Random extractors are required for this. We analyze the randomness obtained by quantum random number generators as well as various examples of post-processing. We discuss the types of randomness extractors. Also, we use information-theoretically secure extractors and present improved novel randomness extraction.

CRC Press eBooksMay 30, 20250 citations

Analysis of entropy extraction efficiencies in random number generation systems

Chao Wang, Shuang Wang, Wei Chen +2 more

Random numbers (RNs) have applications in many areas: lottery games, gambling, computer simulation, and, most importantly, cryptography [N. Gisin et al., Rev. Mod. Phys. 74 (2002) 145]. In cryptography theory, the theoretical security of the system calls for high quality RNs. Therefore, developing methods for producing unpredictable RNs with adequate speed is an attractive topic. Early on, despite the lack of theoretical support, pseudo RNs generated by algorithmic methods performed well and satisfied reasonable statistical requirements. However, as implemented, those pseudorandom sequences were completely determined by mathematical formulas and initial seeds, which cannot introduce extra entropy or information. In these cases, “random” bits are generated that are not at all random. Physical random number generators (RNGs), which, in contrast to algorithmic methods, are based on unpredictable physical random phenomena, have attracted considerable research interest. However, the way that we extract random bits from those physical entropy sources has a large influence on the efficiency and performance of the system. In this manuscript, we will review and discuss several randomness extraction schemes that are based on radiation or photon arrival times. We analyze the robustness, post-processing requirements and, in particular, the extraction efficiency of those methods to aid in the construction of efficient, compact and robust physical RNG systems.

International Journal of Quantum InformationFeb 1, 20160 citations

Real Time Random Number GeneratorTesting

João Dionísio, Tiago Mota, Iola Pinto +1 more

We present a random number generator (RNG) testing application in LabVIEW®, based on six of the statistical tests from the ubiquitous NIST test suite that is widely used in the field of cryptography. The implementation is described, and tests measuring performance, both regarding precision and speed, are demonstrated. The application can be interfaced to real time true RNGs based on quantum optics experiments.

Procedia TechnologyJan 1, 20143 citations

High-efficiency implementation of Toeplitz Strong Extractor for PRNG and QRNG output on CPU/GPU hardware systems

K S V Anurag, G Raghavan, Kanaka Raju P.

Abstract Random Number Generators (RNGs) are devices whose utility spans from cryptography to gambling. Depending on the source of the random seed, RNGs are classified as Pseudo-Random Number Generators (PRNGs), which are based on mathematical algorithms, True Random Number Generators (TRNGs) sourced through seemingly random physical processes, and finally, Quantum Random Number Generators (QRNGs) which harness the intrinsic randomness of measured outcomes of quantum states. To ensure that the output of a QRNG is private and nearly uniform, the raw data undergoes a strong extraction process such as Toeplitz or Trevisan Hashing. The extraction process needs to be extremely efficient to achieve high-speed random number generation. The present work demonstrates state-of-the-art methods for performing information-theoretically provable randomness extraction using variations of the Toeplitz Hashing algorithm. These algorithms are implemented on various hardware for comprehensive analysis. Subsequently, these methods are applied to two raw data sets from a PRNG source and a quantum source. A new benchmark of 19.5 Gbps for Randomness Extraction using the Fast Fourier Transform-based Toeplitz Strong Extractor is demonstrated in this work. The implementation of the algorithm on a GPU-based system demonstrates notably enhanced speed, marking a significant leap beyond the existing state-of-the-art implementations.

Physica ScriptaJun 14, 20242 citations