0
$\begingroup$

I've seen this question! from 2 years ago:

Given $F$ is a $PRF$, we define $G$ for an input $x\in\{0,1\}^n$ as follows:

$$G(x) = F_k(x) \oplus F_k(x \oplus 1^s)$$

The question was if $G$ is a $PRG$. I edited the question a bit to fit the answers given back then. The answers stated this isn't a $PRG$ because $$G(x\oplus 1^n)=F_k(x\oplus 1^n)\oplus F_k(x\oplus 1^n \oplus 1^n)=F_k(x\oplus 1^n)\oplus F_k(x)=G(x)$$Now because $x$, the seed, must be random and because the adversary cannot affect the seed in any way. Why wouldn't this be a $PRG$?

For a random uniformly selected $x$ shouldn't the output of $F_k$ on input $x$ and $x\oplus 1^n$ be pseudorandom and thus $F_k(x) \oplus F_k(x \oplus 1^s)$ is also pseudorandom?

Improve this question
$\endgroup$
12
  • $\begingroup$ That question's OP was conflating PRGs with PRFs, which I did not notice that at the time. ​ fkraiem's answer there explains why "Is G a PRG" is ambiguous. ​ ​ ​ ​ $\endgroup$
    – user991
    Jul 30, 2016 at 10:45
  • $\begingroup$ Looks messy to me; the seed of PRG is a key k, x is PRG output. $\endgroup$
    – kludg
    Jul 30, 2016 at 10:46
  • $\begingroup$ so the above G is a PRG? $\endgroup$
    – avivzk2
    Jul 30, 2016 at 10:48
  • $\begingroup$ As I mentioned, that's ambiguous. ​ ​ $\endgroup$
    – user991
    Jul 30, 2016 at 10:48
  • $\begingroup$ I assume $k$ is the random key, whereas $x$ just needs to be a unique nonce. $\endgroup$
    – CodesInChaos
    Jul 30, 2016 at 10:49

1 Answer 1

Reset to default
1
$\begingroup$

I believe you misunderstood the linked question and probably the definition of PRG.

PRG maps a key $K$ (also called seed) of bit length $l$ into a bit sequence $x\in\{0,1\}^n$ of bit length $n$. PRG is secure if the generated bit sequence $x$ is computationally indistinguishable from truly random.

What the answer to the linked question has shown is that the given PRG's output is easily distinguishable from random because two bits in fixed positions of the PRG's output are equal for any key $K$.

PS: Probably the questions like the linked one implicitly assume the following construction that creates PRG from PRF:

Suppose we have a PRF $F:K\times D \to R$ which map keys $K=\{0,1\}^l$ and domain $D=\{0,1\}^n$ into range $R=\{0,1\}^m$. Now, we can build a PRG $G: K\to \{0,1\}^{n+m}$:

$$G(k)[x]=F(k,x)$$

Note that $x$ is an argument of $F$ but not of $G$; on the LHS $x\in\{0,1\}^n$ denotes a position of a bit sequence of length $m$ in PRG output.

In the simplest case $m=1$, that is PRF $F$ outputs just one bit: $R=\{0,1\}$, and $x\in\{0,1\}^n$ denotes bit position in $G$ output.

Improve this answer
$\endgroup$
1
  • $\begingroup$ I understand now what I did wrong! My assumption that $k$ might be secret. But the attacker knows how $G$ operator and therefore must know $k$ too. Maybe it would of worked if $G(x)=F_x(z)$ where $z$ is fixed $\endgroup$
    – avivzk2
    Jul 30, 2016 at 11:20

Your Answer

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

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