Correction of Overlapping Template Matching Test Included in NIST Randomness Test Suite
Abstract
Accurate values for occurrence probabilities of the template used in the overlapping template matching test included in NIST randomness test suite (NIST SP800-22) have been analyzed. The inaccurate values used in the NIST randomness test suite cause significant difference of pass rate. When the inaccurate values are used and significance level is set to 1%, the experimental mean value of pass rate, which is calculated by use of random number sequences taken from DES (Data Encryption Standard), is about 98.8%. In contrast, our new values derived from a set of recurrence formulas for the NIST randomness test suite give an empirical distribution of pass rate that meets the theoretical binomial distribution. Here, the experimental mean value of pass rate is about 99%, which corresponds to the significance level 1%.
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?
NIST now adopts more accurate values derived by [4] for the Overlapping Template Matching test.
“NIST once used the probabilities derived by an approximation formula, and now it adopts more accurate values derived by [4].”
From Checking the quality of approximation of <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" id="mml84" display="inline" overflow="scroll" altimg="si2.gif"><mml:mi>p</mml:mi></mml:math>-values in statistical tests for random number generators by using a three-level test (2019) · cites this paper as [4]
NIST once used probabilities derived by an approximation formula for the Overlapping Template Matching test.
“NIST once used the probabilities derived by an approximation formula, and now it adopts more accurate values derived by [4].”
From Checking the quality of approximation of <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" id="mml84" display="inline" overflow="scroll" altimg="si2.gif"><mml:mi>p</mml:mi></mml:math>-values in statistical tests for random number generators by using a three-level test (2019) · cites this paper as [4]
Cites
The Art of Computer Programming
Knuth, D. E. (1968) · Cited by 16,097 · see citing works
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
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
Self-citation(2003) · Medical Entomology and Zoology · Cited by 22 · see citing works
The problem of template matching test in the testing randomness by NIST
Takeda, Y., Huzii, M., Kamakura, T., et al. (2005) · IEICE Technical Report; IEICE Tech. Rep. · Cited by 3 · see citing works
Flagged first, then by citations
Cited by
Sorted by citations
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
A Heuristic Statistical Testing Based Approach for Encrypted Network Traffic Identification
Niu, W., Zhuo, Z., Zhang, X., Du, X., Yang, G., & Guizani, M. (2019) · IEEE Transactions on Vehicular Technology · doi:10.1109/tvt.2019.2894290 · Cited by 39 · see citing works
“and non-overlapping template matching test [36] require input 0 and 1 sequence to be at least 106 bits long, and Maurer’s universal statistical test [37] requires input size larger than 387840”
BackgroundPseudorandom number generation using chaotic true orbits of the Bernoulli map
Saito, A., & Yamaguchi, A. (2016) · Chaos An Interdisciplinary Journal of Nonlinear Science · doi:10.1063/1.4954023 · Cited by 32 · see citing works
New Statistical Randomness Tests Based on Length of Runs
Doğanaksoy, A., Sulak, F., Uğuz, M., et al. (2015) · Mathematical Problems in Engineering · doi:10.1155/2015/626408 · Cited by 27 · see citing works
“In 2004, it is discovered that test setting of discrete fourier transform test and lempel-ziv test were wrong [12] and new test, which can be used instead of lempel-ziv test, is defined in [13] and correction of overlapping template matching is stated in 2007 [14].”
Sulak, F., Doğanaksoy, A., Uğuz, M., et al. (2019) · Discrete Applied Mathematics · doi:10.1016/j.dam.2019.07.022 · Cited by 24 · see citing works
A General Method to Evaluate the Correlation of Randomness Tests
Fan, L., Chen, H., & Gao, S. J. (2014) · Lecture notes in computer science · doi:10.1007/978-3-319-05149-9_4 · Cited by 21 · see citing works
Statistical Testing of Random Number Generators and Their Improvement Using Randomness Extraction
Foreman, C., Yeung, R. W. K., & Curchod, F. J. (2024) · Entropy · doi:10.3390/e26121053 · Cited by 22 · see citing works
“Research has found significant dependencies between the tests [33] and implementation issues with certain tests; for example, [34] found that the settings of both the Discrete Fourier Transform test and Lempel-Ziv test were wrong, and [35] found an error within the probability calculations for the…”
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
“Among the test items, Kim et al. [6] analyzed the correctness of the Spectral Test and the Lemple-Ziv Test, and Hamano [4, 5] adjusted the distribution parameters for the Spectral Test and corrected the Overlapping Test.”
MethodA Randomness Test Based on T-Complexity
Hamano, K., & Yamamoto, H. (2010) · IEICE Transactions on Fundamentals of Electronics Communications and Computer Sciences · doi:10.1587/transfun.e93.a.1346 · Cited by 17 · see citing works
“The accurate probabilities given in [9] are described in NIST SP 800-22 Revision 1 [26] although they have not yet been implemented in the NIST test suite (the Statistical Test Suite Version 2.”
MethodSelf-citationError Analysis of NIST SP 800-22 Test Suite
Chen, D., Chen, H., Fan, L., & Luo, K. (2023) · IEEE Transactions on Information Forensics and Security · doi:10.1109/tifs.2023.3287391 · Cited by 14 · 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…”
BackgroundMethodФормулы для чисел последовательностей, содержащих заданный шаблон заданное число раз
Серов, А. А. (2020) · Дискретная математика · doi:10.4213/dm1626 · Cited by 11 · see citing works
On the Additional Chi-Square Tests for the IID Assumption of NIST SP 800-90B
Kang, J.-S., Park, H., & Yeom, Y. (2017) · Conference on Privacy, Security and Trust · doi:10.1109/pst.2017.00051 · Cited by 10 · see citing works
“Hamano and Kaneko [10] have shown that the overlapping template matching test included in the NIST SP 800-22 randomness test suite uses the inaccurate occurrence probabilities of the template.”
BackgroundStudy on the Pass Rate of NIST SP800-22 Statistical Test Suite
Li-hua, D., Yong, Z., Ligang, J., et al. (2014) · International Conference on Computational Intelligence and Security (CIS) · doi:10.1109/cis.2014.120 · Cited by 9 · see citing works
A New Randomness Test Based on Linear Complexity Profile
Hamano, K., Sato, F., & Yamamoto, H. (2009) · IEICE Transactions on Fundamentals of Electronics Communications and Computer Sciences · doi:10.1587/transfun.e92.a.166 · Cited by 9 · see citing works
“In the case of the overlapping template matching test, the problem was caused from inaccurate probabilities derived for the occurrence of the template in the NIST test suite [5].”
MethodSelf-citationHaramoto, H., & Matsumoto, M. (2019) · Mathematics and Computers in Simulation · doi:10.1016/j.matcom.2018.08.005 · Cited by 8 · see citing works
“NIST once used the probabilities derived by an approximation formula, and now it adopts more accurate values derived by [4].”
MethodA new discrete Fourier transform randomness test
Chen, M., Chen, H., Fan, L., et al. (2019) · Science China Information Sciences · doi:10.1007/s11432-018-9489-x · Cited by 7 · see citing works
Formulas for the numbers of sequences containing a given pattern given number of times
Серов, А. А. (2022) · Discrete Mathematics and Applications · doi:10.1515/dma-2022-0020 · Cited by 7 · see citing works
New statistical randomness tests: 4-bit template matching tests
SULAK, F. (2017) · TURKISH JOURNAL OF MATHEMATICS · doi:10.3906/mat-1509-19 · Cited by 5 · see citing works
“There are several studies for the tests of the NIST test suite [28], [7], [9], [22], [11].”
BackgroundMethodParallel Implementation of Chaos Neural Networks for an Embedded GPU
Liu, Z., Murakami, T., Kawamura, S., & Yoshida, H. (2019) · International Conference on Awareness Science and Technology (iCAST) · doi:10.1109/icawst.2019.8923383 · Cited by 5 · see citing works
“the NIST test suite should be corrected [12].”
MethodCorrected runs distribution test for pseudorandom number generators
Fan, L., Chen, H., Chen, M., et al. (2016) · Electronics Letters · doi:10.1049/el.2015.3097 · Cited by 4 · see citing works
“Takeda et al. [7] and Hamano and Kameko [8] studied the accuracy of overlapping matching test and non-overlapping matching test.”
Fast Software Implementation of Serial Test and Approximate Entropy Test of Binary Sequence
Yang, X.-W., Zhan, X.-Q., Kang, H., et al. (2021) · Security and Communication Networks · doi:10.1155/2021/1375954 · Cited by 2 · see citing works
An Efficiency Optimization Scheme for the On-the-Fly Statistical Randomness Test
Chen, T., Ma, Y., Lin, J.-Q., Wang, Z., & Jing, J.-W. (2015) · 2015 IEEE 2nd International Conference on Cyber Security and Cloud Computing · doi:10.1109/cscloud.2015.10 · Cited by 1 · see citing works
LS-14 Test Suite for Long Sequences
Akcengi̇z, Z., Aslan, M., Doğanaksoy, A., Sulak, F., & Uğuz, M. (2023) · Hacettepe Journal of Mathematics and Statistics · doi:10.15672/hujms.1190807 · Cited by 2 · see citing works
“In years, after some corrections and improvements for some tests, this test suit were proposed [5,12,23].”
BackgroundOn pseudorandom number generators
Bastos, D. C., Kowada, L. A. B., & Machado, R. C. S. (2020) · ACTA IMEKO · doi:10.21014/acta_imeko.v9i4.730 · Cited by 1 · see citing works
“Enough flaws of this test suite have been previously reported [33]-[37], but we will now present one more result”
BackgroundJaksic, O. M., Jakšić, Z., Guha, K., et al. (2021) · Microsystem Technologies · doi:10.1007/s00542-020-05137-5 · Cited by 1 · see citing works
An Efficiency Optimization Scheme for the On-the-Fly Statistical Randomness Test
Shen, J., Chen, T., Wang, L., & Ma, Y.-X. (2017) · International Conference on Information, Communications and Signal Processing · doi:10.1007/978-3-319-89500-0_2
The reference distributions of Maurer's universal statistical test and its improved testsPreprint
Hikima, Y., Iwasaki, A., & Umeno, K. (2021) · arXiv (Cornell University) · doi:10.48550/arxiv.2103.10660
“Some of the tests were pointed out that are problematic, and improvements have been proposed [6, 7, 8, 9, 10, 11].”
BackgroundThe Reference Distributions of Maurer’s Universal Statistical Test and Its Improved Tests
Hikima, Y., Iwasaki, A., & Umeno, K. (2021) · IEEE Transactions on Information Theory · doi:10.1109/tit.2021.3131691
“Some of the tests were pointed out that are problematic, and improvements have been proposed [6, 7, 8, 9, 10, 11].”
BackgroundOn the Mathematical Aspects of Cryptographic Randomness Tests Using Discrete Fourier Transform
Dinh, L. H., Thi, L. T., & Văn, L. N. (2024) · doi:10.1109/vcris63677.2024.10813437
Условия надежности двухуровневого подхода к тестированию в наборе тестов NIST SP800-22
Серов, А. А. (2025) · Математические вопросы криптографии · doi:10.4213/mvk495
Accelerating True Orbit Pseudorandom Bit Generation Using Newton’s Method
Saito, A., & Yamaguchi, A. (2026) · Springer proceedings in mathematics & statistics · doi:10.1007/978-3-032-10590-5_18
- Authors
- HAMANO, K., & KANEKO, T.
- Affiliations
- The University of Tokyo (JP)
- Venue
- IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences
- Published
- 2007-09-01
- Volume
- E90-A
- Issue
- 9
- Pages
- 1788-1792
- ISSN
- 0916-8508 (ISSN-L)
- 1745-1337
- OpenAlex
- W2025482752
- Semantic Scholar
- de2c87ea01f475eeb113249aa640a25e941275cd
- Cited by
- 32
- References
- 5
- Citations by year
- 2026: 1 · 2025: 1 · 2024: 3 · 2023: 1 · 2022: 1 · 2021: 4 · 2020: 2 · 2019: 4 · 2018: 2 · 2017: 2 · 2016: 3 · 2015: 2 · 2014: 3
- Type
- journal article
- Language
- en
- Open access
- closed
- Locations
- IEICE Transactions on Fundamentals of Electronics Communications and Computer Sciences (publishedVersion)
- 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, pass rates, binomial distribution, recurrence relations, random number generators, significance level
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
