Cryptology ePrint Archive: Report 2016/863

More Powerful and Reliable Second-level Statistical Randomness Tests for NIST SP 800-22

Shuangyi Zhu and Yuan Ma and Jingqiang Lin and Jia Zhuang and Jiwu Jing

Abstract: Random number generators (RNGs) are essential for cryptographic systems, and statistical tests are usually employed to assess the randomness of their outputs. As the most commonly used statistical test suite, the NIST SP 800-22 suite includes 15 test items, each of which contains two-level tests. For the test items based on the binomial distribution, we find that their second-level tests are flawed due to the inconsistency between the assessed distribution and the assumed one. That is, the sequence that passes the test could still have statistical flaws in the assessed aspect. For this reason, we propose Q-value as the metric for these second-level tests to replace the original P-value without any extra modification, and the first-level tests are kept unchanged. We provide the correctness proof of the proposed Q-value based second-level tests. We perform the theoretical analysis to demonstrate that the modification improves not only the detectability, but also the reliability. That is, the tested sequence that dissatisfies the randomness hypothesis has a higher probability to be rejected by the improved test, and the sequence that satisfies the hypothesis has a higher probability to pass it. The experimental results on several deterministic RNGs indicate that, the Q-value based method is able to detect some statistical flaws that the original SP 800-22 suite cannot realize under the same test parameters.

Category / Keywords: Statistical randomness test, NIST SP800-22, random number generator, P-value

Original Publication (in the same form): IACR-ASIACRYPT-2016

Date: received 6 Sep 2016, last revised 10 Sep 2016

Contact author: yma at is ac cn, mayuan05@hotmail com, zhushuangyi@iie ac cn, linjingqiang@iie ac cn

Available format(s): PDF | BibTeX Citation

Version: 20160910:152906 (All versions of this report)

Short URL:

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]