Title: Randomness Evaluation with the Discrete Fourier Transform Test Based on Exact Analysis of the Reference Distribution,
Abstract: 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.