Interpretation of (NIST) Non Overlapping Template Matching Test

Regarding the Non-Overlapping Template test, this test normally gives us a bunch of p-values (148 values). I would like to ask that how do we interpret those values into a single p-value for presenting in an academic report. I have seen many papers illustrate as only a single p-value. For example,

Cao et.al, Phys.Rev X 6, 2016

In this work the p-value of Non-Overlapping Template test is shown as a single value. I have tried using fisher method to combine all of the p-values but by it's characteristic, the p-value after a combination drops exponentially. Is there any simple way to interpret ?

• I believe the author means "the $P$ values of each and every test is greater than $0.01$". Or in other words, combine them all by taking the minimum. – rikhavshah Dec 2 '18 at 8:18
• @rikhavshah In 148 Template tests, you might expect 1 or 2 failures (p << 0.01). And often there are outliers within the tails of the distribution. The whole test would then fail if you simply threshold passes > 0.01. This is a stochastic test, so stochastic methods have to be used. – Paul Uszak Dec 4 '18 at 12:50

First, Fisher's method is a way to combine several independent statistical tests with known distributions under the null hypothesis into a single statistical test with a known distribution under the null hypothesis. If you would have raised an alarm for certain outcomes of the individual statistical tests with a known false alarm rate, then you can use the same criteria to raise an alarm for the composite test with a known false alarm rate.

• Another way to look at this is: Fisher's method is a way to combine several independent d20 rolls into a single d20 roll, so that if you're given a black box that prints d20 outcomes, you can't tell whether a gremlin inside is doing several statistical tests and applying Fisher's method to them and rounding the result, or just rolling a d20.

If you would have raised an alarm when one of the statistical d20 tests rolled a 1 for the standard false alarm rate of 0.05, then you can raise an alarm when the Fisher composite statistical d20 rolls a 1 for the standard false alarm rate of 0.05.

• Another way to look at this is:

1. With one statistical test, you lay out the possible test outcomes ($$p$$-values) uniformly on a line segment from $$[0,1]$$ and raise an alarm for any data that gives a $$p$$-value in $$[0, 0.05]$$.
2. With two statistical tests, you have a grid of outcomes on the unit square $$[0,1] \times [0,1]$$. On what subspace of the unit square do you raise an alarm?

Fisher's method is a particular choice of which subspace of the unit square raises alarms. There's some good illustrations of this—and comparisons to an alternative method of combining $$p$$-values—in the answers to a question about Fisher's method on stats.se.

There are other methods too for combining a collection of $$n$$ values $$\{p_i\}_{i=1}^n$$ into a single test statistic with a known distribution:

1. The arithmetic mean $$\sum_i p_i/n$$, as discussed in the stats.se answers, and known as Edgington's method.
2. The root-mean-square, $$\sqrt{\sum_i p_i^2/n}$$.
3. The geometric mean $$\prod_i {p_i}^{1/n}$$, which turns out to be tantamount to Fisher's method—just take the log.
4. Pearson's complementary geometric mean, $$1 - \prod_i (1 - p_i)^{1/n}$$.
5. The minimum $$\min_i p_i$$.
6. $$p_1$$, ignoring $$p_2, p_3, \dots, p_n$$ altogether.

Why should you prefer one of these over the others? They all give rise to statistical tests that have any prescribed false alarm rate you want, so they must all be good, right? Well, there's an elephant in the room.

Why raise an alarm when you roll a 1, rather than, say, a 7, on your d20—i.e., why do we care about $$p < 0.05$$? What's really interesting is the alternative hypotheses. The null hypothesis is that the device is working correctly as intended (and perhaps that working correctly means a perfect uniform distribution). But the test is valuable insofar as it raises alarms at a substantially higher rate for plausible deviations from the null hypothesis—for instance, a significantly higher number of one bits than zero bits, which can happen in samples under the null hypothesis but only with low probability. What plausible deviations might there be?

Study the physics or engineering of the system—don't just discard them as waste byproducts of the process that led you to a good NIST test result.

• What do you know about the physics that might let you predict the result better than flipping a coin?
• What manufacturing flaws and failure modes could the engineered system have that might change the distribution?

Many of these deviations or failure modes will not be detected by generic statistical tests. As an extreme case, if your device chooses $$k$$ uniformly at random and produces $$\operatorname{AES}_k(0) \mathbin\| \operatorname{AES}_k(1) \mathbin\| \operatorname{AES}_k(2) \mathbin\| \cdots$$, except when it's broken and always chooses $$k = 0$$, generic statistical tests will never detect that broken case.

What matters for security is showing that the smartest, best-funded physicists in the world can't do better than a certain advantage at predicting what the outcome is, and that if the device fails in some way then you will detect that failure and stop relying on it.

The $$p$$-values of NIST statistical tests on samples you took during development? These are more like the waste byproducts of a process that led you to a good hardware RNG.

• I've seen you raise this point in many answers, but what does "study the physics or engineering of the system" actually entail? How do you enumerate all "plausible deviations" if you may not know all of them? To give an example, recently I've caught a bug in a RNG using a NIST suite that was caused by some bytes coming from uninitialized memory. It worked without me studying any physics or enumerating possible deviations. – Conrado Oct 11 '19 at 11:40
• @Conrado Here's an example of physics reasoning about a hardware RNG: crypto.stackexchange.com/a/51878 I left out a lot of details, of course, such as the sensitivity of the Geiger counter and analysis of its dead time and recovery characteristics. Personally I prefer coin tossing because the raw materials are a little easier to come by, even if it has some tiny deviations from uniform. – Squeamish Ossifrage Oct 11 '19 at 20:47
• @Conrado As for your RNG, there are two separate parts: (1) the random physical source, whose physics and engineering you need to study, along with whatever device driver you have to read from it; (2) the deterministic conditioning component to map high-entropy inputs into uniform outputs, like SHAKE128. The NIST tests have a null hypothesis of independent uniform random bits, which is almost certainly not how your physical source in (1) actually works—in which case the NIST tests don't even make sense! For example, the ionizing event counts are (approximately) Poisson distributed. – Squeamish Ossifrage Oct 11 '19 at 20:54
• @Conrado The NIST tests (or dieharder, etc.) may be helpful as a quick debugging aid when implementing your deterministic conditioning component in (2). But you should have a clear cryptographic design for the conditioning component that has been subjected to scrutiny in the literature, and the NIST tests are no substitute for test vectors and other forms of deterministic software verification to confirm that you've actually implemented the conditioning component you meant to implement. – Squeamish Ossifrage Oct 11 '19 at 20:56
• I think I get what you mean, thanks! As I side note, NIST SP 800-90B does have a non-uniform entropy estimator which can then be fed into the conditioning component so that you can e.g. determine how big the input to SHAKE128 should be. – Conrado Oct 12 '19 at 0:21

As you're dealing with randomness, the test results have randomness within them too. So combinatoric tests have to be statistically based. I've never seen Fisher used for this in the common randomness tests. By definition, $$p$$ is uniformally distributed 0 to 1 for the null hypothesis, ie. data is properly random. A common technique is for a Kolmogorov–Smirnov (KS) test against the expected uniform distribution. The test then outputs a single $$p$$ value for uniformity and thus data randomness. Hope for $$p > 0.01$$.

I only ever generate enough data for Diehard testing, but you see this approach used therein. For example, the 3D Spheres test consolidates 20 $$p$$ values into one:-

 ::              THE 3DSPHERES TEST                               ::
:: Choose  4000 random points in a cube of edge 1000.  At each   ::
:: point, center a sphere large enough to reach the next closest ::
:: point. Then the volume of the smallest such sphere is (very   ::
:: close to) exponentially distributed with mean 120pi/3.  Thus  ::
:: the radius cubed is exponential with mean 30. (The mean is    ::
:: obtained by extensive simulation).  The 3DSPHERES test gener- ::
:: ates 4000 such spheres 20 times.  Each min radius cubed leads ::
:: to a uniform variable by means of 1-exp(-r^3/30.), then a     ::
::  KSTEST is done on the 20 p-values.                           ::
^^^^^^


You can also see it being used in the following NIST results snippet taken from a NIST random excursion results Q & A which is talking about their interpretation:-

  9   3   6   5  10   8   7   7   8   8  0.808725     70/71      RandomExcursionsVariant
6   5   5   8  10   8   7   9   5   8  0.901761     69/71      RandomExcursionsVariant
3   9   5  12   6   6   6  10   8   6  0.437274     71/71      RandomExcursionsVariant
3   6   7   2  10  11   6  10   7   9  0.238562     71/71      RandomExcursionsVariant
4  10   6  12   3  13   4   4   5  10  0.033552     71/71      RandomExcursionsVariant


The decimal number (e.g. 0.808725) is a KS test performed over 9 3 6 5 10 8 7 7 8 individual scores where one failed with $$p$$ < 0.01. The NIST SP 800-22 software does this amalgamation automatically.

You should be able to adapt this technique to the 148 values of your NIST Template test if the program didn't produced them already. Spreadsheets and standard programming libraries can help.

• Would you care to elaborate on why you prefer a K–S test over Fisher's method? Either one is a way to give a single uniformly distributed $p$-value by which you can set any false alarm rate you want—the difference is in their statistical power to distinguish alternative hypotheses, which, of course, depends on the alternative hypotheses. – Squeamish Ossifrage Apr 19 '19 at 17:23
• @SqueamishOssifrage Actually, I don't prefer it. It's just the common way of doing it, as per the extracted example. That's from Diehard output. They do in the Dieharder summary report too. Most of the RNG papers I read do it this way. I guess no one's interested in alternative hypotheses. $H_o$ = random. The data set passes or fails. The NIST suite is about randomness validation, not causality. – Paul Uszak Apr 19 '19 at 17:40
• Under the null hypothesis, setting $p = p_1$ and ignoring $p_2, p_3, \dots, p_n$ also gives a uniform distribution on $p$ with which you can set any prescribed false alarm rate. Much cheaper to compute! Why not use that one? Presumably you're interested in the power of the tests that gave $p_2, p_3, \dots, p_n$ to distinguish alternative hypotheses of nonuniform distributions. But if you don't care about that, $p = p_1$, or even setting $p$ to be a fair d20 roll without reference to the data, works great. – Squeamish Ossifrage Apr 19 '19 at 18:18