Error Analysis of NIST SP 800-22 Test Suite
Abstract
Statistical tests for randomness play an essential role in cryptography, but the reliability of these tests is rarely taken into account, which may mislead our judgement of randomness especially with extremely large samples. In this paper, we make a two-stage error analysis of the commonly used two-level randomness tests in the NIST SP 800-22 test suite. Especially, we give the estimates of thep-value deviations of chi-square approximation in the basic tests based on our proposed continuity constraints, and mathematically express the reliability of uniformity test used in the test suite with the fact of noncentral chi-square approximation. Finally, we analyze the respective error factors and derive the corresponding probability deviation estimation for the tests, explaining some false positive issues in practical test experiments. With our derived error analysis models, one can get a more reliable randomness test strategy with extremely large samples and wider parameter selections.
Integrity signals
Registry
Cites
Statistics
Claims the paper makes
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
Several studies have examined the NIST test to evaluate its quality and assess statistical errors.
“Several studies have examined the NIST test to evaluate its quality and assess statistical errors, for example, the reader can refer to22–24.”
Cites
Bassham, L. E., Rukhin, A. L., Soto, J., Nechvatal, J. R., Smid, M. E., Barker, E. B., Leigh, S. D., Levenson, M., Vangel, M., Banks, D. L., et al. (2010) · NIST Special Publication 800-22 Revision 1a · doi:10.6028/nist.sp.800-22r1a · Cited by 3,617 · see citing works
Pearson, K. (1900) · Springer series in statistics · doi:10.1007/978-1-4612-4380-9_2 · Cited by 2,991 · see citing works
Generalized Inverse of Matrices and its Applications
Mayne, A. J. (1972) · Journal of the Operational Research Society · doi:10.1057/jors.1972.96 · Cited by 1,213 · see citing works
TestU01: A C library for empirical testing of random number generators
L'Ecuyer, P., & Simard, R. (2007) · ACM Transactions on Mathematical Software · doi:10.1145/1268776.1268777 · Cited by 1,014 · see citing works
Normal Approximation by Stein’s Method
Chen, L. H. Y., Goldstein, L. J., & Shao, Q.-M. (2010) · Probability and its applications · doi:10.1007/978-3-642-15007-4 · Cited by 613 · see citing works
Nonparametric Statistical Inference
Gibbons, J. D., & Chakraborti, S. (2011) · International Encyclopedia of Statistical Science · doi:10.1007/978-3-642-04898-2_420 · Cited by 508 · see citing works
Roscoe, J. T., & Byars, J. A. (1971) · Journal of the American Statistical Association · doi:10.1080/01621459.1971.10482341 · Cited by 233 · see citing works
Pareschi, F., Rovatti, R., & Setti, G. (2012) · IEEE Transactions on Information Forensics and Security · doi:10.1109/tifs.2012.2185227 · Cited by 189 · cited 10× · see citing works
“[4] have calculated an upper bound in the Frequency Test for the error between the approximated p-value and the actual one based on Berry-Esséen theorem, and formulated a mathematical condition for the reliability of a two-level test to obtain the restrictions on the parameters N , k.”
BackgroundMethodResultInfluentialApproximate entropy for testing randomness
Rukhin, A. L. (2000) · Journal of Applied Probability · doi:10.1239/jap/1014842270 · Cited by 64 · see citing works
P Values as Random Variables-Expected P Values
Sackrowitz, H. B., & Samuel‐Cahn, E. (1999) · The American Statistician · doi:10.2307/2686051 · Cited by 57 · see citing works
Corrections of the NIST Statistical Test Suite for Randomness
Kim, S.-J., Umeno, K., & Hasegawa, A. (2004) · arXiv · doi:10.48550/arxiv.nlin/0401040 · Cited by 54 · see citing works
On the independence of statistical randomness tests included in the NIST test suite
Sulak, F., Uğuz, M., KOÇAK, O., et al. (2017) · TURKISH JOURNAL OF ELECTRICAL ENGINEERING & COMPUTER SCIENCES · doi:10.3906/elk-1605-212 · Cited by 51 · see citing works
An Accurate Evaluation of Maurer’s Universal Test
Coron, J. S., & Naccache, D. (1999) · Lecture Notes in Computer Science · doi:10.1007/3-540-48892-8_5 · Cited by 47 · see citing works
Second-level NIST Randomness Tests for Improving Test Reliability
Pareschi, F., Rovatti, R., & Setti, G. (2007) · 2007 IEEE International Symposium on Circuits and Systems (ISCAS) · doi:10.1109/iscas.2007.378572 · Cited by 45 · see citing works
The Distribution of the Spectrum for the Discrete Fourier Transform Test Included in SP800-22
HAMANO, K. (2005) · IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences · doi:10.1093/ietfec/e88-a.1.67 · Cited by 34 · see citing works
Correction of Overlapping Template Matching Test Included in NIST Randomness Test Suite
HAMANO, K., & KANEKO, T. (2007) · IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences · doi:10.1093/ietfec/e90-a.9.1788 · Cited by 32 · cited 3× · see citing works
“In order to get more accurate values of the test statistics, Kim et al. [8], Hamado and Kaneko [10], and Coron and Naccache [17] calculated more accurate estimates of the parameters in different tests respectively through mathematical derivation, which is of great help to improve the accuracy and…”
BackgroundMethodNew estimates of the convergence rate in the Lyapunov theoremPreprint
Tyurin, I. S. (2009) · arXiv (Cornell University) · doi:10.48550/arxiv.0912.0726 · Cited by 28 · see citing works
Deriving the Variance of the Discrete Fourier Transform Test Using Parseval’s Theorem
Iwasaki, A. (2019) · IEEE Transactions on Information Theory · doi:10.1109/tit.2019.2947045 · Cited by 27 · see citing works
Okada, H., & Umeno, K. (2017) · IEEE Transactions on Information Forensics and Security · doi:10.1109/tifs.2017.2656473 · Cited by 25 · see citing works
A Power Approximation for the Chi-Square Goodness-of-Fit Test: Simple Hypothesis Case
Broffitt, J. D., & Randles, R. H. (1977) · Journal of the American Statistical Association · doi:10.1080/01621459.1977.10480623 · Cited by 22 · see citing works
More Powerful and Reliable Second-Level Statistical Randomness Tests for NIST SP 800-22
Zhu, S., Ma, Y., Lin, J., et al. (2016) · Lecture notes in computer science · doi:10.1007/978-3-662-53887-6_11 · Cited by 20 · see citing works
Randomness Test to Solve Discrete Fourier Transform Test Problems
Iwasaki, A., & Umeno, K. (2018) · IEICE Transactions on Fundamentals of Electronics Communications and Computer Sciences · doi:10.1587/transfun.e101.a.1204 · Cited by 17 · see citing works
Flagged first, then by citations
Cited by
Sorted by citations
Salehi, R., Malik, A. W., Novotny, M. A., & Khan, S. U. (2026) · Scientific Reports · doi:10.1038/s41598-026-51033-9
- Authors
- Chen, D., Chen, H., Fan, L., & Luo, K.
- Affiliations
- Chinese Academy of Sciences (CN)
- Venue
- IEEE Transactions on Information Forensics and Security
- Published
- 2023
- Volume
- 18
- Pages
- 3745-3759
- ISSN
- 1556-6013 (ISSN-L)
- 1556-6021
- OpenAlex
- W4381198926
- Semantic Scholar
- efa81b7bd8ed07f2449b227946f63946a6d5e0a1
- Cited by
- 14
- References
- 22
- Citations by year
- 2026: 6 · 2025: 3 · 2024: 3 · 2023: 2
- FWCI
- 1.24
- Type
- journal article
- Language
- en
- Open access
- closed
- Licence
- Locations
- IEEE Transactions on Information Forensics and Security (publishedVersion)
- Funders
- National Key Research and Development Program of China (2020YFA0309704)
- Topics
- Physical Sciences › Computer Science › Artificial Intelligence › Cryptographic Implementations and Security
- Physical Sciences › Mathematics › Statistics and Probability › Probability and Statistical Research
- Physical Sciences › Computer Science › Artificial Intelligence › Coding theory and cryptography
- Keywords
- NIST SP 800-22, randomness testing, hypothesis testing, chi-square approximation, continuity correction, noncentral chi-square distribution, uniformity testing, false positives, large sample size, cryptographic randomness
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
