1
$\begingroup$

I was asking myself the following question but I'm not really sure if it's in this way:

I have a first $PRG$: $$G_1: \{0,1\}^{\lambda} \rightarrow \{0,1\}^{\lambda+1}$$

Now I want to construct a second $PRG$ that is structured as follows:

$$G: \{0,1\}^{\lambda} \rightarrow \{0,1\}^{2\lambda}$$

Such that ($||$ is the concatenation symbol and for $x_i$ I'm assuming it's the $i^{th}$ bit of $x$:

$$G(x) = x_1||x_2||...||x_{\lambda-1}||G_1(x)$$

I need to prove that $G$ is a $PRG$ if $G_1$ is. But I was thinking that if I can show a third $PRG$ such that: $$G_1 (x)=x_1||x_2||...x_{\lambda/2}||G_2(x_{\lambda/2}||x_{(\lambda/2)+1}||...||x_{\lambda})$$

Right now my question is: since I'm assuming $G1$ is a $PRG$, I can't modify it right? I mean I cannot do the stuff I'm trying to do with $G_2$?

If I continue stepping on $PRGs$($G_2, G_3, ...$)in practice it's still a $PRG$ since it is the $x$ selected as input of the function is indistinguishable from a uniform but string right?

$\endgroup$

1 Answer 1

1
$\begingroup$

I don't think $G$ is a PRG at all. Consider the following distinguisher $D$, which knows the description of $G$, $G_1$, and given a string $s = x_1||x_2|| ...|| x_{2\lambda}$:

  1. The Distinguisher computes $h = G_1(x_1|| ...|| x_{\lambda-1}||0)$ and $h' = G_1(x_1||...|| x_{\lambda-1}||1)$.
  2. $D$ outputs 1 if either $s = x_1||...||x_{\lambda-1}||h$ or $s = x_1||...||x_{\lambda-1}||h'$, and 0 otherwise

Now the property of pseudorandomness should be violated by $D$, since a random string $r \in \{0,1\}^{2\lambda}$ should rarely satisfy $D(r)=1$.

A quote from Katz & Lindell's Introduction to Modern Cryptography section on PRGs:

The seed and its length. The seed for a pseudorandom generator is analogous to the key used by an encryption scheme, and—just as in the case of a cryptographic key—the seed $s$ must be chosen uniformly and be kept secret from any adversary if we want $G(s)$ to look random. Another important point, evident from the above discussion of brute-force attacks, is that $s$ must be long enough so that it is not feasible to enumerate all possible seeds. In an asymptotic sense this is taken care of by setting the length of the seed equal to the security parameter, so exhaustive search over all possible seeds requires exponential time. In practice, the seed length n must at least be large enough so that a brute-force attack running in time 2n is infeasible.

$\endgroup$
2
  • $\begingroup$ Thanks for the answer, you're right, than fro $G$ to become a $PRG$ it should output a negligible part of its initial seed right? $\endgroup$
    – Invited
    Sep 2, 2022 at 7:01
  • $\begingroup$ That sounds promising. Here's an idea worth trying but I can't guarantee it works. Any kind of seed malleability would thwart this. Set $G(x) = G_1(y)||G_1(z) >> 2$ (delete the last 2 bits) where $y$ is the first $\lambda$ bits of $G_1(x)$ and $z$ is the last $\lambda$ bits of $G_1(x)$. $\endgroup$
    – Lev
    Sep 5, 2022 at 21:25

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.