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}