Let F: {0, 1}* {0, 1} {0, 1} be a blockcipher. Define E: {0, 1} {0,...

 

Transcribed Image Text:

Let F: {0, 1}* {0, 1}" {0, 1}" be a blockcipher. Define E: {0, 1} {0, 1}" {0, 1}" as EK3 || K2 || K1(X) = EK3(EK2(EK1(X))). Prove that if F is a secure PRP, then so is E. To get you started, here's a reminder of how to approach this proof. Given an adversary A that attacks the PRP-security of E, build an adversary B that attacks the PRP-security of F. (Be mindful of the sets from which the keys are sampled in the PRP-experiment for F and E.) Carefully show that the PRP-advantage of B upperbounds the PRP-advantage of A, by analyzing the probabilility that B "wins" its experiment. When building your adversary B, try to make it as simple as possible, and as parsimonious as possible with respect to its resources. Finally, try to write a nice theorem statement to encapsulate your result. Something like this: Theorem 2 Fix integers n, k> 0 and Let F: {0, 1}* {0, 1}" {0, 1}" be a blockcipher. Define E: {0, 1} {0,1}" {0,1}" as EK3 || K2 || K1(X) = EK3(EK2(EK1(X))). Let A be a PRP- adversary (for attacking E) that has time complexity t and asks at most q oracle queries. Then there exists an adversary B, explicitly given in th proof of this theorem, such that Adv (A) [???] Adv (B) + [???] and where B has time complexity t' = [???] and asks q' = [???] queries. You should be able to fill in the missing values as a result of your analysis. Let F: {0, 1}* {0, 1}" {0, 1}" be a blockcipher. Define E: {0, 1} {0, 1}" {0, 1}" as EK3 || K2 || K1(X) = EK3(EK2(EK1(X))). Prove that if F is a secure PRP, then so is E. To get you started, here's a reminder of how to approach this proof. Given an adversary A that attacks the PRP-security of E, build an adversary B that attacks the PRP-security of F. (Be mindful of the sets from which the keys are sampled in the PRP-experiment for F and E.) Carefully show that the PRP-advantage of B upperbounds the PRP-advantage of A, by analyzing the probabilility that B "wins" its experiment. When building your adversary B, try to make it as simple as possible, and as parsimonious as possible with respect to its resources. Finally, try to write a nice theorem statement to encapsulate your result. Something like this: Theorem 2 Fix integers n, k> 0 and Let F: {0, 1}* {0, 1}" {0, 1}" be a blockcipher. Define E: {0, 1} {0,1}" {0,1}" as EK3 || K2 || K1(X) = EK3(EK2(EK1(X))). Let A be a PRP- adversary (for attacking E) that has time complexity t and asks at most q oracle queries. Then there exists an adversary B, explicitly given in th proof of this theorem, such that Adv (A) [???] Adv (B) + [???] and where B has time complexity t' = [???] and asks q' = [???] queries. You should be able to fill in the missing values as a result of your analysis.