7
$\begingroup$

Is the following statement true:

If $G: \{0,1\}^k \to \{0,1\}^n$ is a PRG, then so is $G':\{0,1\}^{k+l} \to \{0,1\}^{n+l}$ defined by $$G'(x||x')=G(x)||x'$$ where $x \in \{0,1\}^k$ and $x' \in \{0,1\}^l$ (where $||$ denotes concatenation).

My thought is that since $x'$ is not processed through the pseudo number generator, then this statement is false. Is my analysis correct?

$\endgroup$
2
  • $\begingroup$ What about using bar $|$ for concatenation? Is $.$ commonly used? $\endgroup$ Sep 23, 2011 at 13:12
  • $\begingroup$ I suppose the formal proof depends on your definition of PRG, but your intuition looks right. $\endgroup$ Sep 23, 2011 at 13:43

2 Answers 2

8
$\begingroup$

If you use a concrete-security definition of security for a PRG, then this statement is true. The proof is a good exercise. If you know enough to pose the problem and to understand the definition of security for a PRG, you should be able to find the reduction proof without difficulty. Start by tracing out what the definition is saying.

A general comment on your analysis: Your analysis makes it sound like you are trying to guess at the answer. Guesses are good, but then you should follow them up with proof. In cryptography, our intuition can often be wrong. Therefore, the accepted standard is a proof. In particular, if you guess that the statement is true, your next step should be to try to prove it; if you guess that the statement is false, your next step should be to find an attack that disproves it. Give it a try! This is a fun problem, and not too hard.

P.S. This looks very much like a standard homework question. I don't know whether it is or not, so I'll just say this. If you are using this web site to answer homework questions, you are not only cheating your fellow students, you are also cheating yourself of the chance to learn the material. To learn cryptography, you must grapple with the problems and try to solve them on your own. You'll only learn through undergoing the process yourself; you won't learn nearly as much by reading other people's solutions. Think of it like learning to ride a bicycle: you can't learn to ride a bicycle by watching someone else ride it. Instead, you have to get on the bicycle yourself, accept that you'll fall or stumble a few times, and work through it.

$\endgroup$
4
$\begingroup$

A few definitions could assist: are $x$ and $x'$ random elements of $\{0,1\}^k$ and $\{0,1\}^l$?

Is $G$ a cryptographically-secure PRG or a PRG with some statistical properties?

Let $\mathcal{D}$ be a PPT-distinguisher and $r$ be a uniformly random bitstring of length $k+l$. A common definition (e.g. from Katz-Lindell book) of a PRG includes the following condition :

$| \mathrm{Pr}[\mathcal{D}(r)=1] - \mathrm{Pr}[\mathcal{D}(G'(x||x'))=1] | \leq \mathsf{negl}(k+l)$

Essentially it says, can you tell the difference between the output of the PRG and a uniformly random string?

$G'$ is not secure under this definition.

For example, consider if $\mathcal{D}$ mounts an exhaustive search. This initially appears to not work since it takes exponential time. But $\mathcal{D}$ only needs to search for values of $x$ since it knows $x'$ from the output $G(x||x')$. Therefore the time is exponential in only $k$, not in $k+l$. That is not good enough for $\mathsf{negl}(k+l)$.

$\endgroup$
2
  • 2
    $\begingroup$ This answer is technically correct if you use the asymptotic definition of PRG, but only if $\ell$ is superpolynomially larger than $k$. Moreover, in practice the asymptotic definition of PRG is not a good one; and if you use a concrete-security definition of PRG, then you find the construction is secure. $\endgroup$
    – D.W.
    Sep 26, 2011 at 4:29
  • $\begingroup$ Note that this is somewhat similar to the "padding-argument" in CS theory. With the asymptotic complexity approach, while adding the $l$ extra bits doesn't fundamentally change the randomness of the overall output (assuming they're drawn uniformly), its presence in the input allows enough margin to break the input seed. $\endgroup$
    – 1110101001
    Mar 12 at 0:19

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.