Proving the randomness of a random number generator?

[bear]

On Fri, 2 Dec 2005, Lee Parkes wrote:

> Hi,
> Apologies if this has been asked before.

> So, the question is, how can the randomness of a PRNG be proved within
> reasonable limits of time, processing availability and skill?


"Randomness" is a quality that, intrinsically, cannot be proven.  Period.
You can take an urn with a hundred numbered balls and pull them out one
at a time -- a truly random process -- and the sequence from one to a
hundred by ones is just as likely as every other sequence.  If it happens
to come up, even that doesn't prove that it wasn't a random process.

On a practical note, I would test the PRNG's output against pattern detectors.
Spectral Analysis software is quite good at detecting patterns in PRNG output.

Then there are the pattern detectors built into various file compression
tools.  If gzip or winzip or arc or arj or (etc) can find a pattern, it
will succeed in producing a shorter file than the original.

Before you do any of that, however, check the literature to see if it's
already been done.  If you're using a commercial or cryptological PRNG
that's been studied, read the papers of the people who studied it, and
the papers of people who studied competing products.  See if they found
anything usable or any useful property that you can use to support a
claim of "randomness."  (note: it won't actually *be* randomness, for
the simple reason that that can't be proven.  But some systems have
proofs that someone who has access to the entire output of the PRNG so
far has no strategy better than random guessing for determining the
next and subsequent outputs, and that may be "random" enough for your
bosses.)


					Bear


---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at metzdowd.com