PUMaC 2016 · 加试 · 第 11 题

PUMaC 2016 Power Round Solutions Eric Neyman 1

1. Notation and Preliminary Definitions
2. Complexity 2.1. Big O Notation Problem 2.1. (a) Yes: c = 2 and N = 1. (b) Yes: c = 1 and N = 2. (c) No: for any positive real number c , we will always have n > 2 c for n large enough. (d) Yes: c = 1000 and N = 1. Problem 2.2. Let c and N be such that f ( n ) ≤ c g ( n ) for all n ≥ N . Let c and N be 1 1 1 1 2 2 such that g ( n ) ≤ c h ( n ) for all n ≥ N . Let N = max( N , N ). Then for all n ≥ N , we have 2 2 1 2 f ( n ) ≤ c g ( n ) ≤ c c h ( n ). Letting c = c c , we conclude that f ( n ) = O ( h ( n )). 1 1 2 1 2 2.2. Polynomial and Negligible Functions Problem 2.3. (a) Yes: k = 2 (or any larger k ). 1 1 2 k (b) No: if such a k were to exist, raising both sides to the power we find that n ≤ c lg( n ) k for large enough values of n for some c , and this is false for all k ∈ N . k n (c) No: for any c and k , n ! > cn for n large enough, since n ! grows as n . lg( n ) k lg( n ) − k (d) No: if n ≤ cn for n large enough then n ≤ c for n large enough, but this is clearly not the case. Problem 2.4. k 1 (a) Let N , c , and k be such that for n ≥ N , f ( n ) ≤ c ( h ( n )) . Let N , c , and k be 1 1 1 1 1 2 2 2 k 2 such that for n ≥ N , g ( n ) ≤ c ( h ( n )) . Let N = max( N , N ), k = max( k , k ), and 2 2 1 2 1 2 c = 2 max( c , c ). Then for n ≥ N , we have 1 2 c k k 1 f ( n ) ≤ c ( h ( n )) ≤ ( h ( n )) 1 2 c k k and similarly g ( n ) ≤ ( h ( n )) , so f ( n )+ g ( n ) ≤ c ( h ( n )) , which means that f ( n )+ g ( n ) 2 is polynomial in h ( n ). k 1 (b) Let N , c , and k be such that for n ≥ N , f ( n ) ≤ c ( h ( n )) . Let N , c , and k 1 1 1 1 1 2 2 2 k 2 be such that for n ≥ N , g ( n ) ≤ c ( h ( n )) . Let N = max( N , N ), k = k + k , and 2 2 1 2 1 2 c = c c . Then for n ≥ N , we have 1 2 k k k + k k 1 2 1 2 f ( n ) g ( n ) ≤ c ( h ( n )) · c ( h ( n )) = c c ( h ( n )) = c ( h ( n )) , 1 2 1 2 which means that f ( n ) · g ( n ) is polynomial in h ( n ). 2

Problem 2.5. k (a) No: take k = 2. Then n | f ( n ) | = 1 which is never less than 1. k n (b) Yes: for all k , will be less than 1 for n large enough. n 2 k n k − lg( n ) k (c) Yes: for any k , = n < 1 for n large enough: specifically, take n = 2 (then lg( n ) n ⌈ ⌉ k lg( n ) = log (2 + 1) = k + 1). 2 Problem 2.6. k (a) For each positive integer k , let N be such that for all n ≥ N , n | f ( n ) | < 1, and k, 1 define N analogously for g . Let N = max(max( N , N ) , 2). Then for all k, 2 k ( k +1) , 1 ( k +1) , 2 n ≥ N , we have k 1 1 1 k k +1 n | f ( n ) | = · n | f ( n ) | < ≤ n n 2 1 k and similarly n | g ( n ) | < , so 2 k k n | f ( n ) + g ( n ) | ≤ n ( | f ( n ) | + | g ( n ) | ) < 1 , so f ( n ) + g ( n ) is indeed negligible. k (b) For each positive integer k , let N be such that for all n ≥ N , n | f ( n ) | < 1, and k, 1 define N analogously for g . Let N = max( N , N ). Then for all n ≥ N , we have k, 2 k k, 1 k, 2 k k 2 k k k n | f ( n ) · g ( n ) | ≤ n | f ( n ) · g ( n ) | = n | f ( n ) | · n | g ( n ) | < 1 , so f ( n ) · g ( n ) is indeed negligible. k f Problem 2.7. Let N and k be such that f ( n ) ≤ n for all n ≥ N (we can ignore the f f f k constant because if f ( n ) ≤ cn for n large enough, then for n large enough (at least as large k +1 as c ), f ( n ) ≤ n , so we just change the k ). For each positive integer k , let N be such k k that for all n ≥ N , n | g ( n ) | < 1. For each positive integer k , define M = max( N , N ). k k k + k f f Then for n ≥ M , we have k k k + k f f f ( n ) ≤ n and n | g ( n ) | < 1 , so k + k k f f f ( n ) · n | g ( n ) | < n k n | f ( n ) · g ( n ) | < 1 , which means that f · g is indeed negligible. 2.3. Polynomial-Time Algorithms Problem 2.8. (a) Clearly the algorithm takes at least n steps on input n . If the algorithm were a k polynomial-time algorithm, then for some c and k , n ≤ c (lg n ) for n large enough; however, this is clearly not the case (as n gets large, doubling n increases the right-hand side by a factor that approaches 1, so n eventually overtakes the right-hand side). (b) For input n , multiply n by n + 1, divide the result by 2, and output the result. 3

3. Some Probability Theory 3.1. Probabilities Over Different Spaces Problem 3.1. 4+3+2+1 10 1 (a) Yes: in particular, the probability is = < . 36 36 2 4 (b) No: if the first roll is a 6 then the probability is (the probability that 3 or higher 6 1 is rolled on the second die), which is greater than . (The first roll being 5 is also a 2 counterexample to the statement.) (c) Yes: for example, if the first roll is 1, then the probability that the sum of the rolls is 1 at least 9 is 0, which is less than . 2 3.2. Random Variables and Bounds on Probabilities Problem 3.2. (a) Suppose that X , X , . . . , X are independent. For any x and x , we have 1 2 n 1 2 ∑ Pr [ X = x and X = x ] = Pr [ X = x and X = x and . . . and X = x ] 1 1 2 2 1 1 2 2 n n ( x ,...,x ) 3 n n ∑ ∏ = Pr [ X = x ] i i i =1 ( x ,...,x ) 3 n ( ) n ∑ ∏ = Pr [ X = x ] Pr [ X = x ] Pr [ X = x ] 1 1 2 2 i i i =3 ( x ,...,x ) n 3 n ∑ ∏ = Pr [ X = x ] Pr [ X = x ] Pr [ X = x ] 1 1 2 2 i i i =3 ( x ,...,x ) 3 n = Pr [ X = x ] Pr [ X = x ] , 1 1 2 2 as desired. 1 1 1 (b) X and X are pairwise independent, since Pr [ X = x ] Pr [ X = x ] = · = 1 2 1 1 2 2 2 2 4 for any x , x ∈ { 0 , 1 } , and indeed for each possible ( x , x ) exactly one of the four 1 2 1 2 bit strings has ( X , X ) = ( x , x ). The other two pairs are, analogously, indepen- 1 2 1 2 dent. However, the three random variables are not independent because for example 1 1 Pr [ X = 0] Pr [ X = 0] Pr [ X = 0] = but the probability that all three are zero is . 1 2 3 8 4 Problem 3.3. Let X be a random variable that only takes on nonnegative values, and let a be positive. We have ( ) ∑ ∑ ∑ E ( X ) 1 1 = x Pr [ X = x ] = x Pr [ X = x ] + x Pr [ X = x ] a a a x x<a x ≥ a 1 ≥ (0 + a · Pr [ X ≥ a ]) = Pr [ X ≥ a ] . a 4

Problem 3.4. Let X , X , . . . , X be pairwise independent random variables. We have 1 2 n     ( ) ( ( )) ( ) 2 2 ∑ ∑ ∑ ∑ ∑     V X = E X − E X = E X − E ( X ) i i i i i i i i i i   ( ) 2 ∑   = E ( X − E ( X )) i i i ( ) ∑ ∑ 2 = E ( X − E ( X )) + 2 ( X − E ( X ))( X − E ( X )) i i i i j j i i 6 = j ∑ ∑ 2 = E (( X − E ( X )) ) + 2 E (( X − E ( X ))( X − E ( X ))) i i i i j j i i 6 = j ∑ ∑ = V ( X ) + 2 E (( X − E ( X ))( X − E ( X ))) . i i i j j i i 6 = j Thus, it suffices to show that E (( X − E ( X ))( X − E ( X ))) = 0. Note that X and X are i i j j i j ′ ′ independent, so clearly X = X − E ( X ) and X = X − E ( X ) are independent. We want i i j j i j ′ ′ to show that E ( X X ) = 0. We have i j ∑ ∑ [ ] [ ] ′ ′ ′ ′ ′ ′ E ( X X ) = x Pr X X = x = x x Pr X = x and X = x i j i j i j i j i j x x ,x i j ∑ ∑ ∑ [ ] [ ] ′ ′ ′ ′ = x x Pr [ X = x ] Pr X = x = x Pr [ X = x ] x Pr X = x i j i j i i j j i j i j x ,x x x i j i j ′ ′ = E ( X ) E ( X ) = 0 · 0 = 0 . i j This concludes the proof. Problem 3.5. We have 2 [ ] E (( X − E ( X )) ) V ( X ) 2 2 Pr [ | X − E ( X ) | ≥ t ] = Pr ( X − E ( X )) ≥ t ≤ = , 2 2 t t with the ≤ step by Markov’s inequality. Problem 3.6. Let X be the number of coins that land heads. (a) Clearly X satisfies the conditions of Markov’s inequality, and E ( X ) = 500. Thus, we have 500 5 Pr [ X ≥ 600] ≤ = . 600 6 (b) Note that if X through X are the coin flips, then since the coin flips are independent 1 1000 we have ( ) ( ) ( ) 2 ∑ ∑ 1 V ( X ) = V X = V ( X ) = 1000 E X − = 250 . i i i 2 i i 5

We thus have 1 V ( X ) 250 1 Pr [ X ≥ 600] = Pr [ | X − E ( X ) | ≥ 100] ≤ = = (= 0 . 0125) . 2 2 2 · 100 20000 80 (c) Use the Chernoff bound. Write your answer in scientific notation. (You may use a calculator.) 4. Introduction to Cryptography 4.1. Definition of an Encryption Scheme 4.2. Examples of Encryption Schemes Problem 4.1. (a) WKDR (b) PUMAC (c) INTEGRATIONBYSMARTS (INTEGRATION BY SMARTS); shift amount: 23. 4.2.1. One-Time Pad Problem 4.2. (a) 110101 (b) 010010 Problem 4.3. (a) 0 (b) x (c) Yes (clearly). (d) Yes: the i -th bit of each expression is 1 if and only if among the i -th bits of x , y , and z , an odd number are 1. (e) If x ⊕ y = z , we have x ⊕ z = x ⊕ ( x ⊕ y ) = ( x ⊕ x ) ⊕ y = y . (f) Clearly if y = z then x ⊕ y = x ⊕ z . If x ⊕ y = x ⊕ z then x ⊕ ( x ⊕ y ) = x ⊕ ( x ⊕ z ). Using the associative property and the identity that x ⊕ x = 0, we find that y = z . Problem 4.4. Bob should take the xor of k and the ciphertext c : c ⊕ k = ( m ⊕ k ) ⊕ k = m . n Problem 4.5. The key space and ciphertext space are both also { 0 , 1 } . G generates n bits n uniformly at random to form k ∈ { 0 , 1 } ; we have E ( m ) = m ⊕ k ; we have D ( c ) = c ⊕ k . k k 6

5. Security of Encryption Schemes 5.1. Indistinguishability of Encryptions Problem 5.1. The encryption scheme the teammate describes is invalid: E has to be k injective; otherwise it is impossible to have an algorithm D that inverts the encryption. Problem 5.2. Suppose that ( G, E, D ) does not satisfy computational indistinguishability of encryptions. Then there exists a non-negligible function ( n ) such that for all n there exist A , m , and m such that 0 1 1 | Pr [ A ( E ( m )) = 1] − Pr [ A ( E ( m )) = 1] | > ( n ) . k 0 k 1 Assume without loss of generality that A outputs 1 more frequently on E ( m ) than on k 1 E ( m ); in particular, A outputs 1 on E ( m ) with probability p and 1 on E ( m ) with k 0 k 0 0 k 1 ′ probability p , where p − p > ( n ). Let A be an adversary that plays the game in the 1 1 0 ′ ′ second definition. A gives m and m to the referee. Say the referee returns y ; then A 0 1 ′ runs A on y and outputs 1 if A ( y ) = 1 and 0 otherwise. We claim that A is correct with 1 1 ′ probability at least + ( n ). Indeed, conditional on b = 0, A outputs 0 with probability 2 2 ′ ′ 1 − p , and conditional on b = 1, A outputs 1 with probability p . Thus, A is correct with 0 1 probability 1 1 1 (1 − p + p ) = + ( n ) . 0 1 2 2 2 ′ 1 Clearly A is a PPT algorithm and ( n ) is non-negligible. Thus, ( G, E, D ) does not satisfy 2 guessing indistinguishability of encryptions. Suppose that ( G, E, D ) does not satisfy guessing indistinguishability of encryptions. Then ′ let ( n ) be any particular non-negligible function and let A a PPT algorithm that wins the 1 guessing game with probability more than + ( n ) for n large enough. Note that this means 2 that there exist m and m (for any fixed n that is large enough) such that, conditional on 0 1 1 ′ ′ A picking m and m , A wins the guessing game with probability more than + ( n ) (if for 0 1 2 1 ′ every pair of messages A won the game with probability at most + ( n ), then the overall 2 ′ 1 probability that A wins the game is at most + ( n )). Construct A , the adversary for the 2 ′ first definition of encryption scheme security, as follows: on input y , A runs A on y and ′ returns the bit that A returns. We claim that | Pr [ A ( E ( m )) = 1] − Pr [ A ( E ( m )) = 1] | > ( n ) . k 0 k 1 ′ Indeed, let the first probability be p and the second probability be p . Since A wins the 0 1 1 1 1 guessing game with m and m with probability (1 − p ) + p > + , it follows that 0 1 0 1 2 2 2 1 This requires a bit of justification. Definitionally, all we have is that for every negligible function neg( n ) there exist n , A , m , and m such that the difference between the stated probabilities is greater than neg( n ). 0 1 But if this is the case, let ( n ) be the largest possible difference in these probabilities (maximized over possible choices of A , m , and m ). Clearly ( n ) is non-negligible, since if it were negligible then 2 ( n ) is a negligible 0 1 function, and there do not exist n , A , m , and m such that the difference between the stated probabilities 0 1 is greater than 2 ( n ). Conversely, if the equation is satisfied for a non-negligible function ( n ), then clearly there is no negligible function that the difference in probabilities is always less than. This reasoning is used in several solutions, heretofore without comment. 7

| p − p | > 2 > . Clearly A is a PPT algorithm, so we conclude that ( G, E, D ) does not 0 1 satisfy computational indistinguishability of encryptions. Therefore, the two definitions describe the same property, as desired. Problem 5.3. Pick any n . Let m and m be any two messages. Let p = Pr [ A ( E ( m )) = 1] = 0 1 k 0 Pr [ A ( m ⊕ k ) = 1]. We can write 0 ∑ ∑ 1 1 p = Pr [ A ( m ⊕ k ) = 1] = Pr [ A ( m ⊕ ( k ⊕ m ⊕ m )) = 1] . 0 1 0 1 n n 2 2 n n k ∈{ 0 , 1 } k ∈{ 0 , 1 } ′ ′ ′ Now, for each k there is a unique k such that k = k ⊕ m ⊕ m , and these k are distinct for 0 1 n n distinct k . In other words f ( k ) = k ⊕ m ⊕ m is a bijective function from { 0 , 1 } to { 0 , 1 } . 0 1 This allows us to write the expression above on the right as ∑ 1 ′ p = Pr [ A ( m ⊕ k ) = 1] = Pr [ A ( m ◦ k ) = 1] . 1 1 n 2 ′ n k ∈{ 0 , 1 } Therefore, | Pr [ A ( E ( m )) = 1] − Pr [ A ( E ( m )) = 1] | = 0 , k 0 k 1 and thus smaller than a negligible function. Therefore, the one-time pad is secure, as desired. Problem 5.4. 8 n (a) Consider the following adversary A : on input c ∈ { 0 , 1 } , A breaks c into 8-bit chunks c , c , . . . , c and returns 1 if and only if c = c = · · · = c . Observe that for n > 1, A 1 2 n 1 2 n n n − 1 always returns 1 on input m = 0 and always returns 0 on input m = 0 ◦ 1. Thus, 0 1 there is no negligible function such that the probability of A distinguishing between these two messages m and m is less than the negligible function for all n (since the 0 1 probability of distinguishing is 1). Therefore, the stated encryption scheme is insecure. (b) In the previous part we saw that an adversary could distinguish between two messages encrypted with the same eight-bit “one-time” pad. The same applies to any constant length. 6. Pseudorandom Generators 6.1. What is a Pseudorandom Generator? Problem 6.1. (a) Let D return the last bit of its input. Clearly D always returns 1 on input H ( x ) for 1 any x and returns 1 with probability for a random x of length ` ( n ) = n + 1. Thus, 2 1 the difference in probabilities is , which is not smaller (for all n ) than any negligible 2 function, so H is not a pseudorandom generator. 8

(b) Let D return 1 if the first half of its input equals the second half, and 0 otherwise. 1 Clearly D always returns 1 on input H ( x ) for any x and returns 1 with probability n 2 for a random x of length ( n ) = 2 n . Thus, the difference in probabilities is nearly 1, which is not smaller (for all n ) than any negligible function, so H is not a pseudorandom generator. (c) Here we do not have ( n ) > n , so H is not a pseudorandom generator. (d) Let D return the binary xor of all bits of its input except the first. On input H ( x ) for any x , D will return x ⊕ x ⊕ x ⊕ x ⊕ · · · ⊕ x ⊕ x ⊕ x = 0 , 1 2 2 3 n n 1 1 while on a random x of length ( n ) = n + 1, D will return 0 with probability . Thus, 2 1 the difference in probabilities is , which is not smaller (for all n ) than any negligible 2 function, so H is not a pseudorandom generator. 6.2. Constructing Secure Encryption Schemes from PRGs Problem 6.2. We first note that ( G, E, D ) is indeed an encryption scheme: G , E , and D are polynomial-time algorithms because ( n ) is polynomial in n (otherwise H would not be a polynomial-time algorithm) and D is deterministic. Furthermore, D ( E ( m )) = k k ( m ⊕ H ) ⊕ H = m . k k Suppose for contradiction that ( G, E, D ) is not a secure encryption scheme. Then for each negligible function there is an n and an A that breaks ( G, E, D ) with probability greater than the negligible function evaluated at n . Put another way, there is a non-negligible function ( n ) such that for each n there is an algorithm A that breaks ( G, E, D ) with probability at least ( n ). We use the guessing definition of indistinguishability of encryptions and note that this means that for each n there exist messages m and m such that A can guess b 0 1 1 from E ( m ) with probability at least + ( n ). k b 2 Construct a distinguisher D as follows: pick b uniformly at random from { 0 , 1 } . Run ( n ) ′ ′ A on m ⊕ y where y ∈ { 0 , 1 } . Output 1 if b = b (where b is the output of A ) and 0 b otherwise. ( n ) If y is chosen uniformly at random from { 0 , 1 } (we write y = U , then D outputs 1 ` ( n ) 1 with probability , since the distribution of m ⊕ y does not depend on m , so A essentially b b 2 has no information. If alternatively y = H ( U ) (i.e. H applied to a uniformly random n -bit n 1 ′ string), then the probability that b = b is at least + ( n ). This is because the input to 2 A is precisely E ( m ) = m ⊕ H ( k ) for k = U . Thus, if D is given H ( U ) as input, it will k n n 1 output 1 with probability at least + ( n ). But this means that H is not a pseudorandom 2 generator, which is a contradiction. Therefore, ( G, E, D ) is a secure encryption scheme, as desired. 9

7. One-Way Functions 7.1. What is a One-Way Function? Problem 7.1. n (a) We construct an adversary A that always inverts f . If A is given ( k, 1 ) as input, A k k returns the string 1 of k ones. Clearly A is polynomial in n and f (1 ) = k . n 2 (b) If A is given ( y, 1 ) as input, i.e. there is some x such that f ( x ) = x = y , A can find x as follows. A knows that the first ( n th-to-last) bit of x is 1. A can figure out the second bit of x by squaring 1100 . . . 0 (with n − 2 zeros); if the result is greater than y then the second bit of x is 0; if it is less than or equal to y then the second bit of x is
8. Similarly, A can find the third bit of x , and so on. − 1 − 1 (c) Note that ( k ) ≡ k (mod p ). So there are two possibilities: either f cannot be computed in polynomial time (this is in fact not the case) in which case f is clearly not a one-way function; or f can be computed in polynomial time, in which case A can simply run f on its own input and return the result. 7.2. Number-Theoretic One-Way Functions and Assumptions 7.3. Hard-Core Bits Problem 7.2. Our solution is based on this document: http://www.cs.cornell.edu/courses/cs687/2006fa/lectures/lecture11.pdf (a) Suppose for contradiction that g is not a one-way function. Let neg( n ) be a negligible function. There is an n and a PPT adversary A that inverts g ( x ◦ y ) for randomly chosen n -bit strings x and y with probability greater than neg(2 n ). Consider the following ′ ′ adversary A : on input t of length n , A generates a random n -bit string y , runs A on ′ t ◦ y , and outputs the first n bits of the result. Clearly A is a PPT algorithm. We ′ claim that A inverts f on n -bit inputs with probability greater than neg(2 n ). ′ ′ Suppose that we run A on f ( x ) for a random x . When A calls A , A is run on g ( x, y ) = f ( x ) ◦ y for a randomly selected 2 n -bit string x ◦ y , since x and y are selected independently and at random from the set of 2 n -bit strings. Therefore, with probability ′ ′ ′ ′ ′ ′ greater than neg(2 n ), A returns a string ( x , y ) such that g ( x ◦ y ) = f ( x ) ◦ y = f ( x ) ◦ y , ′ ′ in which case f ( x ) = f ( x ). Thus, when A returns the first n bits of the output of A , with probability greater than neg(2 n ) this output inverts f . ( ) n Now for any negligible function neg( n ), note that neg is still a negligible function, 2 ′ so as we have shown there is an algorithm A that inverts f with probability neg( n ). This is a contradiction, since there must exist a negligible function such that no PPT algorithm inverts f with probability greater than it, for every n . Therefore, g is a one-way function, as desired. 10

∑ m X i (b) Let X = . Then by Chebyshev’s inequality we have k =1 m V ( X ) Pr [ | X − μ | ≥ ] ≤ . 2 Since the X are pairwise independent, the variances add, so we have i ( ) ( ) ( ) ( ) k 2 ( ) ∑ 2 X X 1 μ μ i 1 V ( X ) = V = mV = m μ · − + (1 − μ ) · m m m m m i =1 1 = μ (1 − μ ) . m Therefore, we have μ (1 − μ ) Pr [ | X − μ | ≥ ] ≤ , 2 m as desired. 2 (c) If A is perfect, then on input ( f ( x ) , y ), it will always return b ( x, y ). Let i = 1; the following computation is the same for all other i . For any j , we have g = b ⊕ A ( f ( x ) , e ⊕ r ) = b ( x, r ) ⊕ b ( x, e ⊕ r ) j j i j j 1 j ( ) ( ) n n ⊕ ⊕ = ( x ∧ ( r ) ) ⊕ ( x ∧ (( e ) ⊕ ( r ) )) k j k k 1 k j k k =1 k =1 n ⊕ = (( x ∧ ( r ) ) ⊕ ( x ∧ (( e ) ⊕ ( r ) ))) k j k k 1 k j k k =1 n ⊕ = (( x ∧ ( r ) ) ⊕ ( x ∧ (1 ⊕ ( r ) ))) ⊕ (( x ∧ ( r ) ) ⊕ ( x ∧ (0 ⊕ ( r ) ))) 1 j 1 1 j 1 k j k k j k k =2 n ⊕ = (( x ∧ ( r ) ) ⊕ ( x ∧ ¬ ⊕ ( r ) )) ⊕ (( x ∧ ( r ) ) ⊕ ( x ∧ ( r ) )) 1 j 1 1 j 1 k j k k j k k =2 = ( x ∧ ( r ) ) ⊕ ( x ∧ ¬ ⊕ ( r ) ) . 1 j 1 1 j 1 If ( r ) = 0 then this simplifies to 0 ⊕ x = x and if ( r ) = 1 then this simplifies to j 1 1 1 j 1 x ⊕ 0 = x . Thus, g = x and so t , the majority of the g ’s, will be x . Similarly, 1 1 j 1 1 j 1 for all 1 ≤ i ≤ n , t = x , so B indeed inverts f . i i n (d) If | S | < 2 · then the probability (over all x , not just those in S ) that A ( f ( x ) , r ) = 2 1+ b ( x, r ) is less than · 1 + 1 · (respectively, the probability that x ∈ S times the 2 2 probability that A ( f ( x ) , r ) = b ( x, r ) given that x ∈ S , times the probability that x 6 ∈ S times the probability that A ( f ( x ) , r ) = b ( x, r ) given that x 6 ∈ S ). And this is at most 1 1

• , contradicting the fact that A ( f ( x ) , r ) = b ( x, r ) with probability + . 2 2 Fix i . Without loss of generality assume x = 1. Then each g is 1 with probability i j 1 greater than + , since g = 1 if A gives the correct output, and the input to A is j 2 2 2 This is clearly only possible if f is injective. 11

f ( x ) (with x ∈ S ) and e ⊕ r (which we may treat as a uniformly random string in i j n n { 0 , 1 } , since r is a uniformly random string in { 0 , 1 } ). Thus, g = 1 with probability j j 1 μ > + and 0 otherwise. Note that a majority of the g are 1 if and only if their j 2 2 1 sum divided by m is greater than . Applying Part (b) to the g , we have j 2 ∑ ∣ [∑ ] [∣ ] ∣ ∣ X 1 X 1 μ (1 − μ ) μ (1 − μ ) 1 i i ∣ ∣ Pr ≤ ≤ Pr − μ ≥ μ − ≤ ≤ ≤ . ( ) ( ) 2 2 ∣ ∣ 2 1 m 2 m 2 m m μ − m 2 2 2 n Thus, if m ≥ , then the probability that at least one of the t returned by g is wrong 2 i n 1 is (using the union bound) at most ≤ , in which case clearly B returns x correctly 2 m 2 with a non-negligible probability. (e) Modify B as follows: B randomly generates lg( m ) strings s , s , . . . , s and lets the 1 2 lg( m ) strings r be the bitwise binary xors of m distinct subsets of these strings. We first j ⊕ show that the r are pairwise independent. Consider two different r ’s: r = s j j j l 1 l ∈ L 1 ⊕ and r = s , where L , L ⊆ { 1 , . . . , lg( m ) } . For n -digit strings z and z , we j l 1 2 1 2 2 l ∈ L 2 have [ ] ⊕ ⊕ Pr [ r = z and r = z ] = Pr s = z and s = z j 1 j 2 l 1 l 2 1 2 l ∈ L l ∈ L 1 2 [ ] ⊕ ⊕ ⊕ ⊕ = Pr s ⊕ s = z and s ⊕ s = z l l 1 l l 2 l ∈ L − L l ∈ L ∩ L l ∈ L − L l ∈ L ∩ L 1 2 1 2 2 1 1 2 [ ] ⊕ ⊕ ⊕ ⊕ = Pr s = z ⊕ s and s = z ⊕ s . l 1 l l 2 l l ∈ L − L l ∈ L ∩ L l ∈ L − L l ∈ L ∩ L 1 2 1 2 2 1 1 2 Unless L − L and L − L are both empty, these are clearly independent events that 1 2 2 1 1 each have probability , and it is impossible for L − L and L − L to both be empty, n 1 2 2 1 2 1 since L 6 = L . Thus, the probability is and so the r ’s are indeed independent. 1 2 n j 4 We then have B guess the bits b , b , . . . , b as follows: for each 1 ≤ k ≤ lg( m ), B lets 1 2 m 1 ′ ′ − lg( m ) b be a random bit. The probability that b = b ( x, s ) for all k is then 2 ≥ . k k k 2 m ⊕ ⊕ ′ For each 1 ≤ j ≤ m , if r is defined as s , let b = b . Then, conditional j l j l l ∈ L l ∈ L j j ′ on b = b ( x, s ) for all k , we have b = b ( x, r ). This is because for any strings x , y , k j j 1 k y of length n , we have 2 n n ⊕ ⊕ b ( x, y ⊕ y ) = x ∧ ( y ⊕ y ) = ( x ∧ y ) ⊕ ( x ∧ y ) = b ( x, y ) ⊕ b ( x, y ) , 1 2 1 2 1 2 1 2 i =1 i =1 and we get b = b ( x, r ) inductively. Thus, B has the right values b with probability j j j 1 at least . 2 m (f) The probability that B inverts f on input x for a random x is at least the probability that x ∈ S times the probability that B inverts f conditional on x ∈ S . The first 1 1 1 probability is at least and the second probability is at least times , where the 2 2 m 2 2 ⌊ ⌋ 2 n 4 n is conditional on m ≥ . Setting m = (or any value that must be greater than 2 2 12

3 2 n ), we find that B inverts f with probability at least , which is a non-negligible 2 3 n function of n . This is a contradiction, since f is a one-way function. Therefore, b ( x, y ) is a hard-core bit of g , and our theorem is proven. Problem 7.3. Suppose that f is bijective. Suppose that g ( x ◦ y ) = g ( x ◦ y ). Then 1 1 2 2 f ( x ) = f ( x ) and y = y . Since f is bijective, we have x = x , so x ◦ y = x ◦ y . Clearly 1 2 1 2 1 2 1 1 2 2 on an input of length n , g outputs a string of length n . For each n , then, g is an injective 2 n 2 n function from { 0 , 1 } to { 0 , 1 } (two sets of the same size), which means that g is bijective. Thus, g is a one-way permutation. Let f be a one-way permutation. Then g as in the theorem is a one-way function with the specified hard-core bit. The fact that f is a one-way permutation tells us that g is a one-way permutation as well. Therefore, the theorem still holds with “function” replaced in its statement with “permutation.” 8. Constructing PRGs 8.1. Overview Problem 8.1. Assume for contradiction that there exists a distinguisher D such that | Pr [ D ( f ( x ) ◦ b ( x )) = 1] − Pr [ D ( U ) = 1] | ≥ ( n ) n +1 for a non-negligible function ( n ), where x = U . (Assume D outputs 0 or 1; otherwise n change D so it outputs 0 whenever it outputs something other than 1.) Now, since f is a permutation, the distribution of f ( x ) is the uniform distribution on n -bit strings. Thus, Pr [ D ( U ) = 1] = Pr [ D ( f ( x ) ◦ U ) = 1] , n +1 1 1 where x = U (and U is either 0 or 1, each with probability ). Note that n 1 2 [ ] 1 1 Pr [ D ( f ( x ) ◦ U ) = 1] = Pr [ D ( f ( x ) ◦ b ( x )) = 1] + Pr D ( f ( x ) ◦ b ( x )) = 1 , 1 2 2 where b ( x ) represents the complement of b ( x ). Combining these three equations gives ∣ [ ]∣ ∣ ∣ Pr [ D ( f ( x ) ◦ b ( x )) = 1] − Pr D ( f ( x ) ◦ b ( x ) = 1 ≥ 2 ( n ) . ∣ ∣ Without loss of generality, assume that the second probability is larger than the first one. Suppose that c = U . We have 1 [ ] 1 Pr [ D ( f ( x ) , b ( x ) ⊕ c ) = c ] = (Pr [ D ( f ( x ) , b ( x )) = 0] + Pr D ( f ( x ) , b ( x )) = 1 ) 2 [ ] 1 = (1 − Pr [ D ( f ( x ) , b ( x )) = 1] + Pr D ( f ( x ) , b ( x )) = 1 ) 2 1 1 ≥ (1 + 2 ) = + . 2 2 13

Thus, define the following adversary A : on input f ( x ), A uniformly randomly generates c ∈ { 0 , 1 } and outputs D ( f ( x ) , c ) ⊕ c . As we have shown, A outputs b ( x ) correctly more than negligibly more than half the time, so b is not a hard-core bit, a contradiction. Therefore, H is a pseudorandom generator, as desired. Suppose a one-way permutation f exists. Then via Theorem 7.3.2 (and Problem 7.3) we can construct a one-way permutation g (except that it only takes even-length inputs). This corresponds to a pseudorandom generator H as constructed in this problem. Note: we did not use the fact that f is one-way. The problem statement would be correct without that stipulation; however, if f were a polynomial-time invertible permutation, then from f ( x ) one could compute x and then b ( x ), so b ( x ) would not be a hard-core bit. 8.2. Extending the Stretch of a PRG Problem 8.2. Define the following distributions (perhaps it makes sense to call them random ′ variables) of ( n )-bit strings. (These are called “hybrids” for reasons that will become apparent.) ′ ′ ( n ) − n A = H ( U ) = H ( U ) 0 n n ′ ( n ) − n − 1 A = H ( U ) 1 n +1 ′ ( n ) − n − 2 A = H ( U ) 2 n +2 . . . A ′ = U ′ ` ( n ) − n ` ( n ) ′ Suppose for contradiction that H is not a pseudorandom generator. Then there is an ′ algorithm D that ( n )-distinguishes between A and A for ( n ) non-negligible, meaning 0 ( n ) − n that ∣ [ ]∣ ∣ ∣ ′ Pr [ D ( A ) = 1] − Pr D ( A ) = 1 ≥ ( n ) . 0 ( n ) − n ′ (This follows from the definition of a pseudorandom generator and the way A and A 0 ( n ) − n ′ are defined.) Then clearly (for each n ) there must exist 0 ≤ i < ( n ) such that ( n ) | Pr [ D ( A ) = 1] − Pr [ D ( A ) = 1] | ≥ i i +1 ′ ( n ) − n ( n ) (by the triangle inequality). Define δ ( n ) = , and note that δ ( n ) is non-negligible, since ′ ( n ) − n ′ ( n ) − n is polynomial in n . ′ n +1 We use D to distinguish between U and H ( U ). Define D ( y ) for y ∈ { 0 , 1 } as n + i +1 n + i ′ ′ ( n ) − n − ( i +1) follows: D computes z = H ( y ) (which it can do because H is polynomial-time ′ ′ ′ and ` ( n ) − n − ( i + 1) is polynomial in n ). Then D outputs D ( z ). Note that if D is given ′ a uniform ( n + i + 1)-bit string as input, then z has the distribution of A , while if D i +1 ′ is given H ( U ) as input, then z has the distribution of A . Thus, D δ ( n )-distinguishes n + i i between U and H ( U ). n + i +1 n + i 14

We are almost, but not quite, done, since we need to construct a non-negligible function ′ ′ ( n ) such that we can ( n )-distinguish between H ( U ) and U (non-negligibly distinguish- n n +1 ing between U and H ( U ) isn’t quite what we want because we don’t know anything n + i +1 n + i about i in terms of n ). For each n , let r ( n ) be the smallest positive integer greater than or equal to n such that we can δ ( n )-distinguish between U and H ( U ) (we have proven that r ( n ) is well- r ( n )+1 r ( n ) defined for each n ). Since δ ( n ) is non-negligible, there exists a positive integer k and an 1 ′ infinite sequence of integers n , n , . . . such that δ ( n ) > for each j , and n > ` ( n ) for 1 2 j k j +1 j n j ′ each j . The latter condition makes sure that r ( n ) is distinct for each j . Define ( n ) to be j 0 if there is no n such that r ( n ) = n , and if for some (unique by construction) j we have j j ′ r ( n ) = n , define ( n ) = δ ( n ). j j ′ ′ Clearly for all n , we can ( n )-distinguish between H ( U ) and U : if ( n ) = 0 then n n +1 ′ this is clear, and otherwise we know we can ( n )-distinguish between H ( U ) and U by n n +1 ′ the way we defined (we can δ ( n )-distinguish between H ( U ) and U ). All that remains j n n +1 ′ to show is that is a non-negligible function of n . 1 ′ ′ Suppose for contradiction that is a negligible function of n . Then for all c , ( n ) < c n for n large enough. Let c = k . For n large enough, we have j 1 1 ′ δ ( n ) = ( r ( n )) < ≤ , j j k k ( r ( n )) n j j 9. Improving on Indistinguishability of Encryptions 9.1. CPA Security Problem 9.1. Since E can use randomness, there is no guarantee that E will output a k consistent ciphertext on input m or m . Thus, c may not be equal to the oracle’s output 0 1 for input m or m . 0 1 Problem 9.2. Suppose that an encryption scheme ( G, E, D ) does not satisfy computational indistinguishability of encryptions. Using the guessing definition, we have that there exists a non-negligible function ( n ) and a PPT adversary A such that for every n , A can pick m , m ∈ P , receive E ( m ) for b uniformly random, and output b with probability at least 0 1 n k b 1 ′

• ( n ). Construct an adversary A that simply runs A , ignoring the oracle access. Then 2 1 ′ A (by proxy of A ) picks m and m and outputs b with probability at least + ( n ). Thus, 0 1 2 ( G, E, D ) is not CPA-secure. By contrapositive, if an encryption scheme is CPA-secure, then it satisfies computational indistinguishability of encryptions, as desired. 9.2. Constructing a CPA-Secure Encryption Scheme Problem 9.3. See 6.24-6.25 (pages 222-225) of Katz & Lindell’s Introduction to Modern Cryptography . Problem 9.4. See 3.7.6-3.7.8 (pages 166-169) of Goldreich’s Foundations of Cryptography . 15

Problem 9.5. The decryption algorithm D works as follows: for each i , D computes f ( V + k I i ) and xors the result with c to obtain m . Then the original messages is m ◦· · ·◦ m . For the i i 1 t rest, see 3.24-3.26 (pages 90-93) of Katz & Lindell’s Introduction to Modern Cryptography . 16