Re: Good enough for crypto?

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

Date: 28 Nov 2003 21:58:02 -0800

Mok-Kong Shen <mok-kong.shen@t-online.de> wrote in message news:<3FC7CAC9.DD08692A@t-online.de>...
> Scott Wilber wrote:
> >
>
> > There are many so-called random number generators that contain
> > virtually no quantum components. Certainly the Lava Lamp generator,
> > which is based on turbulent flow in a heated viscous liquid, is one of
> > them. Another important example is the mechanical systems used to
> > select numbers in most lotteries. These employ plastic or rubber
> > balls that are "mixed" by air flow or rolling drums. Again, these are
> > totally chaotic, and therefore not in the least truly random. This is
> > not to say that they are significantly biased or that they can be
> > predicted to any profitable degree. The parameters involved are
> > extremely complex and we have no present methods of measuring them.
> > Also, it would do no good to be able to predict each ball real-time
> > since all lotteries close before the drawings begin.
>
> Having, as said, barely knowledge in physics, I suppose
> it would be fine if you could explain a little bit
> concretely how your scheme distinguishes itself in matter
> of the 'quantum component' mentioned above in comparison
> to a few other hardware randomness generators that are
> deficient. Isn't it that all currently employed hardware
> generated randomness could be considered to stem from
> certain electromagnetic noise or thermal noise (or
> should it instead be quantum noise)?

In my opinion, there are three types of entropy that are commonly in
use. Only Quantum Entropy, deriving from a pure quantum process, is a
true entropy source. The purest (theoretically simplest) type of
quantum entropy is produced by "splitting" a single polarized photon
with a polarization beam splitter rotated to produce an exact 50/50
probability of the photon exiting either the vertical or horizontal
port. The photons are detected by one of two single-photon detectors
located at each of the output ports. Of course, there is no such
thing as a split photon; this is a mathematical abstraction describing
the photon's probability function or "quantum wave".

The second type of entropy is actually chaotic complexity. This is
the most common "entropy" source used in true (non-deterministic)
random number generators. Examples are, as mentioned; Lavarand, pure
thermal noise, mechanical lottery machines and chaotic analog
circuits. There is little to no true entropy produced by these
sources; however, they do generally meet the present criteria for true
randomness. This is because the level of chaotic complexity is so
high that consecutive points become theoretically unpredictable.
(See Lyapunov Exponents http://hypertextbook.com/chaos/43.shtml )
This does not mean that these systems will always remain entirely
unpredictable; only that our level of mathematical sophistication and
physical measurement are too limited to do so today.

The third type of entropy is pseudo-entropy. This is purely a
complexity that is produced by mathematical algorithms - pseudorandom
number generators. Pseudo-entropy is exactly zero true entropy and no
sequence generated by a pseudo-entropy source or algorithm can ever be
considered random. A pseudorandom sequence can certainly present
statistical properties that are virtually indistinguishable from the
best TRNG, but there is always the possibility of finding a way of
predicting the next bit in the sequence given enough bits and enough
computing power.

So the fundamental difference in the types of entropy described is in
the possibility of predicting bits in sequences generated by each one.
 To summarize, Quantum Entropy produces theoretically unpredictable
sequences under all circumstances; Chaotic Entropy, if properly
applied, produces sequences that are not currently predictable, but
may yield to some degree of prediction with more advanced modeling
and/or measuring devices; Pseudo Entropy produces sequences that are
always theoretically predictable, given sufficient resources.

Virtually all TRNG's advertised and marketed today produce sequences
from a mixture of Quantum and Chaotic Entropy in varying proportions.
Noise diodes produce avalanche noise, which is not identical to pure
shot noise, but has very similar statistical properties. Thermal
noise in resistors produces nearly perfect Gaussian white noise within
a band limited on the low end by flicker and process noise and at the
high end by parasitic capacitance in a distributed series/parallel
configuration with the resistor. All amplifiers produce some thermal
and some shot noise, so no matter what noise source one starts with,
the electronics that interface with it and produce the final output
add their own portion of noise and modify the total transfer function.

>
> >
> > Unfortunately, we have no other tool than mathematical analysis to
> > assess the quality of any sequence of bits. If we know the generated
> > sequence was based on a deterministic or a non-deterministic process,
> > it is possible to use slightly different approaches. Most of the
> > analysis is, of course, statistical in nature. There is NO analytical
> > method that can distinguish between a deterministically- and a
> > non-deterministically-generated sequence, providing there is no
> > significant defect in the statistical properties of either.
>
> Therein lies the dilemma of practically (and reliably)
> evaluating entropy in my humble view. If a PRNG is so
> good that it passes all (currently) available statistical
> tests, then one (without knowledge of the generation
> process) would hardly be able to know that there is in
> fact very little entropy. (On the other hand, it seems
> to me to be justified that such a superb pseudo-random
> source could very well substitute a true random source
> in practical applications.)

This is certainly correct. Firstly, no analysis can determine the
entropy of a source by analyzing its output sequence, and secondly,
The Mersenne Twister followed by our infinitely recursive,
multiple-feedback shift register (IRMFSR) stirring function produces
sequences that have passed all our tests cumulative to 10's of
trillions of bits. (By the way, NO other generator has passed our
tests so far)

This is good enough for almost every function that we use random
numbers for. A very simple TRNG, such as the ComScire PCQNG, could be
used with this exceedingly good pseudorandom generator to determine
which of the bits from the stirring function should be used and which
should be discarded. This would produce a strong one-way function
precluding the possibility of ever reproducing the sequence. This
should serve in any cryptographic application, although I may be
flamed forever for saying so. Anyway, I like a stimulating
discussion.

> >
> > If we know that a sequence is deterministic (pseudorandom), than it is
> > possible to search for patterns that would only occur in this type of
> > sequence. This type of analysis can only succeed if the generator
> > produces significant statistical defects that can be analyzed further,
> > or if the actual generating algorithm can be guessed or otherwise
> > determined.
> >
> > If a sequence is non-deterministic, it will exhibit certain
> > properties. The most important of these relates to its
> > autocorrelation function.
> >
> > The autocorrelation function of a non-deterministic sequence will
> > always decrease with increasing order. The decrease will either be
> > monotonic or the function will oscillate, and the amplitude of the
> > oscillations will decrease monotonically. This is proved by proving
> > the behavior of the generalized autocorrelation function of the random
> > process, including its measurement device - something I will not try
> > to show in this setting.
> >
> > If a sequence is analyzed and is shown to violate this property, than
> > it is at least partly or entirely deterministic. An obvious example
> > is if a pseudorandom sequence is tested for autocorrelation with order
> > equal to its period, where the AC will jump to 1.0.
> >
> > To the best of my knowledge, this theorem on non-deterministic
> > sequences is original and has never been published before. But, its a
> > big world and if anyone has seen this before, I would like to know.
>
> I suppose that by non-deterministic you refer to true
> randomness. Your mentioned original yet unpublished
> study seems interesting. Do you have any intention
> of letting your result open to the statistics people?
> On the other hand, I remember to have read somewhere
> that a white noise (which a good true randomness should
> approximate, if I don't err) doesn't have the property
> of monotone diminution you described but only has an
> auto-correlation function that fluctuates within a fairly
> narrow band around zero.
>
> M. K. Shen

Non-deterministic is typically used if the generator is not
algorithmic or pseudorandom, has no defined period and is generally
not reproducible. It is a little broader in the context of the
present discussion since we may define "true random" more precisely.

I am considering formally publishing this and some other theoretical
developments relating to entropy and random number generation.

The monotonic decrease referred to does not apply to the distribution
of values that are expected from the probability distribution function
(approximately Gaussian for long sequences) and the number of values
taken (N). The probabilities of the autocorrelation function must
significantly exceed, in the statistical meaning, these expected
values.

Scott Wilber

Relevant Pages

  • Re: Good enough for crypto?
    ... >> derive their entropy entirely from pure quantum sources. ... Our latest hardware generator, the ComScire QNG ... assess the quality of any sequence of bits. ... The autocorrelation function of a non-deterministic sequence will ...
    (sci.crypt)
  • Re: ID revisited ... ( Yet another reason for abandoning numerical
    ... except it was poker and an automatic shuffling machine. ... cheaters knew the sequence in advance, what do they need all those ... but only with a few bits of secure entropy. ... pseudo-random number generator if it was not cryptographically secure ...
    (talk.origins)
  • Re: Good enough for crypto?
    ... > derive their entropy entirely from pure quantum sources. ... > generators do have a quantum component in their entropy source. ... Our latest hardware generator, the ComScire QNG ...
    (sci.crypt)
  • Re: Good enough for crypto?
    ... after seeing that you also mentioned 'quantum' ... generators do have a quantum component in their entropy source. ... Our latest hardware generator, the ComScire QNG ... The quantum component in the PCQNG is smaller, ...
    (sci.crypt)
  • Re: 10 questions on QM postulates
    ... > modern physics. ... > questions related to the postulates of Quantum mechanics which I find ... observables, must have only real eigenvalues, and Hermitean operators ... generator of space translations. ...
    (sci.physics.research)