Say $G$ is a $PRG$ that expands its input by a single bit, so we define:
$$G'(x_1||x_2)=G(x_1)||G(x_2)$$
The exercise states to prove that $G'$ is also a PRG.
Now here is my confusion. $PRGs$ are defined for random seeds as input.
But as an adversary I know $G$. So for $x\in\{0,1\}^*$ I could always input
$$x||x$$
And now, I can check if both halves of $G'(x||x)=G(x)||G(x)$ are equal and know that this isn't random.
In the solution they assume that $x_1,x_2$ must be randomly selected as well. But then what is the point of an adversary?
$\begingroup$
$\endgroup$
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
The adversary must not be allowed to choose the seed. (Otherwise, the definition would be trivially unsatisfiable, as the adversary could just check whether the returned string is $G(x)$ for their chosen seed $x$.)
The rationale behind this is that a PRG's seed is understood as (some kind of) a secret key, which the attacker must not be able to know or choose in any threat model. (After all, that's why the secret key is secret. Note that any cryptography trivially breaks when the attacker gets their hand on the key(s).)
By definition, a function $G\colon \{0,1\}^n\to\{0,1\}^{\ell(n)}$ with $\ell(n)>n$ is a pseudorandom generator (PRG) if any polynomial-time adversary is unable to differentiate between a truly random $y\in\{0,1\}^{\ell(n)}$ and the pseudorandom string $G(x)$ for a random seed $x\in\{0,1\}^n$ except for negligible probability.
Intuitively, what this entails is that the output of a PRG, when initialized with a sufficiently random seed, is "just as good" as a real random string.
$\begingroup$
$\endgroup$
0
My assumptions regarding the adversary were wrong!
The adversary doesn't have the ability to request for the output of $G$ on some seed $s$.
The test goes as follows:
- We sample randomly a seed $s$ and compute $s'=G(s)$
- We then give the adversary our $s'$.
- The adversary outputs 1 if $s'$ is in the world of $G$, or 0 otherwise.