2
$\begingroup$

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?

Improve this question
$\endgroup$
2
  • 4
    $\begingroup$ I think that your teacher is confused. D is certainly NOT a PRG, but I'll let you work out why. $\endgroup$
    – Yehuda Lindell
    Commented Dec 21, 2020 at 18:12
  • $\begingroup$ Thanks a lot, waiting for your answer $\endgroup$
    – moyu
    Commented Dec 21, 2020 at 18:40

1 Answer 1

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ 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". $\endgroup$
    – ambiso
    Commented Dec 22, 2020 at 21:12
  • $\begingroup$ Oh, doh. That's what I get for editing it in two parts and forgetting an important condition to mention. $\endgroup$
    – SAI Peregrinus
    Commented Dec 22, 2020 at 22:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.