How to select “good” bits which pass NIST statistical tests x% of the time?

Question

I am trying to implement an algorithm where the first step is to select "good" bits using the NIST test suite. In particular, I have $k$ streams with $n$ bits each. The original paper Toward Sensor-Based Random Number Generation for Mobile and IoT Devices (PDF) states

For a given bit to be ‘good’, it must pass at least 3 of the NIST tests at least 75% of the time.

What would be the best way to go about implementing this?

The NIST tests which I am using are the frequency test, frequency test within a block, runs test, longest run of ones within a block, DFT test, binary matrix rank test, and approximate entropy test.

Answer 1

From the question:

I have $k$ streams with $n$ bits each. (..)
The original paper (..) states "For a given bit to be ‘good’, it must pass at least 3 of the NIST tests at least 75% of the time"

I read "given bit" as meaning "any particular bit index in each of the $k$ streams"; and "of the time" as meaning "of each test run performed for bits at this bit index" (among possibly many such tests because $k$ exceeds the number of bits a given NIST test consumes). Thus the literal implementation could be:

• for $i$ from $0$ to $n-1$ (each of $n$ bit index in a sequence)
  • $p\gets0$ (the number of tests passed for bit $i$)
  • for each of the NIST tests considered (out of 15 at the last count)
    • let $b$ be the number of bits required by the particular NIST test (e.g. 100 for the Frequency (Monobit) Test; 1000 for the DFT test)
    • $f\gets\lfloor k/4b\rfloor$ (the maximum number of times the test is allowed to fail)
    • for $j$ from $0$ to $\lfloor k/b\rfloor-1$ (each group of $b$ streams)
      • perform the test on the $b$-bit sequence obtained by keeping bit $i$ of sequences $j\cdot b$ to $(j+1)\cdot b-1$ (numbering sequences and bits starting from $0$)
      • if the test fails
        • $f\gets f-1$
        • (optional: fail quickly) if $f<0$
          • break from the loop for $j$
    • if $f\ge0$ (the particular test passed at least 75% of the time)
      • $p\gets p+1$
      • (optional: succeed quickly) if $p\ge 3$
        • break from the loop for NIST tests
  • if $p\ge 3$ (at least 3 of the NIST tests passed at least 75% of the time)
    • that bit $i$ pass the original paper's criteria; remember to use this bit in the future.

It is possible to adjust $b$ for each test as a function of $k$ so as to reduce the proportion $k\bmod b$ out of $k$ bits that are not tested, or splitting the $k$ bits almost evenly across sequences tested (within 1 for tests with no constraint on $b$).

NIST tests with $b>k$ succeed for 0 out or 0 time they are run, and accordingly the "at least 75% of the time" criteria is met; thus a test that does not run still accounts in the minimum of 3 tests that pass; I'm among those thinking this is a telltale sign that the criteria is profoundly unsound. Main problem really are:

• As far as we can tell from the question, NIST tests are run unmodified, thus with low $p$-value (like 1%), making the 25% failure rate tolerated seemingly unjustifiable.
• When any test consistently fails, the bit sequence has been distinguished from uniformly independent bits, yet it is sometime kept; this means we are not using the tests for what they are designed to do: test sequences against the null hypothesis that they are uniformly independent bits.
• Treating all the tests equals (when they are designed to detect very specific defects) is a telltale sign of an absence of method.

My algorithm is only the literal implementation of what the paper prescribes. This shall not be interpreted as a recommendation; rather, the opposite: the rationale of the prescription evades me. Advice only binds who trusts it.

Answer 2

Fgrieu has provided a good implementation of your question. But I would add some observations that you might want to consider.

Everything revolves around this entropy heat map:-

The paper's team have done something that I've never seen before. They have used selected NIST tests to qualitatively estimate the entropy coming from various hardware devices. I advisedly use the term qualitatively and not quantitatively as is typical in these cases. They have in fact inverted the usual method for true randomness extraction. So rather than pooling weak entropy and then whitening it with a cryptographic hash function, they have produced the majority of their randomness by initially triaging which bits to use (the black bits) or discard. The team seems to have gotten a reasonable set of final randomness test results, but it's via a very unusual method.

I don't like it. It's never done this way but I accept that that randomness tests can be used to identify random streams, even if they are created artificially. I would suggest that you approach this from the traditional way, and simply XOR all k streams together. Then estimate the entropy rate via Shannon's formula or better still, via compression.

There is a large rider on the paper's findings. The bit streams were taken all together from 37 devices. This is akin to XOR, and vastly improves the entropy of weak sources. XOR 37 of anything, and you'll probably get good entropy. You may find that in your case, each stream in itself is very weak. You need to measure it traditionally to know for sure.