PUMaC 2016 · 加试 · 第 8 题

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