0
$\begingroup$

Suppose we have a secure PRG $G: \{0,1\}^s→ \{0,1\}^n$ and we define a $G'(k)$ as:

$$ G'(k) = G(k) \| G(k) $$

So if $G(k)=\mathbf{i}$, $G'(k) = \mathbf{i} \| \mathbf{i}$

Is $G'$ still a secure PRG?

Based on my own understanding it should be, because the statistical distinguishers will produce the same analogy of zeros and ones, therefore $G'$ should be a secure PRG too.

Is there any other principle about PRGs that $G'$ does not satisfy?

$\endgroup$
  • 2
    $\begingroup$ How likely is it for a random string to be $x\|x$ for any $x$? $\endgroup$ – SEJPM Feb 15 at 14:18
  • $\begingroup$ I am not sure that I understand your question, but if you mean how likely is it to get G'(k)=k||k, it is impossible. We suppose that G is a secure PRG. I edited the question to make it more clear (hopefully) $\endgroup$ – George Sp Feb 15 at 14:47
  • $\begingroup$ So if $x\|x$ is impossible for a secure PRG, can $G'$ be a secure PRG? $\endgroup$ – SEJPM Feb 15 at 14:49
  • $\begingroup$ I am still not sure I understand, please see my latest edit. $\endgroup$ – George Sp Feb 15 at 14:51
  • $\begingroup$ as @SEJPM said How likely is it for a random string to be x∥x for any x. A good PRNG should not give you any information (except the length, in this case) about the output before generation. $\endgroup$ – Aven Desta Feb 15 at 15:57
2
$\begingroup$

Refering to THIS post

If we call $U_k$ the random variable uniformly distributed over bit strings of length $k$, then a function $g: \{0,1\}^k \to \{0,1\}^m$ is called pseudo-random generator if no feasible(poly-time if you want) algorithm can distinguish $g(U_k)$ and $U_m$ with non-negligible probability.

More formally let $U'_m = g(U_k)$ then the distinguishing advantage of any distinguisher efficient $D$ that we denote as $\Delta^D(U'_m, U_m) = \Pr^{DU_m}[Z = 1] - \Pr^{DU'_m}[Z = 1]$ is negligible.

Here $Z$ is the output of the distinguisher, and negligible is any suitable notion of "really small"; same for efficient.

Now my ability to distinguish between $U_k$ from your PRNG $g: \{0,1\}^k \to \{0,1\}^m \mathbin\| \{0,1\}^m$ is obviously more than negligible. Because any OUTPUT from your generator has symmetry and if I see this symmetry the generator being used is most probably your generator.

| improve this answer | |
$\endgroup$
  • $\begingroup$ So, you can distinguish that "my" generator is used, but what does this tell you about the PRG properties of the new generator G'? Is there another condition that is not met for G' to be a secure PRG? $\endgroup$ – George Sp Feb 15 at 16:51
  • $\begingroup$ The above one is to my opinion the best counter example. But here is a similar question here $\endgroup$ – Aven Desta Feb 15 at 16:57
  • $\begingroup$ I don't think you understand my question. I am asking if this new generator G' is a secure PRG given that it's output is the output of a secure PRG (called G) repeated twice. So it G(k)=i, then G'(k)=ii. My question is, "is G' a secure PRG?" . $\endgroup$ – George Sp Feb 15 at 17:06
  • 1
    $\begingroup$ @GeorgeSp I believe I answered your question. No, your function is not a cryptographically secure PRNG. A secure PRNG should not be distinguishable from a uniformly distributed random variable. Yours is not. If this doesn't answer your question perhaps you should paraphrase it for me, or wait for others to answer. Thanks. $\endgroup$ – Aven Desta Feb 15 at 20:57
1
$\begingroup$

Note that for $G : \{0,1\}^s \to \{0,1\}^{n}$ to be a PRG, $n$ must be some polynomial of $s$, so let's rewrite this as $G : \{0,1\}^s \to \{0,1\}^{\ell(s)}$, where $\ell(s)$ is a polynomial.

To disprove the proposition that your $G' : \{0,1\}^s \to \{0,1\}^{2\cdot\ell(s)}$ is a PRG, it suffices to exhibit a probabilistic polynomial time algorithm (over $s$) that, for random $k$, distinguishes $G'(k)$ from a random bitstring drawn from $\{0,1\}^{2\cdot\ell(s)}$ with non-negligible probability. Given a string $x \in \{0,1\}^{2\cdot\ell(s)}$, here's one such algorithm, which runs in time proportional to $2\cdot\ell(s)$:

  1. Split $x$ in length-$n$ halves $x_1$, $x_2$ such that $x_1 \| x_2 = x$;
  2. If $x_1 = x_2$, then output True; otherwise, output False.

If $x$ was produced by $G'$, then this algorithm is guaranteed to output True. If $x$ is random, the probability that it outputs True is $2^{-\ell(s)}$. The distinguishing advantage is therefore

$$ 1 - 2^{-\ell(s)} $$

which is not a negligible function of $s$. Therefore $G'$ is not a PRG.


In simpler English, the statistical test that checks whether the first half of the input is identical to the second half always succeeds on the output of $G'$.

| improve this answer | |
$\endgroup$
0
$\begingroup$

This is in complement to the other answers. We can look at a concrete example with $G: \{0, 1\} \to \{0, 1\}^2 = \{00, 01, 10, 11\}$ and $G(k) = k|k$

A natural game to play is to just try to guess the output of a PRG and see how well we can do. So Let $U_2$ an uniform random generator, so it outputs a 2-bits strings with probability $\frac{1}{4}$. It is clear that no matter the strategy that an adversary $A$ chooses, $A$ only guess correctly with probability $\frac{1}{4}$ when interacting with $U_2$.

Now when interacting with $G$, $A$ can be a bit smarter and only chooses guesses in $\{00, 11\}$. So here $A$ guesses correctly with probability $\frac{1}{2}$.

In other words $A$ has 2 times more chance of guessing the output of $G$ that it would guess the output of $U_2$. This does not sound too good, even if we are building a pseudo random generator. We can generalize this reasoning to any bit length as was done in @Luis Casillas's answer.

Another example, if $G$ was used to generate pads for encryption like in additive stream ciphers, i.e we use $G$ to generate $k$ and encrypt the message $m$ as $c = m \oplus k$.

Then if $m = header|secret$ and somehow(maybe not really realistic) the adversary knows $header$, the $secret$ is no longer secret!

| improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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