Correction Of Overlapping Template Matching Test Included In Nist Randomness Test Suite

摘要

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%.