A printable PDF is available.

The "graduate student only" problem given in Assignment 2 was not a good choice. You can still work on that as a "challenge problem," but the following question is better, and should be substituted for the original problem.

- [5.] In section 3.4.3 it was shown that PRP-CCA security implies
PRP-CPA security. In this question, you are to consider the
converse: if a family of permutations is PRP-CPA
secure, is it necessarily PRP-CCA secure?
To answer this, consider a family of permutations

*F:{0,1}*(note that^{k}×{0,1}^{k}-> {0,1}^{k}*l=k*) that is secure -- meaning that any adversary that is reasonably bounded on resources has "low" advantage. We don't know, and make no assumptions about, whether**A**dv_{F}^{ prp-cpa}(A)*F*is secure in the PRP-CCA sense.First, use

*F*to define a new family of permutations*G:{0,1}*such that^{k}×{0,1}^{k}-> {0,1}^{k}*G*is secure in the PRP-CPA sense (roughly as secure as*F*), and yet*G*is definitely*not*secure in the PRP-CCA sense.You should clearly define your function

*G*, and then carefully and completely prove two things: that for any adversary*B*,is not much higher than**A**dv_{G}^{ prp-cpa}(B)for some similarly-resourced adversary**A**dv_{F}^{ prp-cpa}(A)*A*, and that there exists an adversary*D*such thatis high (close to 1).**A**dv_{G}^{ prp-cca}(D)After the formal parts, think about what this means, and write out in a few English (non-mathematical) sentences what this really means. Given the choice between two families of permutations, one of which was proven secure in the PRP-CPA sense and one of which was proven secure in the PRP-CCA sense, which would you prefer and why?

*Hint:*What you want to do is make it so that the value of the key is easily extracted from a particular query to the*G*oracle. For example, you could define^{-1}*G*from_{K}(x)*F*in such a way that_{K}(x)*G*. Notice how this allows a CCA adversary to extract the key from a single call to the_{K}(K)=0^{k}*G*oracle, and yet it doesn't necessary help (assuming the rest of it is defined correctly) if all you can query is^{-1}*G*. Defining such a*G*is part of the challenge here (remember that XOR is your friend), and then you need to complete the proofs.