5
$\begingroup$

Let $G:\{0,1\}^{*} \mapsto \{0,1\}^{*}$ be a secure PRG. Prove or disprove that the following construction also yields a secure PRG. $$G'(k) = G(k||0),$$ where $||$ denotes the concatenation of two strings.

I understand that proving/disproving such constructions usually involves a proof by reduction or a counterexample. Intuitively, I would say that $G'$ is a secure PRG, since we only fix a bit of the input, which should not make the output distinguishable (in polynomial time). However, for some reason I can't finde the right reduction, since I don't see how a $w \in \{0,1\}^{*}$ and a distinguisher $D'$ for $G'$ can be used to construct a distinguisher for $D$ for $G$.

So is $G'$ a secure PRG? If yes, how can I construct a valid reduction and if no, how does a distinguisher for $G'$ work?

I don't know if it is appropriate, but I would prefer hints, which point me in the right direction instead of complete solutions.

Improve this question
$\endgroup$
5
  • 1
    $\begingroup$ Is the input space of your PRG really $\{0,1\}^*$? If so, what's the distribution of the inputs? (It can't be uniform, since there is no uniform distribution over $\{0,1\}^*$.) $\endgroup$
    – Ilmari Karonen
    Commented Oct 27, 2013 at 18:09
  • $\begingroup$ @Ilmari : $\:$ The distribution of the inputs is uniform on $\{\hspace{-0.01 in}0,\hspace{-0.04 in}1\hspace{-0.03 in}\}^n$, and security is that the amount a $\hspace{.4 in}$ feasible adversary can distinguish by is a negligible function of $n$. $\;\;\;\;$ $\endgroup$
    – user991
    Commented Oct 27, 2013 at 21:57
  • 1
    $\begingroup$ Much bigger hint: $\:$ What happens if the last bit of G's output is always equal to the last bit of G's input? $\;$ $\endgroup$
    – user991
    Commented Oct 27, 2013 at 22:08
  • $\begingroup$ @RickyDemer No that didn't do it as it was written as a comment instead of an answer :P $\endgroup$
    – Maarten Bodewes ♦
    Commented Oct 30, 2013 at 16:34
  • $\begingroup$ @RickyDemer Could somebody either please answer or delete this question? $\endgroup$
    – Maarten Bodewes ♦
    Commented Nov 3, 2013 at 21:22

1 Answer 1

Reset to default
0
$\begingroup$

If there exists a secure PRG, then there is a secure PRG
whose last bit of output is always equal the last bit of its input.
If the last bit of G's output is always equal to the last bit of G's input, then the
function G' constructed as described in the question will not be a secure PRG.

Improve this answer
$\endgroup$

Your Answer

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

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