Proving the randomness of a random number generator?

[Victor Duchovni]

On Fri, Dec 02, 2005 at 11:54:03AM +0100, Lee Parkes wrote:

> Hi,
> Apologies if this has been asked before.
> 
> The company I work for has been asked to prove the randomness of a random
> number generator. I assume they mean an PRNG, but knowing my employer it
> could be anything.. I've turned the work down on the basis of having another
> gig that week. However, it raised the issue of just how this could be 
> achieved. As far as I'm aware there are no strong mathematicians in the team, so
> it will get thrown out to the first available person (cool idea, eh?). There
> will most likely be very little time allocated to do it.
> 
> So, the question is, how can the randomness of a PRNG be proved within 
> reasonable limits of time, processing availability and skill?
> 

It can't be done. What can be done instead is that multiple parties
participate in a random number generation protocol. The protocol ensures
that all can be confident that the number is at least as random as each
one of them wants it to be. If at least one party is using a decent PRNG,
or a physical source of "real" entropy then all the parties get random
numbers, and no-one feels cheated if they like the randomness of their
own contribution to the protocol.

-- 

 /"\ 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