Pith. sign in

REVIEW 3 major objections 5 minor 16 references

Independent Randomness Tests based on the Orthogonalized Non-overlapping Template Matching Test

T0 review · 3 major / 5 minor · reviewed 2026-08-14 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read This paper claims that a linear transformation of the standardized template counts, $C'_j = (LQ)^{-1}C_j$, renders the Non-overlapping Template Matching Test items independent under the null hypothesis.

desk verdict Useful analytic dependence structure for NIST template tests with a sound whitening idea, but the paper overstates exact independence and needs a few corrections before I'd fully trust it. read the letter →

arxiv 1908.07145 v1 pith:VA3LW3QP submitted 2019-08-20 math.ST stat.TH

Atsushi Iwasaki This is my paper · ORCID
classification math.STstat.TH MSC 62F0362H2062E1560F05
keywords randomnesstestsNISTSP800-22non-overlappingtemplatematchingp-valueindependenceorthogonalizationmultivariatenormalapproximationchi-squaretestcorrelationcoefficient
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper targets a known flaw in the NIST SP800-22 randomness test suite: the 148 test items based on the Non-overlapping Template Matching Test are not independent, so no single significance level applies to the suite as a whole. It derives the joint distribution of two such test items' p-values from the multivariate normal approximation of the per-block template counts, and then proposes an orthogonalizing transformation that produces independent test items. After removing three templates whose counts are deterministically tied, the remaining 145 items are claimed to behave as independent tests. The experimental section, using one million $10^{6}$-bit sequences from two different generators, reports that the number of rejecting items per sequence matches the independence expectation. If the claim holds, randomness test users can fix a rational suite-wide criterion with an explicit significance level.

What carries the argument

The machinery is the orthogonalization of the multivariate normal vector $C_j$. After computing the $R\times R$ covariance matrix $\Sigma$ from the pairwise correlation formula (Eq. (31)), the paper chooses an orthogonal matrix $L$ and a diagonal scaling $Q$ so that $Q^\top L^\top \Sigma^{-1} LQ = I$, and transforms $C_j$ to $C'_j = (LQ)^{-1}C_j$; the proof is that the density of $C'_j$ becomes a product of standard normals. The distributional identity underlying the two-test-item dependency analysis is Eq. (35), the joint CDF $F_{N,\rho}(X_N,Y_N)$, an infinite series in $\rho^{2r}$ involving incomplete gamma functions, obtained by inverting the characteristic function of the correlated chi-square pair.

What would settle it

Generate a large null sample with block length $M$ no larger than, say, $2^m$ for $m=9$, apply the orthogonalizing transform (Eq. (40)), and test the empirical covariance of the transformed per-block vectors or the joint distribution of the transformed p-values against the i.i.d. uniform prediction; any systematic off-diagonal correlation or nonuniformity at that $M$ would show that the infinite-$M$ normality and remainder-neglect assumptions are doing real work.

Watch

Extended reading notes

Core claim

The central discovery is that the dependency among Non-overlapping Template Matching Test items can be removed by a linear change of variables. For large block length $M$, the standardized per-block count vectors $C_j$ are treated as jointly normal with a covariance matrix $\Sigma$ whose off-diagonal entries are the pairwise correlations $\rho(T^{(k)}, T^{(\ell)})$ given by Eq. (31). Writing $\Sigma^{-1} = L\Lambda L^\top$ and rescaling by $Q$, the map $C'_j = (LQ)^{-1}C_j$ has identity covariance, so the components of $C'_j$ are standard normal and independent; hence the chi-square statistics built from each component are independent test items. The paper also derives the explicit joint cumulative distribution of two chi-square statistics (Eq. (35)) and of the two p-values, verified by comparing experimental and theoretical two-dimensional p-value distributions. Removing templates that create zero eigenvalues, the author reports that the number of test items rejecting a sequence follows the independent-items expectation for 145 templates.

Load-bearing premise

The whole construction rests on treating the per-block template counts, after standardizing them, as jointly normal already at the block sizes used in practice, and on ignoring the finite-block-size remainder in the correlation formula.

Editorial extensions

If this is right

  • Under the independence claim, the number of the 145 template-based items that reject a sequence at level $\alpha$ is binomially distributed, so a suite-wide pass/fail rule can be set with known Type I error.
  • The explicit two-p-value joint CDF (Eq. (35)) lets a user assess or correct for dependence between any pair of templates without running the full orthogonalization.
  • A single combined p-value for the Non-overlapping Template Matching Test family can be obtained, e.g., by Fisher's method, since the transformed items are independent under the null.
  • The construction explains which templates must be excluded (e.g., 100000000 and 000000001) to avoid singular covariance, turning a numerical necessity into a principled test-set reduction.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • At finite block length $M$ the neglected remainder $O(m^2/(2^m M))$ in Eq. (31) means the orthogonalized items are only asymptotically independent; a practical guide would need to state how large $M$ must be for the approximation to hold.
  • The same recipe might extend to other parametric NIST tests whose block statistics are approximately normal, potentially turning the whole SP800-22 suite into independent items, but the paper does not demonstrate this.
  • Independence under the null does not by itself say how the transformed items behave under a biased generator; power against alternatives is a separate question the paper does not address.
  • The derived joint CDF (35) could be used as a standalone copula to calibrate pairs of dependent p-values, which may be useful when only a small subset of templates is relevant.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 5 minor

Summary. The paper studies the Non-overlapping Template Matching Test of NIST SP800-22 and addresses the fact that the 148 test items based on different 9-bit templates are not independent. It derives the joint distribution of two p-values under the null by modeling each block's standardized count as a bivariate normal variable, and it obtains an explicit joint cumulative distribution function in Eq. (35). The paper then proposes an orthogonalization transformation C'_j = (LQ)^{-1} C_j in Eq. (40), where L and Q diagonalize the covariance matrix built from the pairwise correlation coefficients in Eq. (31), and claims that the transformed test items are independent. The claim is supported by experiments using the Mersenne twister and AES-128.

Significance. The problem is practically important: using multiple template-matching tests with a joint significance level requires understanding and removing the dependence among test items. The paper's main contributions are a closed-form pairwise correlation coefficient, a detailed derivation of the joint CDF of two p-values, and a whitening procedure for the 148 test items. A notable strength is that the correlation coefficients are computed from the analytic formula rather than fitted, and the experimental validation uses two independent generators. If the asymptotic gaps are closed, the orthogonalization method could be useful for defining an explicit overall criterion in NIST SP800-22. However, the central claim that the transformed test items are 'independent of each other' is stronger than what is actually established, because the underlying multivariate normality and the covariance matrix are only asymptotic approximations.

major comments (3)
  1. [Eqs. (19), (28), and (31)] The count of ordered pairs (k,l) in {1,...,M-m+1}^2 with |k-l| >= m is (M-2m+1)(M-2m+2), not (M-m+1)(M-3m+2) as written in Eqs. (19) and (28). The difference is m(m-1), which after division by 2^{2m} is O(m^2/2^{2m}) and therefore does not change the leading-order correlation coefficient. However, the remainder statement in Eq. (31) is not correct as stated. If one retains the exact factor M-m+1 in the near-diagonal sum, the finite-M correction to rho is of order 1/M with a coefficient depending on the template overlap indicators; if one instead replaces every M-m+1 by M before forming the ratio, the residual is O(m/M). In either case the bound O(m^2/(2^m M)) given in Eq. (31) is too small. The paper should replace this with a correct bound and explicitly state that the rho values used to build the covariance matrix are asymptotic quantities.
  2. [Section 3.1 and Section 4.1] The multidimensional extension of Theorem 2.1 is asserted without proof, and exact multivariate normality is impossible for the bounded, discrete block counts. Consequently, Eq. (43) and the statement that the components of C'_j 'follow the standard normal distribution independent of each other' hold only asymptotically. The paper should either supply a rigorous multivariate CLT argument, for example via Cramér-Wold applied to the m-dependent sequence of indicators, or cite an appropriate theorem. It should also state consistently that the independence after the transformation is asymptotic. In addition, Section 4.2 should report a direct residual-dependence check, such as the maximum absolute empirical correlation among the transformed test items over the 10^6 sequences, rather than relying solely on the rejection-count histogram in Figure 3.
  3. [Section 4.1, template removal] The procedure for removing templates to make the covariance matrix nonsingular is incomplete. The text gives examples of dependent template groups (100000000 and 000000001; 011111111 and 111111110; and the four templates 001010101, 010101011, 101010100, 110101010) but does not prove that removing one element from each of these groups actually leaves a nonsingular 145x145 covariance matrix, nor does it explain how the complete list of dependent templates was obtained. Since the transformation in Eq. (40) requires det(Sigma) != 0, the paper should report the eigenvalues of Sigma before and after the removals, or otherwise verify that the remaining 145-template covariance matrix is invertible.
minor comments (5)
  1. [Eq. (4)] The symbol sigma is defined by Eq. (4) as M(1/2^m - (2m-1)/2^{2m}), which is the variance, not the standard deviation, of c_j. The standardization in Eq. (2) then incorrectly divides by the variance instead of the standard deviation. This notational inconsistency should be fixed, for example by writing sigma^2 in Eq. (4).
  2. [Section 3.2] The agreement between the experimental and theoretical joint distributions in Figures 1 and 2 is assessed only visually. A quantitative discrepancy measure or a formal goodness-of-fit statistic for the two-dimensional histograms would make the validation more convincing.
  3. [Section 4.2 and Figure 3] Figure 3 shows the rejection-count histogram before and after transformation but does not provide confidence bands or a goodness-of-fit test against the expected binomial distribution. Adding these would strengthen the claim that the transformed test items are independent.
  4. [Section 4.1] The text says 'we need to remove either 100000000 or 000000001, and 011111111 or 111111110. Finally, we need to remove 001010101 or 010101011 or 101010100 or 110101010,' but the experiment removes 100000000, 111111110, and 001010101. The relation between the general removal rule and the specific templates excluded in the experiment should be stated explicitly.
  5. [References and typography] Reference [4] contains 'at el.' which should be 'et al.'; the equation display after Eq. (53) in the appendix has a typographical artifact 'd¯Xd¯Y' that should be cleaned up; and the caption of Figure 3 lacks axis labels.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the orthogonalizing transformation is a mathematical consequence of the derived covariance model, not a renamed input or fitted prediction.

full rationale

The paper's central derivation is self-contained and non-circular. The correlation coefficient rho(T^(1),T^(2)) is obtained analytically from the joint expectation of block counts (Eqs. 21-31), not fitted to data. The joint cumulative distribution FN,rho in Eq. (35) is derived from first principles in the appendix using characteristic functions and Jordan's lemma. The proposed transformation C'_j = (LQ)^{-1} C_j in Eq. (40) is a standard whitening operation: given the assumed multivariate normal model with covariance Sigma whose off-diagonal entries are the analytically derived rho values, the change of variables in Eqs. (41)-(43) shows that the transformed components are standard normal and independent. This is a derivation, not a prediction that reduces to a fitted parameter; the 'independence' is a mathematical consequence of the model assumptions stated. The experimental section validates the model using independent generators (Mersenne twister and AES-128) and compares rejection counts against the expected binomial-type behavior, so it is an external check rather than a restatement of inputs. The paper does contain a self-citation (reference [13], by the same author) in the literature review of prior dependency studies, but this citation is not load-bearing for the new derivation. The unproved multidimensional extension of Theorem 2.1 and the ignored O(m/M) remainder in Eq. (31) are legitimate mathematical/asymptotic concerns about the strength of the assumptions, but they are not circularity: the paper does not assume the conclusion it claims to establish. Overall, no step in the derivation chain reduces by construction to its own inputs.

Assumptions & free parameters 0 free parameters · 5 assumptions · 0 invented entities

No free parameters are fitted: the covariance matrix is built from the analytic formula (31). The derivation leans on standard CLTs, the unproved multivariate CLT extension, the neglect of finite-M boundary terms, the even-N assumption, and the claimed non-singularity of the reduced covariance matrix, which is not demonstrated.

assumptions (5)
  • standard math Central limit theorem for stationary m-dependent sequences (Hoeffding's theorem)
    Used in Section 2.2 to establish that per-block template counts are approximately normal.
  • domain assumption Multivariate extension of the CLT for m-dependent sequences
    Invoked in Section 3.1 to claim joint normality of the two template counts; a standard result but asserted without proof in the paper.
  • domain assumption Block length M is large enough that O(m/M) boundary corrections in the correlation coefficients can be ignored
    Used when evaluating Eq. (31) and building the covariance matrix; for M=125000 and m=9 the error is about 7e-5, which is small but larger than the stated O(m^2/(2^m M)).
  • domain assumption The number of blocks N is even, as in the NIST default N=8
    Required for the contour derivation in the appendix that assumes N/2 integrality.
  • domain assumption The set of 148 NIST templates and the three removals produce a non-singular covariance matrix for the remaining 145 items
    The removals are asserted from eigenvector checks that are not shown; the reader cannot verify non-singularity from the paper alone.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Independent Randomness Tests based on the Orthogonalized Non-overlapping Template Matching Test." pith.science (2026). https://pith.science/paper/VA3LW3QP

@misc{pith2026190807145,
  author       = {Pith},
  title        = {Pith review of: Independent Randomness Tests based on the Orthogonalized Non-overlapping Template Matching Test},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/VA3LW3QP}},
  note         = {Machine review of arXiv:1908.07145}
}
read the original abstract

In general, randomness tests included in a test suite are not independent of each other. This renders it difficult to fix a rational criterion through the whole test suite with an explicit significance level. In this paper, we focus on the Non-overlapping Template Matching Test, which is a randomness test included in the NIST statistical test suite. The test uses a parameter called "template" and we can consider a test item for each template. We investigate dependency between two test items by deriving the joint probability density function of the two p-values and propose a transformation to make multi test items independent of each other.

Figures

Figures reproduced from arXiv: 1908.07145 by the authors.

Figure 1
Figure 1. Joint distribution of p-values with templates 001010101 and 010101011 [PITH_FULL_IMAGE:figures/full_fig_p007_1.png] view at source ↗
Figure 2
Figure 2. Joint distribution of p-values with templates 001010101 and 101010100 [PITH_FULL_IMAGE:figures/full_fig_p007_2.png] view at source ↗
Figure 3
Figure 3. Number of rejected sequences before and after the transformation [PITH_FULL_IMAGE:figures/full_fig_p009_3.png] view at source ↗
Figures from the paper (1 more)
Figure 4
Figure 4. Figure 4: Integral path CR pN,ρ(XN , YN ) = XN N 2 −1 2 N 2 +1πΓ N 2  Z ∞ −∞ exp  − 1−2it 2(1−2it(1−ρ 2))XN  e −itYN (1 − 2it(1 − ρ 2)) N 2 dt (75) = XN N 2 −1 e − XN 2(1−ρ2) (−i) N 2 2N+1πΓ N 2  (1 − ρ 2) N 2 Z ∞ −∞ exp iρ2 4(1−ρ 2) 2 n t+ i 2(1−ρ2) oXN ! e −itYN n t + i 2(…

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

16 extracted references · 16 canonical work pages

  1. [1]

    Quantum Random Numbers generated by the Cloud Superconducting Quantum Computer

    K. Tamura and Y. Shikano, “Quantum Random Numbers generated by the Cloud Super- conducting Quantum Computer,” arXiv:1906.04410 (2019)

    work page Pith review arXiv 2019

  2. [2]

    DIEHARD: a battery of tests of randomness,

    G. Marsaglia, “DIEHARD: a battery of tests of randomness,” http://stat. fsu. edu/geo (1996)

    work page 1996

  3. [3]

    TestU01: AC library for empirical testing of random number generators,

    P. L’Ecuyer and R. Simard, “TestU01: AC library for empirical testing of random number generators,” ACM Trans. on Mathematical Software 33.4 (2007): 22

    work page 2007

  4. [4]

    A Statistical Test Suite for Random and Pseudorandom Number Gen- erators for Cryptographic Applications,

    A. Rukhin, at el., “ A Statistical Test Suite for Random and Pseudorandom Number Gen- erators for Cryptographic Applications,” National Institute of Standards and Technology Special Publication 800-22 revision 1a (2010)

    work page 2010

  5. [5]

    Orthogonal test series for pseudorandomness test,

    H. Sugita, “Orthogonal test series for pseudorandomness test,” RIMS Kˆ okyˆ uroku 1127 (2000): 80-87 (in Japanese)

    work page 2000

  6. [6]

    Empirical evidence concerning AES,

    P. Hellekalek and S. Wegenkittl, “Empirical evidence concerning AES,” ACM Trans. on Modeling and Computer Simulation 13.4 (2003): 322-333

    work page 2003

  7. [7]

    On independence and sensitivity of statis- tical randomness tests,

    M. S. Turan, A. Do ˇGanaksoy and S. Bozta., “On independence and sensitivity of statis- tical randomness tests,” International Conference on Sequences and Their Applications. Springer, Berlin, Heidelberg, 2008

    work page 2008

  8. [8]

    Extended results for independence and sensitivity of NIST randomness tests,

    A. Do ˇGanaksoy, B. Ege and K. Mus, “Extended results for independence and sensitivity of NIST randomness tests,” Information Security and Cryptography Conference, ISC Turkey, 2008

    work page 2008

Show all 16 references
  1. [9]

    A General Method to Evaluate the Correlation of Randomness Tests,

    L. Fan, H. Chen and S. Gao, “A General Method to Evaluate the Correlation of Randomness Tests,” in: Information Security Applications, WISA 2013, Lecture Notes in Computer Science, vol 8267. Springer, Cham (2014)

    2014

  2. [10]

    Analysis of NIST Randomness test for correlative sequences generated by chaotic true orbit,

    A. Yamaguchi and A. Saito, “Analysis of NIST Randomness test for correlative sequences generated by chaotic true orbit,” proceeding of JSIAM 2016, 2016 (in Japanese)

    2016

  3. [11]

    On the independence of statistical randomness tests included in the NIST test suite,

    F. Sulak, et al,. “On the independence of statistical randomness tests included in the NIST test suite,” Turkish Journal of Electrical Engineering & Computer Sciences 25.5 (2017): 3673-3683

    2017

  4. [12]

    Mutual correlation of NIST statistical randomness tests and com- parison of their sensitivities on transformed sequences,

    A. Do ˇGanaksoy, et al., “Mutual correlation of NIST statistical randomness tests and com- parison of their sensitivities on transformed sequences,” Turkish Journal of Electrical En- gineering & Computer Sciences 25.2 (2017): 655-665. 10

    2017

  5. [13]

    Analysis of NIST SP800-22 focusing on randomness of each sequence,

    A. Iwasaki, “Analysis of NIST SP800-22 focusing on randomness of each sequence,” JSIAM Letters 10 (2018): 1-4

    2018

  6. [14]

    The central limit theorem for dependent random variables,

    W. Hoeffding and R. Herbert, “The central limit theorem for dependent random variables,” Duke Mathematical Journal 15.3 (1948): 773-780

    1948

  7. [15]

    Mersenne twister: a 623-dimensionally equidistributed uniform pseudo-random number generator,

    M. Matsumoto and T. Nishimura, “Mersenne twister: a 623-dimensionally equidistributed uniform pseudo-random number generator,” ACM Trans. on Modeling and Computer Sim- ulation 8.1 (1998): 3-30

    1998

  8. [16]

    Advanced encryption standard,

    V. Rijmen and J. Daemen, “Advanced encryption standard,” Proceedings of Federal Infor- mation Processing Standards Publications, National Institute of Standards and Technology (2001): 19-22. Appendix Derivation of (35) We present the derivation of (35). Assume that random vari...

    2001

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.