Is this a secure PRG

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?


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$.

Category: pseudo random function Time: 2016-07-30 Views: 0

Related post

iOS development

Android development

Python development

JAVA development

Development language

PHP development

Ruby development


Front-end development


development tools

Open Platform

Javascript development

.NET development

cloud computing


Copyright (C), All Rights Reserved.

processed in 0.134 (s). 12 q(s)