Subject: re: What the hell did Santha-Vazirani paper actually say?
From: mark@mips.COM (Mark G. Johnson @ MIPS Computer Systems, Inc.)
I was the poster of the basenote article.  A number of people asked
for a little more data about the S-V paper.  Please excuse the lack
of italics and Greek letters.

from the Introduction:
"We consider an extremely general model of an imperfect source of
randomness.  We shall assume that the previous bits output by the
source can condition the next bit in an arbitrarily bad way.
Accordingly, the model is that the next bit is output by the flip
of a coin whose bias is fixed by an Adversary who has Complete
Knowledge of the history of the process.  To make sure the source
does generate some randomness, the adversary is limited to picking
a bias greater than DELTA and smaller than 1 - DELTA, for some
positive fraction 0 < DELTA < 1.  This models the known practical
sources of randomness such as the zener diode, in which the
frequency of 0's and 1's "drifts" over a period of time.  We shall
call such an adversary source a Slightly-Random Source."
...
"Why is it necessary to consider (imperfect) physical sources of
randomness in lightof the theory of perfect (cryptographically
secure) pseudo-random number generators?  Blum points out that
there is a fundamental problem that this theory leaves unsolved:
that is the source of the random seed.  Using a fair source to
generate this seed may be crucial because of the danger that
the pseudo-random number generator might amplify any dependence or
bias in the bits of the seed.  As another example of the versatility
of quasi-random sequences, we shall prove that they can be used as
seeds for perfect pseudo-random number generators, without weakening
the cryptographic security of the generator?
...
"THEOREM 1:   Let  G: {0,1}* --> {0,1}*   be a perfect pseudo-random
number generator.  Then G with seeds generated by a quasi-random
source is also perfect (passes all probalistic polynomial time
statistical tests)."

The Santha-Vazirani idea is simplicity itself.  First, you obtain  m
Slightly-Random sources of bits (e.g. Zener diodes, at&t noise chips,
etc.).  Then you feed their outputs into an m-input XOR [also known
as a parity tree], such as the TTL part 74F180:

Algorithm QGEN:
Input:  m sequences of bits, each of length n
x[1][1], x[1][2], ..., x[1][n]
x[k][1], x[k][2], ..., x[k][n]
x[m][1], x[m][2], ..., x[m][n]

Output:  a sequence of bits  y[1], y[2], ..., y[n]

Begin:   for i = 1 to n do:
y[i] = parity( x[1][i]  +  x[2][i]  +  ...  +  x[m][i] )
endfor
End.

mj remark:  y[i] is just the LSB of the addition of  m  1-bit quantities.
Which is easily computed by an  m-input XOR tree.

So, bottom line:  Get m>>1 zener diode "slightly random bit generators".
XOR their outputs together.  XOR that with a square wave having 50.00%
duty cycle.  Done.

Lemma 2:    The output bits will be 50.00% zeroes and 50.00% ones, even
if this isn't true of any of the individual zener sources.
Proof:      Left as an exercise to the reader.
--
-- Mark Johnson
MIPS Computer Systems, 930 E. Arques M/S 2-02, Sunnyvale, CA 94086
(408) 524-8308    mark@mips.com  {or ...!decwrl!mips!mark}