Proving the randomness of a random number generator?

[Victor Duchovni]

On Mon, Dec 05, 2005 at 02:21:02AM -0600, Travis H. wrote:

> 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]".

I read the question as something akin to what an on-line gambling site
might seek to assure its customers that its dice are not loaded.

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

The outcome is equally surprising to all observers, having it be
completely predictable by all observers is an uninteresting degenerate
case.

> That's the main thing
> people are looking for in cryptographic RNGs.  What kind of randomness
> or security properties are you talking about?

There is no way to prove that dice you are watching on TV are not loaded
(even if the value distribution is fair). If one gets to participate in
a verifiable protocol that rolls the dice, the picture is different.

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

Actually, even a perfect hardware RNG is of no use in convincing the
skeptical remote observer. How do you prove that the output came from said
RNG?  How do you prove that it is "delayed", and that other participants
are not viewing the output a few steps ahead of the skeptical observer?

If I understood the OP's question correctly (indeed it was not precise),
the answer is that no proof is possible for a non-interactive RNG.

-- 

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