8
$\begingroup$

Suppose I receive a list of 1 million coinflips, and I want to know how likely it is that the list was randomly generated.

My first thought would be to count the number of heads and tails, which should be evenly distributed (around 500.000). But suppose the distribution looks normal, its still possible the list contains patterns or repititions. For example, the first half of the list may be the heads, and the last half the tails. In real random data, that would be highly unlikely.

So how do you calculate the 'randomness' of this list?

Improve this question
$\endgroup$
6
  • $\begingroup$ possible duplicate of What tests can I do to ensure my PRNG is working correctly? $\endgroup$
    – otus
    Commented Oct 16, 2014 at 14:12
  • 8
    $\begingroup$ Short answer: You can't test if it's good. You can only check if it's bad in specific ways. $\endgroup$
    – CodesInChaos
    Commented Oct 16, 2014 at 14:21
  • $\begingroup$ Maurer's universal statistical test (see A. J. Menezes et al., Handbook of Applied Cryptography, sec.5.4.5 (available online)) may be of some interest to you. $\endgroup$
    – Mok-Kong Shen
    Commented Oct 16, 2014 at 19:05
  • $\begingroup$ See @e-sushi 's answer in the duplicate question for several good tests. $\endgroup$
    – John Deters
    Commented Oct 17, 2014 at 3:07
  • $\begingroup$ @otus I disagree about your proposed duplicate: testing the randomess of a CSPRNG output is completely different from testing the randomness of an entropy source. For one thing, the former is just about useless, the latter is useful. $\endgroup$
    – Gilles 'SO- stop being evil'
    Commented Oct 17, 2014 at 9:42

2 Answers 2

Reset to default
7
$\begingroup$

You can never actually prove that it was generated randomly or pseudorandomly. You can only prove with high probability that it wasn't. Calculating the number of heads and tails is one way. Another is calculating runs of consecutive heads or tails. There is a suite of statistical tests from NIST in their FIPS 140-2 document which is a good place to start.

Having said that, for cryptographic purposes you really need to be sure that you are using a secure random number generator and there aren't any tests you can apply to the data itself to sufficiently guarantee that it is secure enough.

Improve this answer
$\endgroup$
4
  • 1
    $\begingroup$ Can you never prove pseudorandomness or do we just not know how? Existance of one-way functions would imply existence of pseudorandom generators right? It would also imply $P\neq NP$. $\endgroup$
    – mikeazo
    Commented Oct 17, 2014 at 18:24
  • 1
    $\begingroup$ Given an algorithm, you can prove that it's output is pseudorandom based on some computational assumption, but that is as close as you can get. For instance, Blum-Blum-Shub is a PRNG that is pseudorandom if factoring is a hard problem. As you say, PRNG implies $P \neq NP$, which is not known. $\endgroup$
    – Travis Mayberry
    Commented Oct 17, 2014 at 19:37
  • $\begingroup$ You mention that you can only prove with high probability that it wasn't produced randomly or pseudorandomly, but that's not true at all against an intelligent adversary. Any statistical test you perform can be bypassed. $\endgroup$
    – Stephen Touset
    Commented Oct 23, 2014 at 22:08
  • $\begingroup$ My statement was a bit ambiguous, but I did not mean that with high probability you will be able to prove that something is not random. I meant that all you can hope for is to prove, with a high degree of certainty, that something is non-random. $\endgroup$
    – Travis Mayberry
    Commented Oct 24, 2014 at 23:01
1
$\begingroup$

Find NIST statistical tests suite for (p)rng provided by National Institute of Science and Technology (Formerly NBS, National Bureau of Standards) here http://csrc.nist.gov/groups/ST/toolkit/rng/index.html

and documention at NIST (see above) or here: National Institute of Science and Technology (Formerly NBS, National Bureau of Standards)

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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