2
$\begingroup$

I am attending the video lectures from Prof Dan Boneh. He gives the following example.

Let $G:\mathcal K\longrightarrow \Bbb Z_2^n$ be a PRG with the property that from the last $\frac{n}{2}$ digits of $G(k)$ we can easily compute the first $\frac{n}{2}$ digits of $G(k)$. We want to show that $G$ is predictable for some $i\in\{0,\dots,n-1\}$.

Well, it is clear that we should use the contrapositive of Yao's Theorem. That is, if we prove that $G$ is not secure, then $G$ is predictable.

To do so, we have to define a statistical test $B:\Bbb Z_2^n\longrightarrow \Bbb Z_2$, and show that the advantage $$\mathrm{Adv_{PRG}}(B,G):=|\mathrm{Pr}_{k\overset{R}{\leftarrow} \mathcal K}(B(G(k))=1)-\mathrm{Pr}_{k\overset{R}{\leftarrow} \mathbb{Z_2^n} }(B(r)=1)|\in [0,1] $$ is non-negligible.

So, my question is what the statistical test $B$ could be?

Improve this question
$\endgroup$
1
  • 2
    $\begingroup$ HINT: If someone came to you with $n$ bits from $G$, but was worried that they might have become garbled, how would you check for garbling? $\endgroup$
    – Daniel S
    Mar 14 at 7:28

0

Reset to default

Your Answer

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