2
$\begingroup$

enter image description here

enter image description here For ii) G2 was proven to be a PRG, and it seems the solution for G5 uses G2.

enter image description here

Can someone try and explain to me the solution that I was given? I specially do not understand how to calculate the given probability:

enter image description here

Also, I understand that to proof something wrong you can just give a counterexample. However is there a more formal way of proving it?

$\endgroup$
  • $\begingroup$ Can you explain the term "winning probability"? $\endgroup$ – Martin Rosenau Dec 1 '18 at 8:24
  • $\begingroup$ Could you remove the images, and use MathJax? and please read Counterexample $\endgroup$ – kelalaka Dec 1 '18 at 9:08
  • $\begingroup$ @kelalaka yes sorry, i will try for the next times, its my first post and I am slightly lost. $\endgroup$ – nachofest Dec 1 '18 at 11:52
  • $\begingroup$ @fgrieu I added parts of the question which i skipped, maybe its easier to understand. $\endgroup$ – nachofest Dec 1 '18 at 11:53
  • $\begingroup$ @MartinRosenau well... thats what I am trying to understand too and how it is calculated $\endgroup$ – nachofest Dec 1 '18 at 11:54
4
$\begingroup$

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

  • it is restricted to input $s$ of $G_5$ that has its last bit equal to zero, meaning $s_{|s|}=0$ or equivalently $s$ is assimilated to an even integer, therefore $s$ and $s+1$ are the same bitstring excepts for bit $s_{|s|}$
  • and $G_5$ is built from a PRG of the form $G_2$, itself built from a PRG noted $G$ even though it's output is one bit narrower than $G$ of the problem statement in (v)

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:

  • the distinguisher receives as input the output of the would-be-PRG under test, itself receiving truly random input bits as input;
  • the distinguisher receives truly random bits as input.

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.

$\endgroup$
  • $\begingroup$ perfect! Only one doubt about it, why is $Pr[A(r)=1]=2^{−(n−1)} $ ? $\endgroup$ – nachofest Dec 2 '18 at 21:30
  • $\begingroup$ @nachofest: I have polished the answer to explain that. I now also use $D$ for the distinguisher, which seems more common and avoids confusion between the distinguisher and its advantage. $\endgroup$ – fgrieu Dec 3 '18 at 6:41

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.