# Is this a secure PRG or not?

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?

Replay

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.

Category: cryptanalysis Time: 2016-07-30 Views: 0