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}