Paper 2016/863

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

Shuangyi Zhu, Yuan Ma, Jingqiang Lin, 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.

Metadata
Available format(s)
PDF
Publication info
Published by the IACR in ASIACRYPT 2016
Keywords
Statistical randomness testNIST SP800-22random number generatorP-value
Contact author(s)
yma @ is ac cn
mayuan05 @ hotmail com
zhushuangyi @ iie ac cn
linjingqiang @ iie ac cn
History
2016-09-10: received
Short URL
https://ia.cr/2016/863
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2016/863,
      author = {Shuangyi Zhu and Yuan Ma and Jingqiang Lin and Jia Zhuang and Jiwu Jing},
      title = {More Powerful and Reliable Second-level Statistical Randomness Tests for NIST SP 800-22},
      howpublished = {Cryptology ePrint Archive, Paper 2016/863},
      year = {2016},
      note = {\url{https://eprint.iacr.org/2016/863}},
      url = {https://eprint.iacr.org/2016/863}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.