PUMaC 2016 · 加试 · 第 9 题

Problem 9.2. (7 points) Prove that if an encryption scheme is CPA-secure, then it satisfies com- putational indistinguishability of encryptions. 9.2 Constructing a CPA-Secure Encryption Scheme This section consists of three problems that will, together, show you how to construct a CPA-secure encryption scheme from a PRG. All three problems are hard, so don’t be discouraged if you can’t 21 solve them. But first, a definition. Definition 9.2.1. For n ≥ 0, let I be a set of keys (called the key index space ). Let ( n ) : N → N n ⋃ be a function (usually ` ( n ) = n though we’ll see one case where ` ( n ) = 2 n ). Let F = F , n n ≥ 0 where ` ( n ) ` ( n ) F = { f : { 0 , 1 } → { 0 , 1 } } . n k k ∈ I n F is a family of pseudorandom functions (for short we say that F is a PRF) if: n • There is a PPT algorithm G such that G (1 ) generates a key k ∈ I (not necessarily uniformly n at random from I ). n • Given k ∈ I , f is computable in polynomial time. n k ⋃ 21 In the definition and throughout this section, denotes the union of the stated set for all n ≥ 0. n ≥ 0 PUMaC 2016 Power Round Page 20 • There exists a negligible function neg( n ) such that for all n , for every PPT algorithm D , ∣ [ ] [ ]∣ ∣ ∣ f ( · ) f ( · ) n k Pr D = 1 − Pr D (1 ) = 1 ≤ neg( n ) , ∣ ∣ n where the first probability is for k randomly generated by G (1 ) and the second probability ( n ) is for a function chosen uniformly at random from the set of all functions f : { 0 , 1 } → ` ( n ) f ( · ) { 0 , 1 } . Here D means that D has oracle access to f . Okay, let’s talk about this. A PRF F is an infinite collection of easily-computable length- preserving functions. But F is pseudorandom; think of it this way. You’re given a mysterious input-output machine inside a black box you can’t open. All you can do is put an input into the machine and get out an output (as many times as you want). The function was randomly chosen in one of two ways: either it’s literally a randomly chosen function from the set of functions from ` ( n ) ` ( n ) { 0 , 1 } to { 0 , 1 } , or it’s a function chosen from F by G . Your goal is to try to distinguish n between these two possibilities by outputting 1 with a (non-negligibly) higher probability in one case than in the other. The last (pseudorandom) property of a PRF says you can’t succeed in doing this using a polynomial-time distinguisher.