Ranking “amount of randomization” in a sequence

Question

I'm facing the problem of implementing pseudo random bit generator (PRBG) on a very low power device. NIST.SP800-22 "Statistical test suite for Pseudo Random Generators" suggests a suite of 15 tests for randomness.

• Is there a way to use those tests as "randomness measures" except from pass / fail?

That is, suppose you want to do changes in your random generator, and to measure, whether you improved the randomness or not. The NIST suite suggests a way to decide whether you are random or not, but its hard to extract the information of "improvement": For two different algorithms, it may happen that for some tests the first gives higher p-value, for other tests the same PRBG gives lower p values, although both pass all tests. So'

• is there some "measure of amount of randomness" test, or or how can NIST tests turn to be such?

Answer 1

The various nist tests look for patterns which should not be present in random data. For any such pattern, e.g imbalance, repetition etc. you can ask youself what is he likelyhood of this strength imbalance or worse occuring in random data. this is the pValue.

If we toss a coin multiple times we can count heads and tails. The closer they are to even the better. We can quantify this as probability. We then look at longer sequences and also expect them to show up more or less with equal frequency and again we can calculate pValue to quantify how likly discrepencies found are to be chance. Most Nist tests already come with this built in.

We also like to analyze the cycle size of PRNGs even when they are too long to detect in a quick black box test this is another measure of "randomness".

Remember these tests are not sufficient for a PRNG to be secure. And though failing any means the stream is distinguishable from random it may still be decent for some cryptographic operations (Solitaire cipher as an example of a biased yet reasonably secure stream cipher).