compressing randomly-generated numbers

Travis H. solinym at gmail.com
Tue Aug 29 17:03:29 EDT 2006


On 8/29/06, Alexander Klimov <alserkli at inbox.ru> wrote:
> Well, it not really a claim since there was no definition, here it is:
> A ``dependency stripping'' algorithm is a deterministic algorithm that
> gets a stream of unbiased (but not necessary independent bits) and
> produces a stream of several independent bits.

Well, this is a fairly strict definition, I think uniform and e-close to
independent is still potentially suitable for use in cryptography.

> > or a computationally-pseudorandom stream,
> This requires a random key.

I can't use e-close to (uniform and independent)?

> Recall that the whole point was to extract random bits -- if we
> already have useful random bits we can simply output them and discard
> the input stream.

I hear this argument often, and it appears that the people who say it
don't care about the rate of random bits, nor the desirability of not having
to trust any one source to be truly unpredictable, nor have they understood
the point of an extractor or hashing the output of multiple sources.

For example, I'd like to use the Quantis HWRNG, but since it is an
opaque container, then I cannot trust it fully.  If I had another source
that I could combine with it, then I do not have to trust it blindly;
the opponent would have to compromise both in order to be able to
predict the combined output.

> Consider ``x a x b x c x ...'', sampling every other bit throws away
> most of entropy.
> In general, there is no ``dependency stripping'' algorithm because an
> input x,x,x,..., where all x are the same (either all 0 or all 1), is
> possible. There is simply no enough entropy in the input to extract at
> least two bits.

No, you have no idea of the unpredictability of that source, because
it is unspecified and unpredictability is untestable.  That could very well
be the output of a perfect HWRNG.   So could 01010101, or 0000000,
or 1111111.  Each output is equally likely, and no amount of testing the
output can say whether the source is imperfectly random or truly random.

This was stated several times on this list; entropy depends on the
model of the source, not on the output.  The sequence:
0, 1, 2, 3, 4... 255, 0, 1, 2, 3, 4... 255 ...
has a zero entropy if the source is defined as "an 8-bit counter starting
at zero", and it has an entropy of 1 if the source is defined as "a HWRNG
that generates 8-bit outputs in a uniform and independent manner".
Re-read the definition of entropy, and pay particular attention to the
calculation of probability for a given event.

> Interestingly, an additional requirement that the input stream has at
> least two bits of entropy does not change the situation

I didn't understand this example.

> See above about ``sampling at a slower rate.''

I can take an analog random source, and sample it at one rate, and have
a nearly independent stream.  If I increase the sample rate, the bits will start
to become more and more dependent upon the prior bit.  So, if that is true,
then logically a serially-correlated stream will become less and less correlated
as I decrease the sample rate.  Taking every other bit corresponds to sampling
at half the speed, but doesn't require modifying the hardware.

It seems that you are saying there is no general solution, given a total lack
of knowledge about the source other than the fact that there is some
dependency between the bits.  I can agree with that.  However, if you
understand the physics of the source, then you do know something about
the random phenomenon used as a source, and in that case you can eliminate
specific kinds of dependencies that it may exhibit.

The easiest way to eliminate (computationally) bias and dependency in one
step is to combine with a CSPRNG.  You can reseed it periodically with
the combined output.
-- 
"If you're not part of the solution, you're part of the precipitate."
Unix "guru" for rent or hire -><- http://www.lightconsulting.com/~travis/
GPG fingerprint: 9D3F 395A DAC5 5CCC 9066  151D 0A6B 4098 0C55 1484

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



More information about the cryptography mailing list