$G$ is a PRG where $|G(s)| > 2 \cdot |s|$.
- $G'(s) = G(s0^{|s|})$.
- $G'(s) = G(s_1...s_{n/2})$, where $s = s_1...s_n$.
My question here is whether my own proposed solutions are correct and do make sense.
$\begingroup$
$\endgroup$
3
-
$\begingroup$ Often a PRG takes a constant length input, in which case neither of your two $G'$ would make sense. $\endgroup$– otusCommented Aug 19, 2015 at 18:03
-
$\begingroup$ What does that even mean? If you really want to help, could you please explain yourself? Please avoid posting such comments with no explanation at all, otherwise they are totally futile. $\endgroup$– pa5h1nh0Commented Aug 19, 2015 at 18:12
-
$\begingroup$ What I mean is that often $G$ is defined with as $G: \{0,1\}^k \mapsto \{0,1\}^l$ for some constant $k$ (and $l$). In that case you couldn't give it an input of twice (1.) or half (2.) the expected length. $\endgroup$– otusCommented Aug 19, 2015 at 18:17
Add a comment
|
3 Answers
$\begingroup$
$\endgroup$
1
Looks good to me! My intuition is that the PRG property means "random in, random out".
In 1. the input is not random so we get no guarantees - indeed, formally one could take any PRG H with 2s-bit inputs and then define G to be H except on strings where the last s bits are 0, in which case G outputs the all-zero string. Now G is still a PRG, because the probability of hitting one of those modified points is at most $2^{-s}$ which makes a negligible difference overall. But $G'$ is now the function that always outputs the all-zero string.
What I've added here is the step from the intuition to a formal proof: I've given a case where $G$ is provably a PRG (ok, I didn't prove it here, but that's an easy exercise) and $G'$ is provably not a PRG.
In 2. if $s_1 \ldots s_n$ is uniform in $\{0,1\}^n$ then $s_1 \ldots s_{n/2}$ is certainly uniform in $\{0,1\}^{n/2}$. So applying $G$ to this string produces something uniformly distributed in the range of $G$, hence the whole thing is a PRG, just like you said.
-
1$\begingroup$ Perfect! So in the 1st case, your formal proof example is very similar to mine, i.e. if $G$ is a PRG, then $G(x)=G(x_1)||G(x_2)-$ where $x=x_1||x_2,x \leftarrow \{{0,1}\}^{2n},|x_1|=|x_2|-$ is a random looking string. But, for any possible input seed $s$ of the same length, $G'(s)=G(s0^{|s|})=G(s)||G(0^{|s|})$ will always output the same $|s|$-bit rightmost sequence. This clearly shows that such a construction can't possibly be a PRG, right? Thank you btw. $\endgroup$– pa5h1nh0Commented Aug 19, 2015 at 16:30
$\begingroup$
$\endgroup$
2
To expand on my comments, you need to define how $G$ is extended for inputs of different sizes before you can determine whether the resulting $G'$ are PRG or not.
With the definition in your answer that $G(s_1 || s_2) = G(s_1)||G(s_2)$ it is indeed not a PRG, but you could define e.g. $G(s_1 || s_2) = G(s_1 \oplus s_2)$, in which case $G'$ is PRG.
Again, it depends on the definition. Suppose $G(t_1 || t_2) = H(t_1)||H_(t_2)$ for some PRG $H$ with a smaller input size. Now $G$ is PRG for random inputs $s = t_1 || t_2$. Define $G(t_1) = H(t_1)$ and $G'$ is PRG. However, if you define $G(t_1) = G(t_1 || 0^{|t_1|})$ you are back to earlier point and $G'$ is not PRG.
-
$\begingroup$ This is an exercise from katz-lindell book. So what should be the best way of solving it? $\endgroup$– pa5h1nh0Commented Aug 22, 2015 at 7:33
-
1$\begingroup$ @pa5h1nh0, since it's an exercise, finding definitions for both "yes" and "no" which you can prove might give you the most insight. $\endgroup$– otusCommented Aug 22, 2015 at 7:45
$\begingroup$
$\endgroup$
In the first case, I would say that $G'$ is not necessarily a PRG because, following from the definition of a PRG, the input seed $w = s0^{|s|}$ to $G$ is not random, so the output can't possibly be pseudorandom: the leftmost $n = |s|$ bits of $w$ correspond to a random seed $s$, but the rightmost $n$ bits are all fixed to $0$. Furthermore, the $G(x)||G(y)$ concatenation $- \enspace x,y \leftarrow \{{0,1}\}^n$, $x \neq y \enspace -$ corresponds to the concatenation of 2 random looking strings; however, the $G(x')||G(y')$ concatenation, where $x' = s$ and $y' = 0^n$, doesn't correspond to the concatenation of 2 random looking strings, as the input seed $y'$ is not random.
In the second case, $G'$ could be a PRG because, following from the definition of a PRG: (1) [expansion] $|G(s_1...s_{n/2})| > 2 \cdot n/2 = n$, so $|G'(s)| > |s|$; (2) [pseudo-randomness] if $s$ is a randomly chosen seed, and $G$ is a PRG, then $s_1...s_{n/2}$ is a random string and $G(s_1...s_{n/2})$ is indistinguishable from a truly random string $y \leftarrow \{{0,1}\}^{l(n)}$, where $l(n) = |G'(s)|$.
In case there are any mistakes or not clear enough, please specify where am I wrong and argue why.