I've been looking at the definition of a PRG, here. This is a broader notion than a cryptographically secure PRG ("CSPRG"), which is described here. I am realizing that I am very confused by this first definition - which I want to understand before I get to the second.

Basically, my question is this: If $f: \mathbb{Z}^+ \to \{0,1\}$ (where $\mathbb Z^+$ is the positive integers) what stops the following from being a PRG?

$$ f(x) = x \pmod 2 $$

Before you laugh, let me write a version of this in terms of the definition at that first link. Notice that there, a PRG is defined mapping $\mathbb{Z}^+$ to the reals, $\mathbb R$. So, I will modify my example using the definition of terms given there.

Assume that we start out with a function $g$ satisfying that definition of a PRG, $g: \mathbb{Z}^+ \to \mathbb R$ and the distribution $$ P(x) = \begin{cases} 1 &x\in[0,1) \\ 0 &x\notin[0,1) \end{cases} $$ That is, we have a uniform distribution on $[0,1)$. Now, let's construct a new function $f$ from $g$, and I will show that $f$ also satisfies the definition of a PRG: $$ f(x) = \begin{cases} g(x) & x\equiv 0 \pmod 2 \\ g(x)+1 & x\equiv 1 \pmod 2 \end{cases} $$ Now, define the distribution $Q$ as $$ Q(x) = P(x/2)/2 = \begin{cases} 1/2 & x\in[0,2) \\ 0 & \text{else} \end{cases}$$

Thus $Q$ is a uniform distribution on $[0,2)$.

Consider a set $E \subseteq [0,2)$. We want to show that the measure of the set $f^{-1}(E)$, restricted to the first $n$ elements of $\mathbb{Z}^+$ is close to the measure of $E$ in $[0,2)$, for $n$ large enough. (Again, see the definition at that first link.)

Let's write $E = E_0 \sqcup E_1$ (meaning disjoint union), where $E_i = E \cap [i,i+1)$

Then: $$ f^{-1}(E) = f^{-1}(E_0) \sqcup f^{-1}(E_1). $$ Since the output of $f$ looks like

$$g(0), g(0) + 1, g(1), g(1) + 1, g(2), g(2) + 1, \dots$$ We have that $$ f^{-1}(E_0) = 2 * g^{-1}(E_0) \\f^{-1}(E_1) = [2 * g^{-1}(E_1 - 1)] + 1 $$ Where, for $S$ a subset of $\mathbb Z ^ +$ or $\mathbb R$, $2*S$ is the set consisting of each element of $S$ multiplied by $2$. Similarly for $S \pm 1$.

Now, let's additionally allow $|S|$ to stand for the measure of the set $S$ and, when $S\subset \mathbb Z ^ +$, let $\#S$ be the number of elements in $S$. Then:

$$ \# [f^{-1}(E) \cap [1,2n]] = \# [g^{-1}(E_0) \cap [1,n]] + \# [g^{-1}(E_1 - 1) \cap [1,n]] $$ By definition of $g$ as a PRG, when $n$ is large enough:

$$ \#[g^{-1}(E_0) \cap [1,n]]/n \approx |E_0| \\ \#[g^{-1}(E_1 - 1) \cap [1,n]]/n \approx |E_1 - 1| $$ Here $\approx$ means within $\epsilon$, as described in the definition. Also, the measures $|E_0|$, $|E_1 - 1|$ are taken with respect to the uniform distribution on the unit interval.

So therefore, $$ \#\left[f^{-1}(E) \cap [1,2n]\right]/2n \approx (|E_0| + |E_1 - 1|)/2 $$

But the latter is just the measure of $E = (E_0 \sqcap E_1)$ taken with respect to the uniform distribution on the interval $[0,2)$. Therefore, $f$ is a PRG.

How can this be?? $f$ is just jumping back and forth, regularly from one interval to the other. While the even numbers have some randomness, the odd values just repeat it.

  • 2
    $\begingroup$ Welcome to CSE. Quick note: to write $f:\mathbb Z^+\mapsto\{0,1\}$, you can use $f:\mathbb Z^+\mapsto\{0,1\}$. As far as I can tell, $f:\mathbb Z^+\mapsto\{0,1\}, x\mapsto f(x)=x\bmod2$ indeed is a PRG by your first definition, which does not seem concerned about predictability, only good distribution. That is NOT the definition used by a cryptographer, which is in term of the (low) advantage an adversary can get in a game where the objective is to determine if some output is produced by the would-be CSPRG, or truly at random. $\endgroup$
    – fgrieu
    Feb 4, 2014 at 10:17
  • 1
    $\begingroup$ fgrieu's comment above is a good answer to the question. $\endgroup$
    – K.G.
    Feb 4, 2014 at 14:43
  • $\begingroup$ The answers to "Definition of a CSPRNG" and "How exactly is “true randomness” defined in the realms of cryptography?" might explain some of it too. $\endgroup$
    – e-sushi
    Feb 4, 2014 at 17:47


Your Answer

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