At 12:12 PM -0400 6/8/2000, Don Davis wrote:
>steve b., perry m., and arnold r. all point out,
>quite correctly, that hashing was used for noise-
>whitening, long before sgi's lavarand and before
>my disk-randomness paper. the difference that
>sgi's work and mine offered was a more rigorous
>notion of randomness. by explicitly drawing on
>the strict mathematical definition of "chaos," we
>could call our generators' outputs random per se.
>thus, chaos-based rngs go beyond prior work on
>noise-whitening, but the difference is perhaps
>more important theoretically than practically.
I don't want to disparage Don's contribution in any way, but it is my
non-lawyer understanding that patents are awarded to the person who
first comes up with an idea, not the person who first provides a
rigorous underpinning for that idea.
As for SGI, their patent defines chaos as follows: "A chaotic system
is one with a state that changes over time in a largely unpredictable
manner." That is hardly "the strict mathematical definition."
>
>both generators produced truly unpredictable bits,
>though SGI & i differed in our statistical criteria.
>my experiment produced asymptotically i.i.d. uniform
>bits, while lavarand produced _effectively_ uniform
>bits. in other words, both SGI and i offered truly
>random bits, and not merely securely unpredictable
>bits. note the contrast with prior work: while
>arnold's DoD citation from 1985 does offer a
>practical & effective way to seed a PRNG, the doc't
>explicitly calls the product bits "pseudo-random."
I think it is important not to let the meaning of term
"pseudo-random" degenerate into "less than perfectly random." It has
a very specific, widely accepted meaning. For example, RFC-2828
defines "pseudo-random" as:
" A sequence of values that appears to be random (i.e.,
unpredictable) but is actually generated by a deterministic
algorithm."
There are applications where a PRNG may be preferable to a source of
true random numbers, for example in Monte-Carlo analyses where it
desirable to be able to repeat any given calculation.
Both the DOD Password guidelines and the SGI patent envision using a
random quantity to seed a PRNG which is then used to provide multiple
instances of cryptographic constants, passwords in the DOD
guidelines, passwords and cryptographic keys in the SGI patent. (What
the SGI patent refers to as a "random number generator" is really a
PRNG.)
>
>our/my novel contribution was to justify dropping
>the prefix "pseudo-". afaik, before my paper,
>noone spoke of software "TRNGs". no-one believed
>it was possible to produce truly random bits
>without specialized hardware, though many of us
>knew that hashing or encrypting an irregular or
>secret input was necessary & sufficient for most
>cryptographic purposes.
>
> - don davis, boston
I think most researchers were reluctant to use the term "truly
random" because it is such a strong assertion and because there is a
fair amount of disagreement as to the proper definition of
"random."� However, some people did speak of possibility of producing
true random bits. For example, here is a quote from: PGP(tm) User's
Guide Volume I: Essential Topics by Philip Zimmermann Revised 22
May 94: (PGP 2.6)
"The public/secret key pair is derived from large truly random numbers
derived mainly from measuring the intervals between your keystrokes
with a fast timer. "
PGP hashes a large number of timing values to produce those bit. I
suspect the same quote can be found in earlier editions.
Arnold Reinhold
