building a true RNG (was: Quantum Computing ...)

[bear]

On Mon, 22 Jul 2002, John S. Denker wrote:

>David Honig wrote yet another nice note:

>I'm not trying to be dense, but I'm totally not
>understanding the distinction here.  The following
>block diagram is excellent for focussing the discussion,
>(thanks):
>
>> Source --> Digitizer --> Simple hash --> Whitener (e.g., DES)
>
>OK, we have DES as an example of a whitener.
>-- Can somebody give me an example of a "simple hash"
>that performs "irreversible compression" of the required
>kind?

Depends on the data and how much entropy you suppose it
has, really.  An irreversible compression function that
I use when extracting entropy from text (for other
purposes) is to have a counter.  Each time you process
a character, you add the character code to the counter,
then multiply the counter by 2.4 rounding down.  This is
based on estimates of 1.33 bits of entropy per character
in english text, and requires an "initialization vector"
(in this case an initialization value) twice as long as
the character code to prevent you from taking too many
bits from the first few characters alone.

For something like a lava-lamp picture, your compression
function might be first converting it into a 4-color image,
editing out the constant parts (eg, the lamp base and edges),
compressing that using PNG format, and then taking some
similarly counter-based function of those bits. Using a
time series of pictures of the same lava-lamp, you'd have
to adjust for lower entropy per byte of processed PNG (by
using a lower factor), because it could be redundant with
other frames.

>-- Isn't the anti-collision property required of even
>the simplest hash?  Isn't that tantamount to a very
>strong "mixing" property?  If there's strong mixing in
>the simple hash function, why do we need more mixing
>in the later "whitening" step?

You are talking, specifically, about cryptographic hash
functions.  The diagram specifies a simple hash function.
The distinction between cryptographic hashes and simple
hashes is, a simple hash is supposed to produce evenly
distributed output.  A cryptographic hash is supposed to
produce evenly distributed *and unpredictable* output.
A simple hash, plus a whitener, is about what you're
thinking of for a cryptographic hash function.

>I assume digestion means the same as distillation?

Roughly.  People talk of "digestion" of a datastream, or
"distillation" of entropy, or "irreversible compression",
etc.  It's roughly the same thing.

>Gimme a break.  In particular, gimme an example of a crypto
>algorithm that will fail if it is fed with a random-symbol
>generator that has "only" 159.98 bits in a 160 bit word.

That's one bit per 8k. I guess it just depends on which
8k comes through and how much your opponent can make of
one bit.



>> >I see no point in "whitening" the output of such a
>> >distiller.
>>
>> So the adversary can't look back into your logic.  A 'distiller'
>> which produces quality entropy (after digesting an arbitrary
>> number of bits) needn't be as opaque as a crypto-secure hash is.
>
>I'm still needing an example of a distiller that has
>the weakness being alleged here.  In particular,
> -- either it wastes entropy (due to excessive hash collisions)
>in which case it isn't a good distiller, and whitening it won't
>improve things (won't recover the lost entropy), or
> -- it doesn't waste entropy, in which case the output has entropy
>density of 159.98/160, in which case there is nothing to be gained
>by so-called "whitening" or any other post-processing.

I think you may be right about that -- whitening protects you
from errors in an overly-simple distiller such as I described
above, but if you've got a really fine-tuned one, it doesn't
help much.


>In particular, (proof by contradiction) consider the following
>scenario:  suppose she captures 100 bits of output, and wants
>to use it to make some predictions about the next 60 bits of
>output.  She uses the 100 bits to "see back into" the
>hypothetical simple-hash function, learn something about the
>input thereof, and then pushes that forward again through the
>simple-hash function to make the predictions.  But this scenario
>violates the most basic requirements of the hash function, even
>the simplest of simple-hash functions.

Again, it violates the requirements of a cryptographic hash
function, not a simple hash function.


				Bear


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