Proving the randomness of a random number generator?

[Travis H.]

On 12/3/05, Victor Duchovni <Victor.Duchovni at morganstanley.com> wrote:
> Actually, this is inaccurate, proving the strength of AES or factoring is
> difficult, and may never happen, we may even prove AES to be not secure
> (in a broad sense) some day. Proving an RNG secure is *impossible*.

I'm not sure it's impossible, but you certainly have to restrict the
scope from "unconditional security", which is an impossibility anyway.
 By analogy, an attacker may have encrypted some plaintext with your
key and gotten your ciphertext before.

Here is a reasonable security model:
An attacker has access to all outputs of this PRNG x_0 .. x_n and
nothing else of relevance.
Can he guess x_(n+1) with probability greater than chance?

Even if you allow the attacker to have seen the sequence before, using
assumptions such as "the bounded storage model" may prevent him from
completely compromising the PRNG:
http://www.crypto.ethz.ch/research/itc/samba/

Part of the problem is that we just don't know what the attacker has
access to, and that the implicit goal (prove that there is no
algorithm for predicting x_(n+1) better than y) is a universal, akin
to cipher design's goal of proving that there is no algorithm for
decrypting ciphertext without the key that is more efficient than y.

There are other possible goals; one might want an observer to be
unable to distinguish it from a stream of numbers drawn from a uniform
distribution, that re-seeding recover from state compromise, that the
smallest program which generates the output x_0..n be of length O(n),
that predicting the next output implies being able to solve a hard
problem.  There are some examples of the latter, for example the
blum-blum shub (BBS) generator:
http://en.wikipedia.org/wiki/Blum_Blum_Shub

I believe that it has been proven that if one-way functions exist,
then secure PRNGs exist.  If I am not mistaken, lack of one-way
functions would prevent effective encryption.  After all, conventional
encryption is just a one-way permutation based on a secret input k. 
It is not even necessary that *trapdoor* one-way functions exist,
which is a common assumption in public-key systems.

For more information, see "Pseudorandomness and Cryptographic
Applications", ISBN 0-691-02546-0, by Michael Luby.  Warning:
theory-intensive.
--
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