Subject: Refutation of Santha-Vazirani random number paper?
From: mark@mips.COM (Mark G. Johnson @ MIPS Computer Systems)
Can someone please enlighten a rank novice?  Have the ideas in the
following paper withstood the test of time -- or, perhaps, have they
been discredited and/or supplanted by new methods?

Miklos Santha and Umesh V. Vazirani, "Generating Quasi-Random Sequences
from Slightly-Random Sources", IEEE Symposium on the Foundations of
Computer Science, Volume 25, pp. 434-440, 1984.

from the Abstract:
   "... these Slightly-Random sources (e.g. zener diodes) and show
    how to convert their output into 'random-looking' sequences,
    which we call Quasi-Random.  We show that quasi-random sequences
    are indistinguishable from truly random ones in a strong sense."


My (admittedly ignorant) reading of the paper leads me to consider
using these ideas as the basis for a very inexpensive, rather secure
random number generator implementation in hardware.  Uses would include
creation of CD-ROMs full of random bits ("one time pads"), randomised
selectors for one-to-many homophonic substitution ciphers, etc.

The Santha/Vazirani scheme could be realized using  N  "Slightly Random
sources" derived from fundamentally different physical mechanisms, such as

      1.  Zener diode
      2.  Chaotic oscillator such as the one whose schematic is given
            in IEEE Trans Ckts and Systems, vol CAS-30, Sept 83, p. 620.
      3.  Radio reception at an "unused" frequency
      4.  Unijunction transistor
      etc.

If care were taken, e.g. separate power supply regulators, star grounding
networks, physical shielding, and so forth, these would appear to meet
the S/V requirements for input "Slightly Random" sequences.  Perhaps
even k>1 instances of each type of source could be used, for example
6 different zeners + 3 oscillators + 4 UJTs, etc.

Question for knowledgable theoreticians: Is this all wet?

Thanks in advance for any and all replies; either email or news
article follow-up very much appreciated.
-- 
 -- 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}