Proving the randomness of a random number generator?

[Victor Duchovni]

On Sat, Dec 03, 2005 at 10:47:52PM -0600, Travis H. wrote:

> 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?
> 

Wrong threat model. The OP asked whether the system generating random
numbers can prove them to have been "randomly" generating to a passive
observer. The answer is "no", this is not possible for the reasons
explained before. This is different from security of random numbers I
generate against being predicted by an adversary.

-- 

 /"\ ASCII RIBBON                  NOTICE: If received in error,
 \ / CAMPAIGN     Victor Duchovni  please destroy and notify
  X AGAINST       IT Security,     sender. Sender does not waive
 / \ HTML MAIL    Morgan Stanley   confidentiality or privilege,
                                   and use is prohibited.

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