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}