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