Proving the randomness of a random number generator?

Travis H. solinym at gmail.com
Mon Dec 5 03:21:02 EST 2005


On 12/4/05, Victor Duchovni <Victor.Duchovni at morganstanley.com> wrote:
> Wrong threat model. The OP asked whether the system generating random
> numbers can prove them to have been "randomly" generating to a passive
> observer.

I didn't read it that way, but the question wasn't particularly
well-formed. I'm not sure what you mean by "prove them to have been
randomly generat[ed]".  Given your discussion of an attacker being
able to predict the sequence due to having seen it before, it sounds a
lot like you're talking about unpredictability.  That's the main thing
people are looking for in cryptographic RNGs.  What kind of randomness
or security properties are you talking about?

There's another definition of randomness I'm aware of, namely that the
bits are derived from independent samples taken from some sample space
based on some fixed probability distribution, but that doesn't seem
relevant unless you're talking about a HWRNG.  As another poster
pointed out, this definition is about a process, not an outcome, as
all outcomes are equally likely.

If the goal is truly to prove that the numbers are nondeterministic,
then an investigation of the physical proceses involved and careful
measurement (of the generation device, not the digital output!) is the
only proper way to get some assurance.  I'll sidestep the question of
whether anything is really nondeterministic for the moment (God is
omniscient, or so I'm told).
--
http://www.lightconsulting.com/~travis/  -><- Knight of the Lambda Calculus
"We already have enough fast, insecure systems." -- Schneier & Ferguson
GPG fingerprint: 50A1 15C5 A9DE 23B9 ED98 C93E 38E9 204A 94C2 641B

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



More information about the cryptography mailing list