# Questions about using PRF to construct PRG

Let F be a secure pseudorandom function with 128-bit key and 256-bit block length. Which are the following functions G are secure pseudorandom generators? (Select all that apply.)

A. $$G(x)=F_x(0...0)$$, where $$x$$ is a $$128$$-bit input.

B. $$G(x)=F_x(0...0)|| F_x(0...0)$$, where $$x$$ is a $$128$$-bit input.

C. $$G(x)=F_x(0...0)||F_x(1...1)$$, where $$x$$ is a $$128$$-bit input.

D. $$G(x)=F_{0...0}(x)|| F_{1...1}(x)$$, where $$x$$ is a $$256$$-bit input.

The answer our teacher gave is $$A,D$$. But I don't understand. And Why C is wrong?

• I think that your teacher is confused. D is certainly NOT a PRG, but I'll let you work out why. Commented Dec 21, 2020 at 18:12
– moyu
Commented Dec 21, 2020 at 18:40

We don't directly answer homework questions, but will give hints.

An attacker is assumed to have control over all non-secret inputs. The key is secret, the block is not. This answer has a good definition of a PRG: in simple terms a PRG is a function that takes a fixed-length secret input seed bitstring, and outputs a longer bitstring which cannot be distinguished from a random bitstring with non-negligible probability.

A. $$G(x)=F_{x}(0...0)$$, where x is a 128-bit input key.

Does the attacker control any of the inputs? Can the attacker distinguish the output from that of a random function with non-negligible probability (ie, are there any observable patterns in the output)? Is the output longer than the input?

The only input variable is a secret key. No extra patterns get added to the output. How long is the output?

B. $$G(x)=F_{x}(0...0)||F_{x}(0...0)$$, where x is a 128-bit input key.

Same questions.

The only input variable is a secret key. The output repeats some sequence twice. How long is the output?

C. $$G(x)=F_{x}(0...0)||F_{x}(1...1)$$, where x is a 128-bit input key.

Same questions.

The only input variable is a secret key. Does the output have any extra patterns? How long is the output?

D. $$G(x)=F_{0...0}(x)||F_{1...1}(x)$$, where x is a 256-bit input data block.

Same questions.

The only input variable is a public data block. Does the output have any extra patterns? How long is the output?

There's a missing option that continues the pattern: E. $$G(x)=F_{0...0}(x)||F_{0...0}(x)$$, where x is a public 256-bit data block.

If you can answer the A-D, E should be trivial.

• I think this is a bit misleading, D is different from A-C, and is not a PRG - for reasons completely different from "what the adversary can control". Commented Dec 22, 2020 at 21:12
• Oh, doh. That's what I get for editing it in two parts and forgetting an important condition to mention. Commented Dec 22, 2020 at 22:09