1
$\begingroup$

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

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – rikhavshah Dec 2 '18 at 8:18
  • $\begingroup$ @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. $\endgroup$ – Paul Uszak Dec 4 '18 at 12:50
0
$\begingroup$

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.

$\endgroup$
-4
$\begingroup$

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 should be able to adapt this technique to the 148 values of your NIST Template test. Spreadsheets and standard programming libraries can help.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Squeamish Ossifrage Apr 19 at 17:23
  • $\begingroup$ @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. $\endgroup$ – Paul Uszak Apr 19 at 17:40
  • $\begingroup$ 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. $\endgroup$ – Squeamish Ossifrage Apr 19 at 18:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.