Re: Good enough for crypto?

From: Scott Wilber (swilber_at_comscire.com)
Date: 11/27/03 

Date: 26 Nov 2003 20:25:03 -0800

Richard Herring <junk@[127.0.0.1]> wrote in message news:<2inNh$m68Mx$EwJq@baesystems.com>...
> In message <3fc4cb88$0$4847$ba620dc5@nova.planet.nl>, Ernst Lippe
> <ernstl-at-planet-dot-nl@ignore.this> writes
> >On Tue, 25 Nov 2003 17:06:24 +0000, Richard Herring wrote:
> >
> >> In message <3fc350f0$0$3245$ba620dc5@nova.planet.nl>, Ernst Lippe
> >> <ernstl-at-planet-dot-nl@ignore.this> writes
> >> [...]
> >>
> >>>Normally, when people are talking about "the entropy of a source" what
> >>>they mean is the entropy of the best possible statistical model of
> >>>that source.
> >>>
> >>>Perhaps, some examples will make this clearer. Suppose that you
> >>>have an entropy (bit)source, for which you can show that it is unbiased
> >>>and that successive bits are independent. The best model for this
> >>>source is a binomial distribution with p= 0.5. The entropy from
> >>>this model is 100%, every output bit contains 1 bit of entropy.
> >>>
> >>>Now let's take the bits in the value of pi. When you assume that the
> >>>best model is again the binomial distribution, the entropy in these
> >>>bits is again 100%. However, when you assume that the best statistical
> >>>model is the binary expansion of pi, you can always predict the next
> >>>bit, so the entropy under this model is zero.
> >>
> >> If pi is normal, this is true for _any_ sequence of bits ;-)
> >>
> >> Finding the starting point is left as an exercise for the reader.
> >
> >The total entropy of any PRNG is equal to the amount of information
> >in its parameters. In this case the only parameter is the starting
> >point. Because the total entropy for any PRNG is fixed, the average
> >entropy per output bit will always go to zero when you take longer
> >output sequences.
>
> Of course. But who mentioned a PRNG? "Binary expansion of pi" is the
> model, not the generator.

The binary expansion of Pi or e or Sqrt(3), i.e., any irrational
number may be used as a model, while the program (including the
computer it is running on) that actually spits out the bits is the
generator. All of these generators are totally deterministic, and as
such produce sequences of exactly zero true entropy. At most, the
sequences contain a total amount of entropy, or more specifically,
complexity, that is contained in the simplest program (generator)
needed to produce the output. Even with this theory of entropy, the
per-bit entropy approaches zero as N increases without bound.

It is simpler and easier to classify different types of generators
using the definition that any generator based on any
model/algorithm/physical device whatever; whose every bit is 100%
predictable produces sequences containing exactly zero true entropy.

This would make binary expansions of Pi and all other irrational
numbers zero entropy sources. To be clear, sequences based on these
binary expansions may contain statistical entropy that approaches
exactly 1.0. Statistical entropy is here defined as the complexity
relative to maximum possible complexity. Complexity is something that
we can estimate algorithmically; on any sequence from any source.

By this definition, any sequence that is known, stored, printed or
otherwise published contains zero true entropy.

By contrast, "perfect" true random number generators (TRNG) produce
sequences of bits that are not predictable beyond 50.0% within
expected statistical bounds for a given N by any means whatever.

The caveat about a known or stored sequence containing zero entropy is
not inconsistent with the use of "true" random sequences being used
for totally secure cryptographic functions. As long as the sequence
from a TRNG is kept secret or unknowable by all but the one using it,
the outcome is perfectly secure. This follows directly from the fact
that no computational method can be applied to exceed the 50%
probability of predicting any bit in the sequence.

An interesting thought relating to quantum gates and random sequences.
 It will be possible to "store" a sequence of qbits or quantum
probability functions in a properly designed quantum computer that is
not known or knowable by anyone until the sequence is destructively
read out. A truly random sequence! This is a physical analog to
quantum cryptography that could be transported instead of transmitted.

Enough.

Scott Wilber

Relevant Pages

  • Re: Linfords Fallacy
    ... This way the entropy of the sequence of all heads or all tails is 0. ... probability distributions, not sequences. ... I would agree with Kolmogorov's complexity idea. ...
    (sci.math)
  • Re: Good enough for crypto?
    ... > such produce sequences of exactly zero true entropy. ... that is contained in the simplest program (generator) ...
    (sci.crypt)
  • Randomness from natural texts
    ... hardware generation of randomness, estimation of entropy, ... xor-ing a sufficient number of such ... resulting sequences from different texts and doing some ...
    (sci.crypt)
  • Re: Linfords Fallacy
    ... This way the entropy of the sequence of all heads or all tails is 0. ... The sequences with alternating elements(010101... ... is the additive identity and 1 is the ... multiplicative identity. ...
    (sci.math)
  • Re: compression of equal probability sources
    ... I wonder if original poster is still around and ... Im inclined to believe mr. Singer that both the sequences you posted have the same entropy with my model, and furthermore that my guess that this is so for all possible sequences is also true (it shouldn't be too difficult to construct a proof by complete induction for this, if there isn't a simpler way mr. Singer sees which I can't ... ... So lets just compute the entropy for the simplest sequence, all 0s followed by all 1s ... ...
    (comp.compression)
Quantcast