Randomness Evaluation with the Discrete Fourier Transform Test Based on Exact Analysis of the Reference Distribution
This work addresses a critical issue in cryptographic randomness evaluation, making it more reliable for security applications, though it is incremental as it improves an existing test rather than introducing a new paradigm.
The authors tackled the problem of the DFT test in NIST SP 800-22 having a numerically estimated reference distribution, which they argue makes it unreliable for evaluating randomness in cryptographic applications; they proved that a power spectrum follows a chi-squared distribution and proposed a new test that is more reliable and sensitive, as shown in tests on non-random sequences and PRNGs.
In this paper, we study the problems in the discrete Fourier transform (DFT) test included in NIST SP 800-22 released by the National Institute of Standards and Technology (NIST), which is a collection of tests for evaluating both physical and pseudo-random number generators for cryptographic applications. The most crucial problem in the DFT test is that its reference distribution of the test statistic is not derived mathematically but rather numerically estimated, the DFT test for randomness is based on a pseudo-random number generator (PRNG). Therefore, the present DFT test should not be used unless the reference distribution is mathematically derived. Here, we prove that a power spectrum, which is a component of the test statistic, follows a chi-squared distribution with 2 degrees of freedom. Based on this fact, we propose a test whose reference distribution of the test statistic is mathematically derived. Furthermore, the results of testing non-random sequences and several PRNGs showed that the proposed test is more reliable and definitely more sensitive than the present DFT test.