Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
For ii) G2 was proven to be a PRG, and it seems the solution for G5 uses G2.
Can someone try and explain to me the solution that I was given? I specially do not understand how to calculate the given probability:
Also, I understand that to proof something wrong you can just give a counterexample. However is there a more formal way of proving it?
I'll be reading the problem statement as
$G$ is a PRG. Decide for each $i$ whether $G_i$ is always a PRG and prove the answer:
(ii) $G_2(s):=G(s_1\ldots s_{|s|-1})\mathbin\|s_{|s|}$
(v) $G_5(s):=G(s)\mathbin\|G(s+1)$ where $+$ denotes addition of binary numbers.
$G_2$ is a PRG. Intuitive argument: if the input of $G_2$ is uniform random bits, then its whole output is indistinguishable from random, because the rightmost bit is directly taken as the rightmost bit of the random input, and all the others bits because they are the output of a PRG seeded with the other input bits (which, critically, are independent). That can be formalized by turning an hypothetical distinguisher for $G_2$ into a distinguisher for $G$ (and showing that the output of $G_2$ is wider than its input, and whatever other technicality is required by the definition of PRG).
The solution quoted starts with
For every $s$ whose last bit equals zero we have that $G_2(s)\mathbin\|G_2(s+1)=$ $G(s_1\ldots s_{|s-1|})\mathbin\|0\mathbin\|G(s_1\ldots s_{|s-1|})\mathbin\|1$
but that comes without explanation about notation or intent, and with typos.
On notation: a bitstring $s$ of $|s|$ bits is assimilated to an element of $\Bbb Z_{2^{|s|}}$ per the big-endian convention, with bits numbered starting from 1 for the first/left/most significant: $$s=\displaystyle\sum_{i=1}^{|s|}\,s_i\,2^{|s|-i}$$
On intent: It is computed what $G_5$ becomes under two hypothesis
Replacing $G_5$ then $G_2$ by their definition, it comes
$$\begin{align}G_5(s)&=G_2(s)\mathbin\|G_2(s+1)\\ &=G(s_1\ldots s_{|s|-1})\mathbin\|0\mathbin\|G(s_1\ldots s_{|s|-1})\mathbin\|1 \end{align}$$
On typos: in that formula we twice have $|s|-1$ where the question's solution has $|s-1|$.
It should now be intuitively clear that $G_5$ is not necessarily a PRG. That formula shows that if $G_5$ is built from a PRG of the special form $G_2$, and its input has its last bit equal to zero, then the output of $G_5$ has two identical halves, except for their last bit ($0$ for the left half and $1$ for the right half). This characteristic allows to build a good distinguisher (assuming $|s|\ge2$ at the input of $G_5$). We'll prove this in detail.
A distinguisher is a deterministic algorithm $D$ that accepts as input a bistring as wide as the output of the would-be-PRG under test, and outputs 0 or 1. Its advantage $\operatorname{Adv}(D)$ is, by definition, how much in absolute value the probability that it outputs 1 differs in two situations:
As a formula: $\operatorname{Adv}(D)=\big|\,\Pr[D(G(s))=1]-\Pr[D(r)=1]\,\big|$
The left probability is computed over all bitstrings $s$ as wide as the input of the would-be-PRG under test $G$. The right probability is computed over all bitstrings $r$ as wide as the output of $G$. The $|\quad|$ notation stands for absolute value of a real, rather than length of a bitstring $s$ as in $|s|$.
The distinguisher $D$ proposed by the question's solution outputs 1 iff the two halves of its input are identical save for their right bit. When testing a generator $G_5$ of the special form considered, that always occurs when the rightmost bit of the generator's input is $0$, hence $\Pr[D(G_5(s))=1]\ge\frac12$; while if the input of $D$ is $2n$ bits and $n\ge1$, $\Pr[D(r)=1]=2^{-(n-1)}$ (because in the experiment computing that probability, it is compared two random independent bitstrings of $n-1$ bits). Therefore $\operatorname{Adv}(D)\ge\big|\,\frac12-2^{-(n-1)}\,\big|=\frac12\left(1-2^{-(n-2)}\right)$, which is a sizable advantage (at least $\frac14$ for $n\ge3$ ).
The proposed solution states at least $\frac12\left(1-2^{-(n-1)}\right)$, which is a better advantage. That's reachable, but requires computing the advantage exactly, or/and a better distinguisher, which is left as an exercise to the reader.
I understand that to prove something wrong you can just give a counterexample. However is there a more formal way of proving it?
Counterexample is the simplest and most formal way of disproving something. In cryptography, its the best. There are exceptions in other domains.
