Generating Quasi-Random Sequences From Slightly-Random .
Generating Quasi-Random Sequences from Slightly-Random Sources.(Extended Abstract)M i k l o s Santha’UmeshV. Vazirani“University of CaliforniaBerkeley, CA 94720.This source may be regarded as flipping a coinwhose bias depends on the current state of theMarkov process, and therefore depends on thesequence of bits previously output. Blurn showst h a t the obvious generalization of the von Neumann procedure does not work. He shows by a nelegant proof t h a t , surprisingly enough, changing the order in which the bits are output yieldsindependent, unbiased flips.We consider a n extremely general model ofan imperfect source of randomness. We shallassume t h a t the previous bits output by thesource can condition the next bit in an arbitrarily bad way. Accordingly, the model is t h a tthe next bit is output by t h e flip of a coin whosebias is fixed by an adversary who has completeknowledge of the history of the process. Tomake sure t h a t the source does generate somerandomness, the adversary is limited to pickinga bias greater than 6 and smaller than 1-6, forsome positive fraction O 6 1. This models theknown practical sources of randomness such ast h e zener diode, in which t h e frequency of 0’sand 1’s ”drifts” over a period of time [Mu]. Weshall call such an adversary source a slightlyrandom source.It can be shown t h a t no algorithm canextract a sequence of absolutely unbiased coinflips from such a n adversary source. Instead,we consider a different approach: we introducet h e notion of quasi-random sequences. TheseAbstract: Several applications require trulyrandom bit sequences, whereas physicalsources of randomness a r e a t best imperfect.We consider a general model for theseslightly -random sources (e.g. zener diodes),and show how t o convert their output into ‘random looking’ sequences, which we callquasi -random. We show that quasi-randomsequences a r e indistinguishable from truly random ones in a strong sense. This enables us t oprove t h a t quasi-random sequences can beused in place of truly random ones for applications such a s seeds for pseudo-random numbergenerators, randomizing algorithms, and stochastic simulation experiments.1. Introduction.The existence of a source of fair coin flipshas been extensively assumed for applicationssuch as randomizing algorithms [Ra], cryptographic protocols [Bll, GM] and stochasticsimulation experiments [Sc, KG]. Unfortunately, t h e available sources of randomness(e.g. zener diodes) are imperfect. The simplestmodel of a n imperfect source of randomness isa coin whose bias is unknown, but fixed. VonNeumann [vN] proposed a very simple real timealgorithm t o extract unbiased flips from such asource. More recently, Blum [ B E ] considers thequestion when the imperfect random source isa deterministic finite s t a t e Markov process.sequences may not b e truly independent o runbiased, but will be provably indistinguishablefrom truly random sequences in a very strongsense (even stronger than t h a t of Yao [Ya]). A sa consequence of this indistinguishability, it will*Supported by NSF Grant MCS 82-04506, and by the Pompeo Fellowship.CCSupported by NSF Grant MCS 82-04506, and by theIBM Doctoral Fellowship.4340272-5428/84/0000/0434 01.00@1984 IEEE
follow that truly random sequences can beDefinition: A quusi-random generator is asource such that for every t 0, for nsufficiently large, and for every functional statistical test f : I,uf(n) - ,u;(n)I / n t .The notion of a functional statistical t e s t isa strengthening of the concept of probabilisticpolynomial time statistical t e s t , introduced byYao [Ya]. Instead of evaluating a pseudorandom number generator on a few statisticaltests (as was done in practice), Yao proposedt h a t a pseudo-random number generator is"perfect" if it passes all probabilistic polynomial time statistical tests.An obviousdifference between Yao's statisticai tests, andour functional statistical t e s t s is that the function f need not be efficiently computable; itneed not be computable a t all. A morefundamental difference between these twonotions arises from the fact that whereas theprobabilistic polynomial statistical test is acomplexity theoretic notion, t h e functional statistical t e s t is an information theoretic notion.For this reason, Yao's definition of a perfectpseudo-random number generator is not uniform: a pseudo-random number generator isperfect if for any specified level of security1f n t and any proba.bilistic polynomial time statistical test there is some seed length n whichensures this security. In general this value ndepends on t h e statistical t e s t , and no finitevalue n will ensure this level of security withrespect to all statistical tests. On the otherhand quasi-randomness is a uniform concept:for any desired level of security, a length n canbe picked so t h a t the n-length quasi randomsequences achieve this security relative toevery functional statistical test.The following Pwo theorems illustrate howthe strong properties of quasi-random generators allow them to replace truly randomsequences. The first theorem shows thatquasi-random sequences are just a s "good" astruly random sequences when fed as seeds topseudo-random nuniber generators.replaced by quasi-random sequences in all theusual computational applications of randomsequences. A s an example, we shall prove t h a tquasi-random sequences can be used instead oftruly random coin flips t o generate randomvariates for stochastic simulation experiments.The advantage of considering quasi-randomsequences is that they can be generated byslightly-random sources of the type describedabove, which closely model actual physical devices.We show how to extract n bit quasi-randomsequences from O(lognlog*n) such semirandom sources operating in parallel: the algorithm is efficient and uses no storage. Moreover, i t is a real-time algorithm in the sensethat it generates one quasi-random bit a t eachstep. We also prove t h a t our method of generation achieves optimal compression factor.Why is it necessary to consider (imperfect)physical sources of randomness in light of thetheory of perfect (cryptographically secure)pseudo-random number generators [Sh, BM,Ya]. Blum [Bl] points out that there is a fundamental problem t h a t this theory leavesunsolved: t h a t is the source for the randomseed. Using a fair source t o generate this seedmay be crucial because of the danger t h a t thepseudo-randomnumbergeneratormightamplify any dependence or bias in t h e bits ofthe seed. A s another example of the versatilityof quasi-random sequences, we shall prove thatthey can be used as seeds for perfect pseudorandom number generators, without weakeningthe cryptographic security of the generator.2. Quasi-Randomness.Definition: A functional statistical test is anyfunction f: I O , l j * [ O , l ] , where [0,1] denotes t h eunit interval.We are given a source which for everylength n, generates n-length strings x E 10,ljnwith some probability p , (x) .Let , u f ( n ) l / 2 "--A probabilistic polynomial time statisticalt e s t is a function from g O , l { * to i O , l { , which iscomputed by a probabilistic polynomial timeTuring machine. A pseudo-random number generator passes a probabilistic polynomial timestatistical t e s t if for every t O , for n sufficientlylarge, the average value of the t e s t (function)on n-length pseudo-random strings differs byno more than l / n ' ! from the average value ofthe t e s t on truly random strings.f (z), be t h e averageIzI nvalue of f on random n-length strings.Let ,u;(n) C p , ( s ) f ( z ) , be t h e average121 71value of f on n-length strings generated by thesource.43 5
generated by a quasi-random generator. Leta,* I ( y ) - q ( I.y ) Then Ia,-a,* 1 I / n t ,Theorem 1: Let G: l O , l ] *I O * l j * be a perfectpseudo-random number generator. Then G withseeds generated by a quasi-random source isalso perfect (passes all probabilistic polynomialtime statistical tests).YEZfor every t, for sufficiently large n.Comrnen't: The above theorem can be used toget effective bounds: given a bound one cancompute n so that the error (the area betweenthe two density plots) introduced by substituting quasi-random sequences for truly randomones is less than the bound. This value of n, isguaranteed to work regardless of the algorithmused for generating the random variates,because of the uniformity property. The factthat functional statistical tests in the definitionof quasi-randomness are not required to bepolynomial time tests is also very important inthis theorem. This is because the running timeof algorithms for producing some distributionshas not been analyzed, and may well be superpolynomial.Proof: The basic idea of the proof is: suppose tothe contrary that the generator when fedquasi-random seeds fails a probabilistic polynomial time statistical test T; then the quasirandom number generator fails the functionalstatistical test obtained by composing thepseudo-random number generator with the testT.More formally: Let T: f O , l ] * 4 l 0 , l j be anyprobabilistic polynomial time statistical test,and t O fixed. Suppose that G on n-length seedsgenerates poly(n)-length sequences or somepolynomial poly (n).Recall thatP , T G ( )l/Zn12Now, I P Tbecause@ /( ))-PX( )GI ,T ( G ( z ) ).I a(l/nt)isperfect,I p ( n ) - p u ; I' ( On () l / n t )becausesource is quasi-random.I t follows thatIPTcpo2Ytn))-P;G(4I andouro w n t )*Since this is true for each test T, and every t 0, it follows that the pseudo-random numbergenerator with quasi-random seeds is perfect.Q.E.D. O( 1/ n t ) O( 1/ n t )Next, we show that quasi-random sequencescan be used in place of sequences of coin flipsby any procedure that generates (random variates of) a desired distribution T from asequence of coin flips. Let f : { O , l { * Z, the setof integers. Given a probability distribution Pron l0,ljn,f induces a probability distributionon Z in a natural way as follows:R ( Z )Let. T be the desiredp,(y) O ( l / n t ) for every t 0.lz I n,1(2) ydistribution. A s a measure of the closeness withwhich T is approximated by the distributioninducedbythefunctionf,leta, 2 I T ( Y )-pn (y ) 1 . Intuitively, an measuresY 2t 0.the area between the density plots of the twodistributions.Theorem 2: Let f be any function as above; letp , be the probability density induced by f whenall n length strings are picked with uniformprobability, and let qn be the probability density induced by f when the n length strings are436
3. Extracting Quasi-random Sequencesfrom Semi-random Sources.Now the task of extracting quasi-randomsequences from O(logn1og'n) slightly-randomsources is reduced to constructing the highquality source described above. Each of theO(logn1og'n) slightly-random sources has itsown adversary who picks the bias of the nextflip. Once again each adversary has completeknowledge of the previous coin flips. We shalluse the "unbiasing' property of the parity (xor)function. This property has been veryeffectively exploited in the past by Yao [Ya] toconstruct a perfect pseudo-random numbergenerator, from any one way function. Thealgorithm QGEN be low converts slightly-randomsources into a high quality source. In the nextsection, we shall prove that the choice of theparity function in the algorithm QGEN isoptimal.Recall that a slightly-random s o u r c e is aprocess which generates sequences of 0's and1's from the flips of a biased coin, where thebias of the coin is determined by an adversary.We now describe the basic principle underlying the generation of quasi-random stringsdespite the presence of an adversary. Considerthe following "high-quality"source: Thesequences of length n are generated by a coinC, whose bias can be slightly changed aftereach flip, with the constraint that the bias mustbe greater than 1 / 2 - & ( n ) and less than1 / 2 & ( n ) . Before each flip of this coin, anadversary, who has knowledge of the history ofthe coin flips sets the bias of the coin. The purpose of the adversary is to create as muchdependence in the distribution of flipsequences as possible. We would like to showthat if ( nis )a sufficiently small function of n,then this source is quasi-random.Algorithm QGEN:Input: m sequences of bits, each of length n.Theorem 3: If for every t and for all sufficientlylarge n &(n) l / n t , then the source definedabove is quasi random.output: y y 1 , . . . ,y,Begin:for i l to n do:Proof: For any n-length string x x . . . x,, forevery i, I s i r n , let Pr(xiIxl . . xi-t2 denote theconditional probability that the i coin flip isxi, when the result of the first i-1 coin flips isx i * . . xi-,. Then the probability that thesource generates x is:-yi : parity ( X l i Consider the following source: For each n,n-length sequences are generated by feedingn-bit outputs of 6'-'lognlog*n slightly-randomsources to QGEN. QGEN converts these inputsinto an n-length sequence.Theorem 4: The source defined above is quasirandom.Proof: We show that this source is "high quality"and therefore by Theorem 3 it is quasi-random.More precisely we show that if m slightlyrandom sources were used, then each bit output by QGEN has bias in the range[I/ 2-( 1-26)m, I/ 2 ( 1 - 2 6 ) ] : i.e.I P r ( Y i o l Y , , , . ,:Yi-l u)- P r ( y i l Iyl, . . . , yi-l u) I ( 1 - 2 d e I t ) .We introduce the following notation, forl k lognlog*n :(1/2n-P,(z))f(s)I1zI nc xmi)endforFor any functional statistical test f:s.10,ljnEnd.p,(z) P r ( x , I " l . . X n - l ) X . ' ' xPr(z,Ix,)Pr(x,).Since each successive bit is generated by theflip of a coin whose bias is between 1 / 2 - ( nand)1/2 (n):(1/ 2-&(n))n 5 p,(x) I; (1/ 2 &(?2)),.IPf(n)-P;(n)l IE11/2n-Pn(2)112 ( nI2 ((1/2 &(n))n--l/2")' (1 2&(n))n-l.We are done by the following elementary calculation:(1 2&(?2))"--1 2 n & ( n ) o( n e ( n ) )rk .i P r ( X , i . . . " o l y l. . yi-l'u)sk,i fi(%, , . xk l Iy1 ' . . y(-l u) .We prove by induction on k, that O ( l / n t ) for e v e r y t 0.Q.E.D.ITk,i--!Sk,*431I (1-26)k .,
Theorem 5: Let f : l O , l j m lO,l] be any booleanfunction. Then there are strategies for madversaries such that the bias of f(s, . . . sl)differs atleast ( 1 - 2 l ) from 1/2, where si is abit generated by the ith source.The basis step of the induction follows directlyfrom the definition of a semi-random source. Toprove the induction step, letyi-l U) pB(zk i o)y1' ''B ( z k 1 i 1 Iy1 '"yi-l u)' 8tProof: By induction on the number of sources.The basis follows from the definition of aslightly-random source. For the inductive step,fix the output of the lSt source to be 0. Then bythe inductive assumption, the other m-1 adversaries have strategies which force the bias of frestricted to s 1 0, to be bounded atleast( 1-26)m-1 away from 1/2. Let po(0)be the probability that f restricted to s 1 is 0, and p o ( l )the probability that it is 1. We assume withoutloss of generality that the inductively assumedstrategies for the m-1 adversaries yield:po(0)-po(l) A 2 (1-26)m-1. Fix these strategies for the m-1 adversaries.Case 1 : For f resticted to s 1,p ,(O) A 2 p 1). In this case the first adversary chooses bias 1-6 towards 0. Then Pr[O] Pr[ 11 ( 1 - 6 ) A - 6 A (1-26)A2 ( 1-26)m *6 p , q 1-6,because the bias of the k l t hcoin is between 6 and 1-6. Moreover xk 1 isindependent from zli, . . . , zki, because theinput sequences are generated by parallelsources. A simple consideration shows thatrkfl,i'k l,i rk ,i'P 'k ,i'q'k,i'P r k , i ' q7.ThenIrk l,i-sk l,iII I(Tk,i-Sk,i)(iD-q) ( 1-26)k ( 1-26) (1-26)k l,This completes the induction.Finally, substituting any function that growsfaster than logn asymptotically (we chooselognlog'n) for k, we get Case 2: p , ( O ) p , ( l ) A . In this case the firstadversary chooses bias 1-6 towards 1. ThenPr[ 11 - Pr[O] 2 (1-6)A - 6 A (1-26)A2 (1-26)m.o(l/n?) for every t Q.E.D.Q.E.D.I t is somewhat surprising that the bound ofTheorem 5 is exactly the same as the boundproved in Theorem 4. This directly yields:4. Lowerbounds, or t h e Power of t h eAdversary.Corollary: the parity function achieves themost efficient conversion of slightly-randomsource outputs into quasi-random sequences.We prove below that the choice of the parityfunction in the algorithm QGEN of Section 3 isoptimal. The model is that any algorithm mustlook a t a fixed size block of slightly-random bitsto produce one quasi-random bit. Thus anysuch algorithm is in general a boolean functionmapping m bits into 1 bit. We prove below thatm must grow faster than logn asymptotically toachieve quasi-randomness. Clearly, it sufficest o consider the (hardest) case when the mslightly-random bits are outputs of m distinctslightly-random sources.Finally, we show that that there is no algorithm to convert the output of a single slightlyrandom source into quasi-random sequences,no matter how much bit-compression isallowed. Let f: t0,lj" -,l 0 , l ) be any booleanfunction. Intuitively, f tries to compress m bitsof the source output into one quasi-random bit.We prove that far every f , there is an adversarystrategy so that the bias of the extracted bit is1 - 6 towards 1, thus showing that the extractedbit is just a s bad as any bit in the originalsource output.The function f , may be represented in acomplete binary tree of height m as follows: thetwo branches from each node are labelled 0 and1. Each path from root to leaf then corresponds438
to a unique binary string of length m. Thevalue of f on a string is assigned t o thecorresponding leaf in the tree. An adversarystrategy for the slightly-random source consists of labelling for each node of the tree: the1-branch with a bias b between 6 and 1 - 6, andthe corresponding 0-branch 1 - b. The probability of picking any root-leaf path in the tree issimply the product of the biases on the edges.Define the weight of a subtree be thenumber of 1-leaves in it. Assume without lossof generality t h a t f(x) 1 for atleast 112 fraction of the strings of length m. The followingadversary strategy guarantees that the probability of reaching a 1-leaf (i.e. f(x) 1) isatleast 1-6: for each node, label the branchleading t o the heavier subtree with bias 1 - 6.The proof goes by induction on the height, m, ofthe tree. Consider a subtree of height k , rootedat A. Let a denote the number of 1-leaves in thesubtree. Then a is either 2k or a k bit numberakak-, . * . a l . Let o ( i ) denote the number of1's in the prefix ak . . . q ,.Then we associatea valuet v(a), with the subtree:5. Acknowledgements:We are extremely iindebted to Manuel Blum, notonly for raising the issues that sparked off thisresearch, but also for his ability to detect verysubtle flaws in "proofs". Vijay Vazirani played acritical role in helping us clarify several conceptual points. Sampath Kannan was a catalystfor the lower bound proofs. W e wish t o thankthem and Ashok C'handra, Richard Karp, DexterKozen, Steven Rudith, Michael Sipser & AviWigderson for some very useful discussions.6. References.[Bll][B12]M. Blum, "Coin Flipping by Telephone,"IEEE COMPCON (1982).M. Blum, "Independent Unbiased CoinFlips From a Correlated Biased Source:a Finite State Markov Chain," to appear.[BBS] L. Blum, M. Blum and M. Shub, "A Simple Secure Pseudo-Random NumberGenerator," t o appear in SIAM Journal ofComputing.M. Blum and S . Micali, "HOWt o GenerateCryptographically Strong Sequences ofPseudo-Random Bits," 1982 FOCS.S.Goldwasser and S.Micali, "Probabilistic Encryption and How to Play MentalPoker Keeping Secret all Partial Information," 1982 STOC.W. Kennedy and J. Gentle, S t a t i s t i c a lC o m p u t i n g , Marcel Dekker, Inc. NewYork.D. Knuth, The A r t of C o m p u t e r P r o g r a m m i n g , Volzlime 2: S e m i n u m e r i c a l Algor i t h m s , Addison-Wesley, Reading, MA(second edition 1981).J. von Neumann, 'Various TechniquesUsed in Connection with RandomDigit
A probabilistic polynomial time statistical test is a function from gO,l{* to iO,l{, which is computed by a probabilistic polynomial time Turing machine. A pseudo-random number gen- erator passes a probabilistic polynomial time statistical test if for every t O, for n sufficiently large, the average value of the test (function)
9.2 Generating a random number from a given interval 285 9.3 The generate and test paradigm 287 9.4 Generating a random prime 292 9.5 Generating a random non-increasing sequence 295 9.6 Generating a random factored number 298 9.7 Some complexity theory 302 9.8 Notes 304 10 Probabilistic primality testing 306 10.1 Trial division 306
Start by finding out how Python generates random numbers. Type ?random to find out about scipy's random number generators. Try typing 'random.random()' a few times. Try calling it with an integer argument. Use 'hist' (really pylab.hist) to make a histogram of 1000 numbers generated by random.random. Is th
Start by finding out how Python generates random numbers. Type ?random to find out about scipy's random number generators. Try typing 'random.random()' a few times. Try calling it with an integer argument. Use 'hist' (really pylab.hist) to make a histogram of 1000 numbers generated by random.random. Is the distribution Gaussian, uniform, or .
producing random digits is, of course, in a state of sin.” [J. von Neumann, 1951] Sinful pleasures. “If the numbers are not random, they are at least higgledy-piggledy.” [G. Marsaglia, 1984] Does it look random enough to you? “Random numbers should not be generated with a method chosen at random.
Generating U(0,1) Random Variables They are usually the building block for generating other random variables. We will look at: –Properties that a random number generator should possess –Linear Congruential Generators (LCGs) –Use Matl
7.3 Rejection Method: Gamma, Poisson, Binomial Deviates 281 7.4 Generation of Random Bits 287 7.5 Random Sequences Based on Data Encryption 290 7.6 Simple Monte Carlo Integration 295 7.7 Quasi- (that is, Sub-) Random Sequences 299 7.8 Adaptive and Recursive M
Generating Random Variables and Stochastic Processes 4 The Inverse Transform Method for Continuous Random Variables Suppose now that Xis a continuous random variable and we want to generate a value of X. Recall that when Xwas discrete, we could generate a variate by rst generating Uand then setting X x j if F(x j 1) U F(x j). This suggests .
par catégorie alimentaire. A partir des informations disponibles dans les listes d’ingrédients, il est parfois délicat pour un même libellé d’ingrédient de différencier son utilisation en tant qu’additif ou en tant que substance à usage d’enrichissement (exemple : acide ascorbique). Pour ce rapport et pour ces substances, il a été décidé, par convention (choisie), de .
