91Ó°ÊÓ

Let \(F\) be a secure PRF with in \(=2 \lambda,\) and let \(G\) be a length-doubling PRG. Define $$ F^{\prime}(k, x)=F(k, G(x)) $$ We will see that \(F^{\prime}\) is not necessarily a PRF. (a) Prove that if \(G\) is injective then \(F^{\prime}\) is a secure PRF.

Show that a 1 -round keyed Feistel cipher eannot be a secure PRP, no matter what its round functions are. That is, construct a distinguisher that successfully distinguishes \(\mathcal{L}_{\text {prp-real }}^{F}\) and \(\mathcal{L}_{\text {prp-rand }}^{F}\), knowing only that \(F\) is a 1-round Feistel cipher. In particular, the purpose is to attack the Feistel transform and not its round function, so your attack should work no matter what the round function is.

Show that a 2 -round keyed Feistel cipher cannot be a secure PRP, no matter what its round functions are. Your attack should work without knowing the round keys, and it should work even with different (independent) round keys.

Show that any function \(F\) that is a 3 -round keyed Feistel cipher cannot be a secure strong PRP. As above, your distinguisher should work without knowing what the round functions are, and the attack should work with different (independent) round functions.

Let \(F\) be a secure PRP with blocklength blen \(=\lambda,\) and consider \(\widehat{F}(k, x)=F(k, k) \oplus F(k, x)\). (a) Show that \(\widehat{F}\) is not a strong PRP (even if \(F\) is). (b) Show that \(\widehat{F}\) is a secure (normal) PRP.