How to Privatize Random Bits Marius Zimand The University of Rochester Computer Science Department Rochester, New York 14627 Technical Report 616 Abstract The paper investigates the extent to which a public source of random bits can be used to obtain private random bits that can be safely used in cryptographic protocols. We consider two cases: (a) the case in which the part privatizing random bits is computationally more powerful than the adversary, and (b) the case in which the part privatizing random bits has a small number of private random bits. The rst case corresponds to randomized hard functions and the second variant corresponds to randomized pseudo-random generators. We show the existence of strong randomized hard functions and pseudo-random generators. As a side eect, it is shown that relative to a random oracle P=poly is not measurable in EXP in the resource-bounded theoretical sense and a very strong separation between sublinear time and AC 0 is obtained. Keywords: one-way function, pseudo-random generator, hard function. Supported 9322513. in part by grant NSF-CCR-8957604, NSF-INT-9116781/JSPS-ENG-207 and NSF-CCR- 1 Introduction It is commonly accepted that random bits are a valuable computational resource. Unfortunately, random bits are hard and expensive to produce. Generating them by special-purpose devices such as Geiger counters or Zener diodes is slow and the outcomes must still be further processed (see [SV86] and [Blu84]). One solution to reduce the costs of getting good random bits is to share the random source. We can think of a scenario where there is a public server which provides random bits to anyone requesting them. It is conceivable that this is more practical than connecting a Geiger counter to your PC. However, in some cryptographic protocols one needs private random bits such that the adversary has no means to predict them. Consider for example the perfect encryption system, one-time pad, that was invented in 1917 by Major Joseph Mauborgne and AT & T's Gilbert Vernam [Kah67]. In this system both the sender and the receiver have a common key consisting of a long string of random bits, called the one-time pad. Encryption is done by XORing bitwise the message with the one-time pad and decryption is done by XORing the ciphertext with the one-time pad. While the system is provably resistant to any cryptanalysis attack, it has the drawback of requiring a key that is as long as the message and this creates big problems with keys generation and distribution. These problems would disappear if there was a public server distributing random one-time pads from which the sender and the receiver could extract strings that look random to any adversary of some computational power. Thus the problem reduces to obtaining private random bits out of a public source and this is the question that we investigate here. Clearly the part (\we") that wants to obtain private random bits must have some advantage over the adversary (\they"), as otherwise \they" could simply reproduce the operations performed by \us". We consider two types of advantages. In the rst variant, \we" are computationally more powerful than \they". This corresponds to designing a hard function f for size (n), i :e :, a boolean function such that the probability that any adversary circuit of size (n) correctly computes f is very close to 1=2. This must hold with high probability over the choices of public random bits that are available to both the device computing f and to the adversaries. We show that for every > and n (n) 2n , with < 1, there is such an f computable in time O(max((n)3+ n log log n; n5)). The function f outputs a single private random bit, but we observe that it can be used to obtain a linear number of such bits. The second type of advantage is that \we" possess a small number of private random bits. This corresponds to a pseudo-random generator, i :e :, a function f that takes as input a small number of random bits (which in our context are private) and produces a larger number of bits that look random to the adversary. Again this must hold with high probability over the choices of public random bits. We show that there exists such a randomized pseudo-random generator that uses nO(1) private random bits, 2O(n) public random bits and produces up to 2O(n) bits that are not distinguishable with a bias better than 2? (n) by any adversary circuit of size 2an for some positive constant a. Moreover, every bit of the output is produced in nO(1) time. This holds with probability over the choices of public random bits larger than 1 ? 2?q(n) for any polynomial q . The construction is done by transforming a function built by Impagliazzo [Imp96], which is strongly one1 way with respect to a random oracle and is safe against non-uniform adversaries, into a randomized pseudo-random generator. Impagliazzo demonstrated the existence of such a randomized pseudo-random generator using the general result of Hastad, Impagliazzo, Levin and Luby [HILL91] that shows that the existence of one-way functions is equivalent to the existence of pseudo-random generators. As we are interested here in eective methods for privatizing random bits, we present a complete construction that, taking advantage of some features of the one-way function in [Imp96] is somewhat simpler than the construction implied by [HILL91]. The concepts and the proofs in this work are inspired by probability one relativizations. The existence of pseudo-random generators and one-way functions without the support of a random source is related to some open questions in computational complexity theory which are beyond reach given the \current state of the art." For example, the existence of one-way functions immediately implies P 6= NP (though the converse is open). However, we do know that PA 6= NPA for a random oracle A. This suggests that one could show the existence of randomized one-way functions and the other concepts without any complexity-theoretic assumption and this is basically what we do in this work. The results of this type are explicitly stated in Section 5. Thus we show the existence of hard functions with respect to a random oracle. We also investigate the relation between sets decidable in exponential time (EXP ) and sets accepted by polynomial-size circuits (P=poly ) in worlds relativized with random oracles. It is known from the work of Lutz and Schmidt [LS93] that, relative to a random oracle A, EXP A is not included in PA =poly (actually their result is stronger in many aspects). Such questions can be investigated more deeply using the apparatus of resource-bounded measure theory. Lutz has shown in [Lut92] that sets that are accepted by circuits of size bounded by nk for a xed k have measure 0 in EXP . However, nothing is known about the measure of P=poly in EXP . Using a result of Regan, Sivakumar and Cai [RSC95a] and a randomized pseudo-random generator, we show that with respect to a random oracle A, PA =poly does not have measure 0 or 1 in EXP A . An analogue result concerning the measure of NP in EXP has been obtained by Kautz and Miltersen [KM94]. Moreover, by employing a similar counting strategy as the one used in the construction of the randomized hard function, we establish a strong separation from sub-linear time. Machines working in sub-linear time are dened by allowing random access to the readonly input tape and yield quite respectable complexity classes. For example, Allender and Strauss [AS94] consider machines that work in O(log n) time in order to dene a meaningful notion of measure inside P. More relevant to our result, Barrington, Immerman and Straubing [BIS90] argue convincingly that machines running in O(log n) time yield the proper, robust, notion of uniformity for polynomial-size, constant-depth circuits (i :e :, AC0 circuits). The general idea is that the machine describing the AC0 circuit should have less power than the circuit itself as otherwise the circuits could potentially benet from the computation of the machine that describes it. But how does DTIME [O(log n)] relate to AC0? After all, AC0 is a very weak class itself and it is known from the work of Ajtai [Ajt83] that the languages in AC0 are in a large proportion (of strings at each suciently large length n) constant on proper cylinders partitioning the domain (i :e :, n) and, thus, a machine could, in principle, approximate them without reading the whole input. However, we show that machines running in sub-linear time cannot approximate AC0. More exactly, for each 2 2 (0; 1), we exhibit a very simple predicate f that can be computed by linear-size depth-2 monotone circuits such that if M is a machine running in n time, then for all suciently large n, j Probx2n (f (x) = M (x)) ? 1=2 j n? (1) . The notation is standard: is the set of nite binary strings and n is the set of binary strings of length n; if x 2 , then jxj is the length of string x; x(i) denotes the i-th bit of x; if S is a set, then jS j is the cardinality of S ; and, nally, if y is a real number, then jyj is the modulus of y . All probabilities are with respect to the uniform distribution or with respect to the Lebesgue measure in the case of probabilities over sets of oracles. 2 Formal Framework The access to a public source of random bits is formalized by using functional oracles. That is the machine computing the hard function or the pseudo-random generator is an oracle machine and we stipulate that the oracle is a function R such that if x is on the query tape and the machine enters a query state, then R(x) is immediately provided on some specially designated answer tape. This models both the situation when the request to the public-server is done on-line and the situation in which the random bits are transferred in a precomputation phase and stored, say, on the hard-disk. The function R consists in fact of a family of functions (Rn)n 2 N, where Rn : i(n) ! m(n) . We stipulate that the machine computing the cryptographic primitive asks on inputs of length n only queries of length i(n). The probabilistic space on inputs of length n is denoted by Rn and consists of the set of all functions Rn as above and the uniform distribution on this set (note that i(n) and m(n) are the same for all functions in Rn). Such a function Rn can be encoded in 2i(n)m(n) bits, and if the oracle machine M works with Rn as its oracle on inputs of length n, we say that M uses 2i(n) m(n) public random bits. 3 Randomized hard function Intuitively, a hard function is a function that cannot be approximated by a circuit of reasonable large size on a fraction of the inputs that is signicantly dierent than 1/2. Formally, a function f : n ! f0; 1g has hardness ((n); (n)) if for any circuit C of size (n), j Probx2n (C (x) = f (x)) ? 1=2 j (n): We dene the notion of a randomized hard function by requiring that the above relation holds with high probability. Denition 3.1 Let ; ; : N ! R, M be an oracle machine, and fR be the function computed by the machine M with oracle R. The function computed by M is a randomized hard function that has hardness (; ) with probability if (a) fR is 0-1 valued for all R, and (b) with probability of R in Rn at least (n), it holds that for any family C = (Cn )n2N of oracle circuits of size (n) and for n 2 N suciently large, n R j j fx 2 : Cn2n(x) = fR (x) gj ? 12 j (n) : 3 If (n) = 2? (n) , (n) = 1 ? 2? ((n)) , then the randomized hard function is said to be strong for size (n). CnR denotes the fact that the oracle circuit Cn runs with function R as the function oracle (i:e:, if the input bits at an oracle gate form the string x, then the string R(x) is produced as the output bits of the oracle gate). Theorem 3.2 For any > 0 and any size (n) verifying n (n) 2n, for some < 1, there exists a randomized hard functions that is hard for size (n) and is computable in time O(max((n)3+ n log log n; n5 )). Proof. The normal approach is to associate to each string x in n a random string rx of length 2n (n) + 1 and to let the hard function fR , on input x, output the parity of rx. Then an adversary C of size (n) cannot access all the bits of rx during the computations that take as inputs all the strings in n . Therefore, the events \C R (xi) = fR (xi)" (where xi is the i-th string in n) have probability of success 1/2 and are independent and one can use the Cherno's bounds. The problem is that for small (n), fR spends time (2n) which is disproportionately large compared with the size of the adversary. The solution is to follow the above scheme but to let the random rx have only limited independence. For simplicity, let s denote (n) and let m = 2 ds1+ e, for some positive that will be specied later. Also, let t = ms + 1. Rn consists of all functions R : dlog te ! mn . For each y in dlog te , we decompose R(y ) into m strings of length n, a0 ; : : :; am?1 (i :e :, R(y ) = a0 : : :am?1 ) and we associate to y the function h(x) = am?1 xm?1 + am?2 xm?2 + : : : + a0, where the computations are in the nite eld GF (2n ). There are at least t such functions h1; h2; : : :; ht, where hi is the function associated as above to the i-th string in dlog te . As it is well-known (see, for example, [Koz91, pag. 200]), for each i 2 f1; : : :; tg, the following facts hold true: (a) for each x; y 2 n , Prob(hi (x) = y ) = 2?n , and (b) the random variables fhi(x) : x 2 ng are m-wise independent. We now dene fR (x) = h1(x)(1) : : : ht(x)(1), i :e :, fR (x) is the parity of the string obtained by concatenating the rst bit of hi (x), i = 1; : : :; t. Let C be a xed oracle circuit of size at most s. Let Xi = 1, if C R(xi ) = fR(xi), and 0, otherwise, where xi is the i-th string in n . The following fact, whose proof we defer for the moment, holds: Fact 3.3 Let i1; i2; : : :; im 2 f1; : : :; 2ng and bi ; : : :; bim be xed bits. Then, Prob(Xi = bi j Xi = bi ^ : : : ^ Xim = bim ) = 1=2. 1 1 2 1 2 n Let X = 2i=1 Xi. Then the expected value of X is E [X ] = 2n =2. By Fact 3.3, the random variables (Xi )i=1;:::;2n are m-independent. Using the Cherno's bounds for 0-1 random variables with limited independence from [SSS93], we obtain that if m d 2 E [X ]e?1=3e, then Prob(jX ? E [X ]j E [X ]) e?bm=2c . We can pick (recall that m = 2 ds1+ e) and = 2?an such that m d 22n?1 e?1=3e. Then Prob(j 2Xn ? 21 j 2?an ) e?bm=2c : There are at most (4s2 )s oracle circuits of size s (by the usual convention, an oracle gate contributes with its indegree to the size of the circuit). Thus the probability that there exists an oracle circuit C of size s such that jProbx2n (C R(x) = fR (x)) ? 1=2j > 2?an is P 4 less than (4s2 )s e?bm=2c = 2?(log es ?2s log 2s) < 2?s . Finally, observe that computing fR (x) involves nding an irreducible of degree n over GF (2) and then t = ms + 1 evaluations of a polynomial of degree m ? 1 in GF (2n ) in a point x 2 n . Finding the irreducible polynomial requires O(n5) time (see [Sho88]) and the rest requires O((ms + 1)mn log n log n) time. It remains to prove Fact 3.3. 1+ Proof of Fact 3.3. We compute the probability that fR(xi ) = 0 conditioned by the events Xi = bi ^ : : : ^ Xim = bim and (C R(xi ) = b) for some xed bit b. For a set T = fj1 < j2 : : : < jk g, we denote by R(T ) the string R(yj ) : : :R(yjk ) and hT (x) = hj (x)(1) : : : hjk (x)(1). Let I = f1; : : :; tg. In what follows, we consider sets of strings Y = fyj ; : : :; yjms g dlog te of cardinality ms. Observe that the values of the random variables (Xi = bi ); : : :; (Xim = bim ) and (C R (xi ) = b) are determined by hI (xi ); : : :; hI (xim ) and by the values of R on the strings y that are queried during the computations of C R on inputs xi ; : : :; xim , and that there are at most ms such queried strings. 1 2 2 1 1 1 1 2 2 1 1 1 Let Z = f(Y; B1; : : :; Bm ) j jY j = ms ^ (R(Y ) = B1 ^ (hI ?Y (xi ) = B2 ) ^ : : : ^ (hI ?Y (xim ) = Bm ) ! (Xi = b1 ^ : : : ^ Xim = bim ^ C R (xi ) = b))g and let query R(x) denote the set of strings queried by C R on x. Then 2 1 1 Prob(fR(xi ) = 0 j (Xi = bi ) ^ (Xim = bim ) : : : ^ (C R (xi ) = b)) = 2 2 1 1 = Prob(hI (xi ) = 0 j (Xi = bi ) ^ (Xim = bim ) : : : ^ (C R(xi ) = b) = 2 1 = P 2 1 Prob(hI (xi ) = 0 j (query R(xi ) [ : : : [ query R (xim ) Y ) ^ (Y;B1 ;:::;Bm )2Z 1 1 ^ (R(Y ) = B1 ) ^ (hI ?Y (xi ) = B2) ^ : : : ^ (hI ?Y (xim ) = Bm ) 2 Prob(queryR(xi ) [ : : : [ queryR(xim ) Y) ^ (R(Y ) = B1) ^ 1 ^ (hI ?Y (xi ) = B2 ) ^ (hI ?Y (xim ) = Bm )j (Xi = bi ) ^ : : : 2 2 ^ (Xim = bim ) ^ (C R(xi ) = b)): 1 2 () For any xed (Y; B1; : : :; Bm ) 2 Z , we show that the corresponding term in the above sum is equal to 1=2 Prob(query R(xi ) [ : : : [ query R (xim ) Y) ^ (R(Y ) = B1 ) ^ ^ (hI ?Y (xi ) = B2) ^ (hI ?Y (xim ) = Bm )j (Xi = bi ) ^ : : : ^ (Xim = bim ) ^ (C R(xi ) = b)). This is 1 2 2 2 1 5 clearly true if the above probability is 0. Otherwise, Prob(hI (xi ) = 0 j (query R (xi ) [ : : : [ query R(xim ) Y ) ^ (R(Y ) = B1 ) ^ 1 1 ^ (hI ?Y (xi ) = B2) ^ : : : ^ (hI ?Y (xim ) = Bm)) = 2 = Prob(hI ?Y (xi ) = hY (xi ) j (query R(xi ) [ : : : [ query R (xim ) Y ) ^ (R(Y ) = B1 ) ^ 1 1 1 ^ (hI ?Y (xi ) = B2) ^ : : : ^ (hI ?Y (xim ) = Bm)) = 2 ( since R(Y ) and R(I ? Y ) are independent; B def = hY (xi ) for R(Y ) = B1 ) 1 = Prob(hI ?Y (xi ) = B j (hI ?Y (xi ) = B2 ) ^ : : : ^ (hI ?Y (xim ) = Bm )) = 1 2 ( by the m-wise independence of the hash functions ) = Prob(hI ?Y (xi ) = B ) = 1=2 (because I ? Y 6= ;):): Thus our claim holds. Going back to (*), we obtain that Prob(fR (xi ) = 0 j (Xi = bi ) ^ : : : ^ (Xim = bim ) ^ (C R (xi) = b2)) is equal to 1/2. Therefore, for b = 1 (the case b = 0 is similar) Prob(Xi = 1 j (Xi = bi ) ^ : : : ^ (Xim = bim )) = 1 1 2 2 2 1 2 = Prob(fR(xi ) = 0 j (Xi = bi ) ^ : : : ^ (Xim = bim ) ^ (C R(xi ) = 0)) 2 1 2 Prob(C R(xi) = 0 j (Xi = bi ) ^ ^ (Xim = bim ))+ 2 1 + Prob(fR (xi ) = 1 j (Xi = bi ) ^ : : : ^ (Xim = bim ) ^ (C R (xi) = 1)) 2 1 2 Prob(C R(xi ) = 1 j (Xi = bi ) ^ : : : ^ (Xim = bim )) = 1=2: 1 2 2 . The randomized hard functions in the above theorem satisfy the following Condition A for any size (n) with n (n) 2n , < 1, which implies some good independence properties of the values ffR (x); x 2 n g. Condition A for size (n): for any circuit C of size (n), for all suciently large n and all x 2 n , j ProbR2Rn (fR (x) = C R (x)) ? 1=2 j 2? (n) . The next proposition shows that the knowledge of cn values of the function fR on the domain n is not very helpful for the adversary to compute further values on the same domain. Proposition 3.4 Let fR be a strong randomized hard function having hardness (; ) with probability and satisfying Condition A for size (n). Let n = fx1 ; : : :; x2n g. There 6 exists a constant c > 0 such that for all sets I f1; : : :; 2ng with jI j cn and for all combinations of bits b1; : : :; b2n , bi 2 f0; 1g, if C is an oracle circuit of size (n), then j Probx2n;R2Rn (fR(x) = C R(x) j 8i 2 I (fR(xi) = bi)) ? 1=2 j 2? (n) . Proof. Let d > 0 be a constant such that fR has hardness (2?dn ; (n)) with probability 1 ? 2?dn and for all suciently large n and for all x 2 n , j ProbR2Rn (fR (x) = b) ? 1=2 j 2?dn+1 . We abbreviate 2?dn by (n) and take c to be a positive constant less than d. We focus on a suciently large n. Let I = fa1 ; : : :; ak g be an arbitrary subset of f1; : : :; 2ng with k cn. By induction on j , 0 j k, we show that if C is an oracle circuit of size (n) and b1; : : :; b2n are some arbitrary bits, then: j Probx;R(fR(x) = C R(x) j (8i j ) (fR(xai ) = bi)) ? 1=2 j 2j+1(n); (1) and ProbR (Sj+1) (1=2 ? (n))ji=1 (1=2 ? 2i+1 (n)); (2) where for each j 1, Sj = fR 2 Rn j (8i j )(fR(xai ) = bi )g and, by convention, the product ji=1 (1=2 ? 2i+1 (n)) is 1 for j = 0. Relation (1) clearly implies the conclusion we need. The relations are easily veried for j = 0. Consider now the induction step (j ? 1) ! j . For the sake of contradiction, suppose Probx;R(fR(x) = C R(x) j (8i j ) (fR(xai ) = bi)) > 1=2 + 2j+1 (n): (3) Let B = fR 2 Sj j Probx (fR (x) = C R (x)) 1=2 + (n)g and = ProbR(B j Sj ). Then, Probx;R(fR (x) = C R(x) j Sj ) (1 ? ) + (1=2 + (n)): So, 1=2 + 2j +1 (n) < (1 ? ) + (1=2 + (n)). It follows that j +1 (n) : < 1 ? (21=2 ?? 1) (n) Consequently, j +1 (n) ProbR (B j Sj ) > (21=2 ?? 1) (n) ; where B is the complement of B , and, thus, j +1 (n) Prob(S ): ProbR2Rn (Probx2n (fR (x) = C R(x)) > 1=2 + (n)) > (21=2 ?? 1) j (n) Using the induction hypothesis, ProbR(Probx2n (fR(x) = C R(x)) > 1=2 + (n)) > ?1(1=2 ? 2i+1 (n)) = (n)2?(j ?1) (2j +1 ? 1) j ?1 (1 ? 2i+2 (n)) > (2j+1 ? 1)(n)ji=1 i=1 ?1 2i+2 ) (n): (n)2?(j?1)(2j+1 ? 1)(1 ? (n) ji=1 7 This contradicts the hardness of fR and, thus, relation (3) is false. By taking the \complementary" circuit of C , we deduce that Probx;R(fR (x) 6= C R (x) j Sj ) 1=2 + 2j +1 (n) and (1) is proved. For (2), we note (using the induction hypothesis and relation 1 for j and the circuit which outputs bj+1 on all inputs) that Prob(Sj+1) = Prob(fR(xj+1 ) = ?1 (1=2 ? 2i+1(n)) = bj+1 j Sj )Prob(Sj ) (1=2 ? 2j+1 (n))(1=2 ? (n))ji=1 (1=2 ? (n))ji=1 (1=2 ? 2i+1 (n)). 4 Randomized pseudo-random generator We pass next to the second cryptographic primitive. A pseudo-random generator is a function f that maps short strings to longer strings such that any adversary of some signicant computational power cannot distinguish with a good bias between the uniform distribution on the set of long strings and the distribution induced by f when its input is uniform randomly selected in the set of short strings. Thus the function f takes as input short random strings and outputs long strings that look random to the adversary (for concreteness, we require that f doubles the length of its inputs). In the randomized version, the pseudo-random generator takes as input a short private random string and using a public source of random bits produces a long string which looks random to the adversary even though this one knows the public string that has been used. Let us make the above discussion more formal. We consider families of distributions, also called ensembles, X = (Xn )n2N, where each Xn is a distribution onPn . The statistical dierence between two ensembles X and Y is dened by (Xn ; Yn ) = 2n j Prob(Xn = ) ? Prob(Yn = ) j. Ideally, we would like that the pseudo-random generator G : s ! l induces a distribution (G(x))x2s that is -close to the uniform distribution Ul on l for some small , i :e :, that has (G(x); Ul) . If this were possible, then an adversary of arbitrarily large size could not distinguish between the two distributions with a bias greater than , simply because there is no such statistical dierence between the two distributions. Unfortunately, if s < l this is not possible for = o(1). However, the two distributions could still be computationally undistinguishable. Let us consider for two ensembles X and Y , d(Xn ; Yn ) = maxAn j ProbXn (A) ? ProbYn (A) j. It is not dicult to see that d(Xn; Yn ) = 1=2(Xn; Yn ). Now, if an adversary circuit C cannot nd a set A n such that j ProbXn (A) ? ProbYn (A) j > , then for him the two distributions behave as if they had a statistical dierence bounded from above by 2. Therefore, we say that G : short(n) ! long(n) is a pseudo-random generator with security (; ) and expansion factor long (n) ? short(n), if for any circuit C of size (n), j Probx2short n (C (G(x)) = 1) ? Proby2long n (C (y) = 1) j (n): ( ) ( ) The randomized version follows the same ideas. Denition 4.1 Let ; ; : N ! R, long; short : N ! N, M be an oracle machine, and fR be the function computed by the machine M with oracle R. The function computed by M is a randomized pseudo-random generator that has security (; ) with probability and expansion factor long (n) ? short(n) if (a) M runs in polynomial time on all inputs and with all oracles, (b) fR on inputs of length short(n) produces outputs of length long (n) for all R, 8 and (c) with probability of R in Rn at least (n) it holds that for any family C = (Cn )n2N of oracle circuits of size less than (n), the following relation is true for n 2 N suciently large: R R j Probx2short n (Clong (n) (fR(x)) = 1) ? Proby2long n (Clong(n) (y ) = 1) j (n)): ( ) ( ) If (n) = 2?(short(n)) , (n) = 2(short(n)) and (n) = 1 ? 2?short(n) , for some positive constant then the randomized pseudo-random generator function is said to be strong. CnR is as in Denition 3.1. Impagliazzo [Imp96] has shown the existence of randomized one-way functions and he inferred from here the existence of strong randomized pseudo-random generators, using the general result of Hastad, Impagliazzo, Levin and Luby [HILL91] that states that pseudorandom generators exist if and only if one-way functions exist. We present below the complete construction of a strong randomized pseudo-random generator. Our starting point is also the strong randomized one-way function from [Imp96], but since this one-way function has the feature that is poly-to-1, we can use a simpler strategy following ideas from [Gol93, Section 3.5.1]. Let us describe formally the main steps in the construction. It is known how to transform a pseudo-random generator with a one bit expansion factor into one pseudo-random generator that doubles the length of the input (see [Gol93] or [BH89]) and how to transform the latter into a pseudo-random generator with an exponential expansion factor(see [GGM86]). Therefore the main objective is to get a randomized pseudo-random generator with a one-bit expansion factor. The natural idea would be to consider random functions R : n ! n+1 and to take as the pseudo-random generator the function fR (x) = R(x). However, it is not true that, with high probability of R, the distribution of fR (x) is 2? (n) -close (from the statistical dierence point of view) to the uniform distribution. Therefore we consider Rn the family of functions R : n ! n and take fR (x) = R(x) (in fact, according to Section 2 we should use here the notation Rnk for some k that will be dened later). Note that so far the expansion factor is 0. Surprisingly, we shrink fR (x) by applying to it a hash function randomly chosen (using private random bits) from a family of hash functions. More precisely, let Hnm be the family of functions h : n ! m of the form h(x) = xA + b, where A is an n-by-m binary matrix and b is an m-dimensional binary vector. It is known that if x 6= y 2 n , then h(x) and h(y ) are independent and uniformly distributed in m when h is uniformly at random selected from Hnm. We take m n ? 2 log n. The point is that, by a variant of the Leftover Hash Lemma of Impagliazzo, Levin and Luby [ILL89], with high probability of R in Rn , (h(fR(x)); h)x2n;h2Hnm is 2? (n) close to the uniform distribution. In order to compensate for the loss of length, we take advantage of the result of Impagliazzo [Imp96] that shows that, with high probability of R in Rn , fR is a strong one-way function and thus, by the results of Goldreich and Levin [GL89], fR can be transformed into a function gR that has for any constant d, a hard-core function b : n ! d log n . This means that the distributions (gR(x); b(x))x2n and (gR(x); u)x2n;u2d n cannot be log 9 distinguished with a bias of 2?o(n) by circuits of exponential size. Thus, we let the pseudorandom generator on input (x; h) to output (h(gR(x)); h; b(x)). In fact, in order to obtain the right parameters, we need to do a \product" of the above construction and consider 3n independent copies of gR (x1) : : :gR(x3n ) and b(x1) : : :b(x3n ) and apply an appropriately modied hash function to gR(x1) : : :gR (x3n ). The next lemma, proved by Impagliazzo [Imp96], summarizes the useful properties of fR . For completeness, we include a full proof. Lemma 4.2 [Imp96] For any polynomial q(n) and constant a < 1=2, there is a positive constant b such that with probability of R in Rn at least 1 ? 2?q(n) , it holds that for all oracle circuits of size 2an (a) Probx2n (fR(C R (fR(x)) 6= fR (x)) 1 ? 2?bn , (b) all strings in n have at most 2eq (n) + n preimages under fR . Proof. We show rst the following: Fact 4.3 With probability of R 2 Rn at least 1 ? 2?2q(n), no string in n has more than 2eq (n) + n preimages under fR . Proof of Fact 4.3. Take m = 2eq(n)+ n. By Markov's inequality, the probability over Rn that a xed y in n has m preimages under fR is at most the expected number of sets A ?2n of size m such that all elements in A map to y . The number of these sets is . Thus the m ?2n ?nm n m ? nm m 2 q ( n )+ n < (e2 =m) 2 = (e=m) < (1=2) . Summing above expected value is m 2 over all y in n , the probability that there is one string with more than m preimages is at most 2?2q(n) . Let C be an oracle circuit that attempts to invert fR and let s = 2an be its size. Without loss of generality we can assume that C R (y ) outputs z only if fR (z ) = y . We say that C R inverts y if fR (C R (y )) = y and that C R inverts a set T n if it inverts all elements of T . Fact 4.4 With probability of R 2 Rn at least 1 ? 2?(t?2s log2s), no oracle circuit of size s inverts a set with 2e2st elements. Proof of Fact 4.4. Let T be a set of size t. The probability that C R inverts T is at most nt that a queried string satises fR () 2 T is t=2n . The t (t=2 ) . Indeed, the probability R probability that for all y in T , C (y ) nds a query such that fR () 2 T is bounded from ?ts above by the probability that t questions out of the possible ts total number of questions ?ts are mapped by R into elements in T and this latter probability is t (t=2n )t . Thus, the expected number of sets T of cardinality t that are inverted by C R is at most ?2n ?ts nt n t t nt 2 t def t t (t=2 ) (e2 =t) (ets=t) (t=2 ) = (e s) = . The probability that a set U of cardinality u = 2e2 st is inverted by C?R is equal to the probability that all subsets T U of cardinality t are inverted. There are ut (u=t)t def =k such sets. By Markov's inequality, the probability that k subsets of cardinality t are inverted is at most =k = (e2 st=u)t = 2?t . 10 There are less than (4s2)s oracle circuits of size s. Therefore the probability that there is a circuit of size s that inverts a set of cardinality 2e2 st is at most 22s log 2s 2?t = 2?(t?2s log2s) . We can now nalize the proof of Lemma 4.2. Take t = 2s log 2s + 2q (n). By Fact 4.3 and Fact 4.4, with probability of R 2 Rn at least 1 ? 2?(t?2s log 2s) ? 2?2q(n) 1 ? 2?q(n) , no circuit of size s can invert more than 2e2 st elements and each element in n has at most 2eq (n) + n preimages under fR . Since a < 1=2, there is a b > 0 such that with probability of R in Rn at least 1 ? 2?q(n) , for any oracle circuit C of size s = 2an , there are at least 2n ? 2(1?b)n strings that map via fR into noninvertible strings. Thus (a) is proved and (b) follows from Fact 4.3. We pass now to construct the randomized pseudo-random generator. Let R0 be the set of R0 s satisfying (a) and (b) in Lemma 4.2. Let m = 2eq(n)+n. For each R 2 R0, let gR(x; s) = (fR (x); s), where jxj = n and jsj = 2n. Let l(n) = 1 + 2 log m. Let bi (x; s) denote the innerproduct mod 2 of the binary vectors x and (si ; : : :; si+n?1 ), where s = (s1; : : :s2n ). Then, by the results of Goldreich and Levin [GL89], the function b(x; s) = b1(x; s) : : :bl(n)(x; s) is a hard-core function of the function gR , i :e :, there exists a positive constant b1 such that for any oracle circuit C of size 2an and any R 2 R0 j Probx2 n (C R(gR(x); b(x)) = 1) ? Probx2 n;y2l n (C R(gR(x); y) = 1)j < 2?b n : Take now the function gR : 9n ! 9n , gR (x1 ; : : :; x3n) = gR (x1) : : :gR(x3n ) and b : 9n ! 3n(1+2 log m) , b(x1 ; : : :; x3n) = b(x1) : : :b(x3n ), where jxi j = 3n for all i. By 3 3 2 1 ( ) 2 2 using the hybrid method (see the exposition of Goldreich [Gol93]), we derive the existence of a positive constant b2 such that for any oracle circuit C of size 2an and any R 2 R0 R ?b n : j Probx2 n (C R(gR(x); b(x)) = 1) ? Probx2 n ;y2 n m (C (gR (x); y ) = 1)j < 2 Let p = 9n2 ? [3n(1 + 2 log m) ? 1] and p0 = 3n(1 + 2 log m). Let H denote a family of hash functions that map strings of length 9n2 into strings of length p. We nally dene the randomized pseudo-random generator as GR (x; h) = (h(gR(x)); h; b(x)); where h 2 H . Note rst that jGR (x; h)j = p + jhj + p0 = 9n2 + jhj + 1, and, thus, GR produces an output which is one bit longer than the input. Let R 2 R0 and let C be an oracle circuit of size 2an . We need to evaluate (4) j Probx2 n ;h2H (C R(GR(x; h) = 1) ? Proby2 n (C R(y) = 1) j: The rst term is Probx2 n ;h2H (C R(h(g(x)); h; b(x)) = 1) and the second term in the above equation can be rewritten as Probu2p ;h2H;z2p (C R(u; h; z ) = 1) and thus the above is less or equal to j Probx2 n ;h2H (C R(h(gR(x)); h; b(x)) = 1) ? Probx2 n ;h2H;z2p (C R(h(gR(x)); h; z) = 1) j 9 2 9 2 3 (1+2 log 2 ) 9 2 +1 9 2 9 2 0 9 2 9 2 0 + + j Probx2 n ;h2H;z2p (C R(h(gR (x)); h; z ) = 1) ? Probu2p ;h2H;z2p (C R(u; h; z ) = 1) j: 9 2 0 0 11 For all R in R0, the rst term is bounded from above by 2?b n , because otherwise the circuit C can be easily transformed into a circuit D that distinguishes (gR (x); bR (x)) from (gR (x); z ) with a probability larger than 2?b n which would contradict the fact that b is a hard-core function for gR . The second term is bounded by the statistical dierence between the distributions (h(gR (x)); h)x2 n ;h2H and (u; h)u2p;h2H : This can be evaluated by a relation between the statistical dierence and the \collision probability" (see [IZ89]). More precisely, if the \collision probability", Probh;h ;x;x ((h(gR(x)); h) = (h0 (gR (x0 )); h0) is bounded from above by jH1j2p (1 + 2 ), then the above statistical dierence is bounded from above by . Therefore, we only need to evaluate the collision probability. Observe rst that for all R 2 R0, 2 2 9 2 0 0 Probx;x 2 n (gR (x) = g R(x0 )) = 2?6n (Prob(fR (y) = fR (y 0)))3n 0 2 9 2 and Prob(fR(y) = fR (y 0)) = X z2n Prob(fR (y) = z ^ fR (y0 ) = z) = 2n m=2n m=2n = m2 =2n: Therefore Probh;h ;x;x ((h(gR (x)); h) = (h0(gR(x0 )); h0)) 0 0 Probh;h (h = h0)(Prob(h(gR(x)) = h0(gR(x0)) j h = h0) 0 jH1 j (Prob(gR(x) = gR(x0)) + Prob(h(gR(x)) = h(gR(x0)) j gR(x) 6= gR(x0)) jH1 j ( 2mnn + 21p ) = 6 9 2 = jH1j2p (m6n 2?[3n(1+2log m)?1] + 1) = jH1j2p (2?(3n?1) + 1): In the transition from line 3 to line 4, we have used the following: Probh;x;x (h(gR(x)) = h(g R (x0)) j gR (x) 6= g R(x0 )) = 0 = u6=u Prob(h(gR (x)) = h(g R (x0)) j gR (x) = u ^ gR (x0 ) = u0) P 0 Prob(gR(x) = u ^ gR(x0) = u0 j gR(x) 6= gR(x0)) = = u6=u Prob(h(u) = h(u0 ))Prob(gR (x) = u ^ g R(x0 ) = u0 j gR (x) 6= gR (x0)) = P 0 = 21p u6=u Prob(gR (x) = u ^ gR (x0 ) = u0 j g R (x) 6= g R (x0)) = 21p : P 0 Returning to equation (4), it follows that there exists a positive constant b3 such that j Probx (C R(GR(x)) = 1) ? Proby (C R(y ) = 1) j < 2?b n . Observe that without loss of 3 12 generality we can assume that for some constant k the length of the input of GR is nk . We have obtained that for every oracle circuit of size 2an and for every R in R0, j Probx2nk (C R(GR(x)) = 1) ? Proby2nk (C R(y) = 1) j < 2?b n : 4 +1 As we noted above, GR produces an output that is one bit longer than its input, i :e :, it has a one bit expansion factor. By a standard construction (see [Gol93] or [BH89]), the expansion factor can be enlarged to doubling the length of the input. Namely, we dene IR (x) = s1 : : :s2jxj, where s1 ; : : :; s2jxj are bits obtained in the following way: let x0 = x and, recursively, si is the rst bit of GR (xi?1) and xi is the jxj{bit long sux of GR (xi?1), for every 1 i 2jxj. Again, by an application of the hybrid method we derive the existence of a positive constant b4 such that for every oracle circuit of size 2an and for every R in R0, j Probx2 n (C R(GR(x)) = 1) ? Proby2 9 2 n 18 2 (C R(y ) = 1) j < 2?b n : 4 In a last step, thek expansion is made exponential. We x R in R0 and denote IR simply by k n n I . Let I0; I1 : ! denote the functions that give the rst nk ,k respectively the last nk bits of the output of I . Let 0 < b5 < b4. We now dene GR : n ! 2b n as follows. Let m = b5 n and 1 ; : : :; m be an m-bit long string. Then the 1 : : :m (in binary) bit of FR (x) is dened as the rst bit of I (I : : : (Im (x)) : : :)). Then the techniques of Goldreich, Goldwasser and Micali [GGM86] show that for all R in R0 and all oracle circuits C of size 2an 5 1 2 j Probx2nk (C R(FR(x) = 1)) ? Proby2 b n (C R(y) = 1) j < 2?(b ?b )n : 2 5 4 5 Consequently we have proved: Theorem 4.5 For every size of adversaries (n) with n (n) 2an for some a < 1=2, there exists a strong randomized pseudo-random generator with expansion factor 2 (n) ? nO(1). Moreover, every bit of the output can be computed in time polynomial in the length of the private seed. In fact, the result we proved is stronger, because the function FR achieves the prescribed security with probability of R larger than 1 ? 2?q(n) , for any polynomial q . 5 Probability 1 Results Theorem 3.2 and Theorem 4.5 can be used to obtain probability one relativized results. First we need to reformulate them in terms of random oracles. This can be done by encoding a family of functions R = (Rn )n2N (where each function Rn is an element of the probabilistic space Rn from Section 2) into a standard (i :e :, a set) oracle. To be more precise, an oracle A is viewed as a boolean function dened on . For x 2 n , it is convenient to call A(x) as bit x of A. If the functions Rn 2 Rn are of type Rn : i(n) ! m(n) then for each x 2 i(n) we encode Rn (x) in the bits x10; x102; : : :; x10m(n) of the oracle, 13 i :e :, for each n 2 N and x 2 i(n) , A(x10)A(x102) : : :A(x10m(n)) = Rn (x). Thus an oracle A encodes unambiguously a collection of functions (Rn)n2N , where for all n, Rn : i(n) ! m(n) for some xed strictly increasing functions i and m mapping naturals to naturals. Let A be the set of all oracles (or, equivalently, the set of all innite binary sequences) endowed with a probability distribution given by the Lebesgue measure. If P () is a property dependent on oracles A 2 A, we say that P holds relative to a random oracle, if ProbA2A (P (A) is true ) = 1. Impagliazzo [Imp96] has shown that strong one-way functions and pseudo-random generators exist relative to a random oracle (or, in an equivalent formulation, for a set of oracles having measure one). Theorem 3.2 easily implies the existence of strong hard functions relative to a random oracle. Theorem 5.1 For any function (n) with n (n) 2n for some < 1, with probability one on the set of oracles, there exists an oracle machine M computing a 0-1 valued function and running in time O(max((n)4+ ; n5)) for any > 0, such that for all circuits C of size (n) and all n suciently large j Probx2n (C A(x) = M A (x)) ? 1=2 j < 2? (n) : Proof : By applying the Borel-Cantelli Lemma to Theorem 3.2. Our next result concerns the resource-bounded measure of P=poly in EXP = DTIME [2nO ]. We need to review some basic notions of the theory of resourcebounded measure developed by Lutz [Lut92] building on earlier studies of Schnorr [Sch73]. For a comprehensive exposition, see the work of Mayordomo [May94]. A martingale is a function d from to the dyadic rationals (i :e :, numbers of the form n=2r for non-negative integers n; r), which satises the relation: for all w 2 , d(w) = 1=2(d(w0) + d(w1)). For measuring classes in EXP , it is enough to restrict our attention to martingales that are computable in QP = DTIME [2(log n)O ] (QP stands for quasipolynomial time). A class C is QP -measurable and has QP -measure 0, written QP (C ) = 0, if there is a QP -computable martingale d such that C S [d], where S [d] = fA : limn!1 d(A(1 : n)) = 1g (we say that martingale d succeeds on C ). A class C has measure 0 in EXP if QP (C \ EXP ) = 0 and it has measure 1 in EXP if QP (EXP ? C ) = 0. If C has neither measure 0 nor measure 1 in EXP , we say that C is not measurable in EXP . For the motivations behind these denitions, the reader could consult one of the following references [Lut92], [May94], [RSC95b], [Zim94]. Lutz [Lut92] showed that P=poly has measure 0 in the larger class DTIME [2n n ] and observed that since there are oracles A that make EXP A PA=poly ([Wil85]), relativizable techniques are not sucient to prove QP (P=poly \ EXP ) = 0. Regan, Sivakumar and Cai [RSC95b] have established a relation between the resource bounded measure of P=poly in EXP and the existence of strong pseudo-random generators. More precisely, they showed that if there exists strong pseudo-random generators then P=poly is not measurable in EXP . Building on their proof and using the techniques in Theorem 4.5, we obtain the following result. (1) (1) log Theorem 5.2 With respect to a random oracle A, PA =poly is not measurable in EXP A. 14 Proof : Suppose that with probability 1, QP (PA=poly \ EXP A) = 0. Since there are countable many QP martingales, there exists a QP -computable oracle martingale d and a set A0 of oracles with Prob(A0 ) > 0 such that for all A 2 A0 , dA succeeds on all languages L 2 P A =poly \ EXP A . Let c be a constant such that the computation time of dA on an c (log m ) input of length m is bounded by 2 . We repeat the construction of the randomized pseudo-random generator, except that in the last step, FA maps strings of length nk into =c n strings of length 2 (instead of 2b n ). Let us denote m = n1=(c+1) . Then, we obtain that with probability of A at most 2?n , it holds that if C is an oracle circuit of size 2O(mc ), 1 ( +1) 5 j Probx2mk c (C A(FA(x) = 1)) ? Proby2 m (C A(y) = 1) j > 2?O(mc ): Then by the Borel-Cantelli Lemma,c with probability one of A in A, the above relation holds +1 2 ( +1) for all oracle circuit C of size 2O(m ) and for almost every natural m. Observe that FA (x) can be interpreted as a boolean function on m variables, whose truth-table is the 2m -bit long string FA (x). We denote this function by fA;x . From the construction, it is easy to see that for all y in m , the computation of fA;x (y ) amounts to m computations of the form I(x) with = 0 or 1, and, thus, can be done in polynomial time in m. Given an innite sequence X = fxm 2 mc : m 2 Ng, one can build a language LA (X ) such that the characteristic sequence of LA (X ) for strings of length m is just fA;xm . By the above discussion, LA (X ) 2 PA=poly. We need the following two results from [RSC95b] which, for our purposes, we state in the relativized case. +1 Lemma 5.3 [RSC95b] Let d be an oracle martingale. Then for every oracle A, for any string u 2 , any l 2 N, b 2 R, jfv 2 l : dA(uv) (1 + 1b )dA(u)gj 2l( b +1 1 ): Lemma 5.4 [RSC95b] Let d be a QP -computable oracle martingale such for some oracle A, PA =poly \ EXP A is in S [dA] (i:e:, martingale dA witnesses that PA =poly has measure 0 in EXP A). Then for every polynomial q there exist innitely many m and circuits Ci of size at most q (i), for 0 i < m such that for all circuits Cn of size at most q(m), dA (u0 : : :um ) > (1 + 12 )dA(u0 : : :um?1 ); m where ui is the 2i -bit binary \characteristic string" that indicates the membership in L(Ci) of the strings in i . Now we build a circuit Dm for each m in the set of \innitely many m" guaranteed by Lemma 5.4. The strings u0 ; : : :; um?1 promised by that lemma are wired into Dm ; on m 2 input w 2 , Dm (w) accepts i dA (u0 u1 : : :um?1 w) (1 + 1=m2)dA (u0u1 : : :um?1 ). By Lemma 5.4, for all A 2 A0 , there are innitely many m such that Dm (fA;x ) = 0 for all x in mc . Thus, with positive probability of A in A, it holds that for innitely many n, Probx2mc (DmA (fA;x) = 1)) = 0. On the other hand, by Lemma 5.3, for all A 2 A and all m 2 N, Proby2 m (DmA (y ) = 1) 1=(m2 + 1). Therefore, D = (Dm )m2N is a family of +1 +1 2 15 oracle circuits of size 2O(mc) which for all oracles A in A0 achieves for innitely many m 2m and a string a bias of 1=(m2 + 1) in distingushing between a truly random string y 2 fA;x for a random x 2 mc . Since A0 has a strictly positive measure, this contradicts the fact that with probability one FA is a strong pseudo-random generator. Thus, relative to a random oracle, P=poly does not have measure 0 in EXP . It is shown in [RSC95b], how to build from a QP martingale that succeeds on EXP ? P=poly a QP martingale that succeeds on P=poly \ EXP . Since that construction relativizes, it follows that relative to a random oracle, P=poly does not have measure 1 in EXP . +1 6 AC0 vs. Sub-Linear Time Machines that run in sub-linear time have as special features a random-access read-only input tape and a read-write address tape for storing pointers to the input tape. At each moment, the machine has access to the bit on the input tape denoted on the address tape. As this is very similar to our model of machines computing randomized cryptographic primitives, it is not surprising that the counting techniques developed in previous sections are applicable in the investigation of sub-linear-time complexity classes. For example, using the parity construction from Theorem 3.2, the following hierarchy result is immediate: let h; k : N ! N be two functions with (i) h(n) < k(n) n, for all suciently large n, and (ii) k is fully time-constructible; there is a predicate f computable in k(n) time such that if M is a machine running in h(n) time, then, for all suciently large n, Probx2n (f (x) = M (x)) = 1=2. Perhaps more interesting is a similar relation that holds between DTIME [n ] and AC0, for all 2 [0; 1). Theorem 6.1 Let 2 (0; 1). There is a predicate f computable by a monotone linear-size depth-2 circuit such that if M is a machine running in time n , then for all suciently large n, j Probx2n (f (x) = M (x)) ? 1=2 j n? (1) . Proof : Fix some positive < and denote = ? and m = d log ne. Consider n 2 N such that mdln 2 2me n. Each x 2 n is decomposed into bln 2 2mc substrings x(1); : : :; x(bln 2 2mc), each of length m, and some remaining string which will be ignored in the sequel. We dene the predicate f by f (x) = 1, if there is i 2 f1; : : :; bln 2 2m cg such that x(i) = 1m , and 0, otherwise. It is easy to check that f can be computed by a circuit having the claimed parameters. Consider a machine M that runs in n steps on inputs of length n. Let S = fx 2 n j for each j 2 f1; : : :; ng, if the j -th bit of x is read by M on input x, then the substring x(i) that contains the j -th bit of x veries x(i) 6= 1m ). The probability in n of S , the complementary of S , is less than n 2?m n?(?) = n? . We claim that for each b 2 f0; 1g, Prob(f (x) = 0 j M (x) = b ^ S ) = (1?2?m )bln2 2m c?q(jxj), where q (jxj) is the number of bits read by M on input x. Indeed, since we are conditioning by S , all bits that are read by M on input x, belong to some substrings x(i) such that x(i) 6= 1m. Therefore, the above probability is equal to the probability that the remaining 16 \non-touched" substrings are dierent from 1m . The probability that such a substring is dierent from 1m is (1 ? 2?m ) and there are bln 2 2m c such substrings. Since q (jxj) n , we deduce that (1 ? 2?m )bln2 2m c?q(jxj) 2 [(1=2 ? 2?m )bln2 2m c ; (1=2 ? 2?m )bln2 2m c?n ] [(1=2 ? n? ); (1=2 + n? )] (the last relation follows from the Taylor expansions of the functions involved). Then, Prob(f (x) = M (x) j S ) = Prob(f (x) = 0 j M (x) = 0 ^ S )Prob(M (x) = 0 j S )+ +Prob(f (x) = 1 j M (x) = 1 ^ S )Prob(M (x) = 1 j S ) = = (1=2 n? )Prob(M (x) = 0 j S + (1=2 n? )Prob(M (x) = 1 j S ) = 1=2 n? : Since for any events A and B , Prob(A j B ) ? Prob(B ) Prob(A) Prob(A j B )+ Prob(B ), it follows that j Prob(f (x) = M (x)) ? 1=2 j 2n? : 17 References [Ajt83] [AS94] [BH89] [BIS90] [Blu84] [GGM86] [GL89] [Gol93] [HILL91] [ILL89] [Imp96] [IZ89] [Kah67] [KM94] M. Ajtai. 11 -formulae on nite structures. Ann. Pure and Applied Logic, 24:1{ 48, 1983. E. Allender and M. Strauss. Measure on small complexity classes, with applications for BPP. In Proceedings of the 34th IEEE Symposium on Foundations of Computer Science, pages 807{818, 1994. R. Boppana and R. Hirschfeld. Pseudorandom generators and complexity classes. In S. Micali, editor, Advances in Computing Research. Randomness and Computation, pages 1{26. JAI Press Inc., 1989. D. Barrington, N. Immerman, and H. Straubing. On uniformity within NC1. Journal of Computer and System Sciences, 41:274{306, 1990. M. Blum. Independent unbiased coin ips from a correlated biased source: A nite state Markov chain. In Proceedings of the 25th IEEE Symposium on Foundations of Computer Science, pages 425{433, 1984. O. Goldreich, S. Goldwasser, and S. Micali. How to construct a random functions. Journal of the ACM, 33(4):792{807, 1986. O. Goldreich and L. Levin. A hard-core predicate for all one-way functions. In Proceedings of the 21st ACM Symposium on Theory of Computing, pages 25{32, 1989. O. Goldreich. Foundations of cryptography (fragments of a book), February 1993. ECCC Technical report, available at http://www.eccc.uni-trier.de/local/ECCCBooks/eccc-books.html. J. Hastad, R. Impagliazzo, L. Levin, and M. Luby. Construction of a pseudorandom generator from any one-way function. Technical Report 91-68, ICSI, Berkeley, 1991. R. Impagliazzo, L. Levin, and M. Luby. Pseudo-random generation from one-way function. In Proceedings of the 21st ACM Symposium on Theory of Computing, pages 12{24. ACM Press, 1989. R. Impagliazzo. Very strong one-way functions and pseudo-random generators exist relative to a random oracle. (manuscript), January 1996. R. Impagliazzo and D. Zuckerman. How to recycle random bits. In Proceedings of the 30th IEEE Symposium on Foundations of Computer Science, pages 248{253. IEEE Computer Society Press, October/November 1989. D. Kahn. The codebreakers: the story of secret writing. New York, MacMillan, 1967. S. Kautz and P. Miltersen. Relative to a random oracle, NP is not small. In Proceedings of the 9th Structure in Complexity Theory Conference, pages 162{ 174. IEEE Computer Society Press, 1994. 18 [Koz91] D. Kozen. The Design and Analysis of Algorithms. Springer-Verlag, 1991. [LS93] J. Lutz and W. Schmidt. Circuit size relative to pseudorandom oracles. Theoretical Computer Science, 107:95{120, 1993. [Lut92] J. Lutz. Almost everywhere high nonuniform complexity. Journal of Computer and System Sciences, 44:220{258, 1992. [May94] E. Mayordomo. Contributions to the Study of Resouce-Bounded Measure. PhD thesis, Universidad Polytecnica de Catalunya, Barcelona, April 1994. [RSC95a] K. Regan, D. Sivakumar, and J. Cai. Pseudorandom generators, measure theory, and natural proofs. In Proceedings of the 35th IEEE Symposium on Foundations of Computer Science, pages 26{35. IEEE Computer Society Press, October 1995. [RSC95b] K. Regan, D. Sivakumar, and J. Cai. Pseudorandom generators, measure theory, and natural proofs. Technical Report TR95-006, Electronic Colloquium on Computational Complexity, 1995. Available at http://www.eccc.uni-trier.de/eccc/. [Sch73] C. Schnorr. Process complexity and eective random tests. Journal of Computer and System Sciences, 7:376{388, 1973. [Sho88] V. Shoup. New algorithms for nding irreducible polynomials over nite elds. In Proceedings of the 29th IEEE Symposium on Foundations of Computer Science, pages 283{290. IEEE Computer Society Press, 1988. [SSS93] J.P. Schmidt, A. Siegel, and A. Srinivasan. Cherno-Hoeding bounds for applications with limited independence. In Proceedings of the ACM/SIAM Symposium on Discrete Algorithms, pages 331{340, 1993. [SV86] M. Santha and U. Vazirani. Generating quasi-random sequences from semirandom sources. Journal of Computer and System Sciences, 33:75{87, 1986. [Wil85] C. Wilson. Relativized circuit complexity. Journal of Computer and System Sciences, 31(2):169{181, 1985. [Zim94] M. Zimand. On the size of classes with weak membership properties. Technical Report 557, Department of Computer Science, Univ. of Rochester, Rochester, NY, 1994. 19

© Copyright 2018