Course:Fall 2006 Class Test 1

From CRYPTUTOR

This is the first in-class test for the Fall 2006 introductory course. Given October 25.

Problem 1: Swapping Roles in a PRF:

[5 pts] Give the definition of a pseudorandom generator (PRG).

[10 pts] Let be a PRG. Prove that the following function must also be a PRG:

[5 pts] Give the definition of a pseudorandom function (PRF).

[30 pts] Recall the GGM construction of a PRF F from a PRG , which conceptually uses a large binary tree. To compute F_s(x), we use the key s as the input to the root PRG, and then traverse the tree of PRGs according to the bits of x (use the left k bits of G's output for a 0 and the use the right k bits for a 1).

Now suppose we reverse the roles of s and x in the construction. That is, F_s(x) is the result of giving x as the input to the root PRG and traversing the tree according to the bits of s. Prove that this modified construction does not necessarily yield a PRF.

Hint: What happens if we apply this modified GGM construction to a PRG that looks like G ^* from part 2?

Problem 2: Order of Quantifiers is Important in SIM Definitions:

[50 pts] Recall the definition of SIM-CPA. We usually quantify over PPT adversaries, environments, and simulators. If we restrict ourselves to only deterministic environments, the security does not change (you don't have to show this). Let's see what happens if we also change the order of quantifiers...

Suppose we change the order of quantifiers in the SIM-CPA definition to the following:

Prove that the "encryption scheme" satisfies this modified SIM-CPA security definition, and thus it is not a very meaningful security definition. Proceed by constructing a simulator for an arbitrary adversary and (deterministic) environment. Where do you use the fact that the environment is deterministic?