```From: mark@microunity.com (Mark Johnson)
Newsgroups: sci.crypt,comp.periphials,sci.electronics

Subject: Applicable idea for Truly Random Number hardware
Message-ID:
Date: 25 Sep 91 13:36:14 GMT
References: <1991Sep20.131024.19997@lonex.rl.af.mil>
Sender: usenet@microunity.com (news)
Organization: MicroUnity Systems Engineering, Inc.
Lines: 112
Xref: cactus.org sci.crypt:4181 sci.electronics:17125
Nntp-Posting-Host: thalia

Suppose we have a sequence of bits, A = (a0, a1, a2, a3, ...).
It is produced by some physical process, for example a zener
diode or a Geiger-Muller tube.

Also suppose that the hardware is not perfectly "balanced"
(or "trimmed" or "optimized" or whatever word you prefer), so
that the sequence A doesn't contain equal numbers of ONES
and ZEROES.  (For example, the "zero crossing detector" is
actually a "+0.05 volt crossing detector" due to hardware
tolerances).

Suppose the probability that an element of A is a binary ONE
is equal to X --- P(ak == 1) = X , where (0 <= X <= 1) .

Now suppose that we create another sequence of bits
B = (b0, b1, b2, b3, ...).  Suppose that we construct B such
that P(bk == 1) = 1/2 ; that is, we know by the very design of B
it's equally likely that each element of B is a ONE or a ZERO.

Now, consider the new sequence C = A XOR B.  Each element ck of C
is just the XOR of the corresponding elements of A and B,
ck = ak XOR bk.

==> What is the probability that an element of C is a ONE? <==

Consider the truth table of the XOR function:

ak    bk  |  ck = ak XOR bk
------------+-----------------
0     0   |           0
0     1   |           1
1     0   |           1
1     1   |           0

For ck to be a ONE, we need (ak, bk) = (0,1) or else
(ak, bk) = (1,0).  Thus P(ck == 1) = P(0,1) + P(1,0).
Doing the algebra,

P(ck == 1) = (1-X)*(0.5)  + (X)*(1-0.5)
= 0.5 - 0.5X   + X - 0.5X
= 0.5

So the XOR sequence C has equi-distribution; an element ck
of C is equally likely to be a ONE or a ZERO.  Regardless of
the probability X that an element of A was a ONE. (!?).

-------------
-------------

Next, look at the case where B is not equi-distributed, but instead
the probability that an element of B is a binary ONE is equal to
Y --- P(bk == 1) = Y, where (0 <= Y <= 1) .

What's the probability that an element of C is a binary ONE?

P(ck == 1) = (1-X)*(Y)  + (X)*(1-Y)
= Y - XY     + X - XY
= X + Y - 2XY

Suppose sequences A and B come each from biased physical sources
such that X and Y are not exactly 0.50.  For example, X = Y = 0.6.
What happens when we XOR these sequences together?

P(ck == 1) = 0.48    ;    P(ck == 0) = 0.52

So the XOR of two biased sequences is less biased than either
of the originals. (?!).

What happens if we XOR together not two but *three* sequences,
each of whom has a non-equi-distribution?  Suppose that each
of the three sequences has P(sk == 1) = 0.6.  Then, grinding
out the math,

P( (XOR of three p=0.6 sequences) == 1 ) = 0.504.

So we are quickly converging to an equi-distributed, unbiased
sequence, one with p(sk == 1) = 1/2 , by XORing together several
biased sequences.

This idea was explored in a paper that appeared at "STOC":

Miklos Santha and Umesh V. Vasirani, "Generating Quasi-Random
Sequences from Slightly-Random Sources", 1984 IEEE Symposium on
the Theory of Computation, pp. 434-439.

The paper above is subtitled "(Extended Abstract)".  A later
version, which I myself have not seen, appears as

M. Santha and U. V. Vasirani, "Generating Quasi-Random Sequences
from Slightly-Random Sources", Journal of Computer Systems and
Sciences, Vol. 33, No. 1, August 1986, pp. 75-87.

------------
------------

Now suppose we take sequence A from a zener diode noise generator,
and sequence B from a maximal-length-shift-register generator using
a 32b shift register.

Because the shift register sequence is of length (2^N - 1) rather
than (2^N), sequence B is not perfectly equi-distributed.  The
probability that an element bk of sequence B is a binary ONE is
equal to (2147483648 / 4294967295), different from 0.5 by
(1 part in 1E9).

If we XOR sequence A with sequence B, we'll get an unbiased,
equi-distributed sequence C.  The probability that an element of
C is a binary ONE, will differ from 0.5 by less than (1 part in 1E9),
even if zener diode sequence A is badly skewed.
--
Mark Johnson       mark@microunity.com       (408) 734-8100
```