Interpretation of (NIST) Non Overlapping Template Matching Test

Question

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 ?

Thank you in advance.

Answer 1

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.

Answer 2

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.