}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}(C)+\leavevmode\hbox
to11.37pt{\vbox to11.37pt{\pgfpicture\makeatletter\hbox{\hskip
5.68657pt\lower-5.68657pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{5.48657pt}{0.0pt}\pgfsys@curveto{5.48657pt}{3.03018pt}{3.03018pt}{5.48657pt}{0.0pt}{5.48657pt}\pgfsys@curveto{-3.03018pt}{5.48657pt}{-5.48657pt}{3.03018pt}{-5.48657pt}{0.0pt}\pgfsys@curveto{-5.48657pt}{-3.03018pt}{-3.03018pt}{-5.48657pt}{0.0pt}{-5.48657pt}\pgfsys@curveto{3.03018pt}{-5.48657pt}{5.48657pt}{-3.03018pt}{5.48657pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-2.5pt}{-3.22221pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{3}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}(C)\geq 1/2+1/(2p(n))$
or $\leavevmode\hbox to11.37pt{\vbox
to11.37pt{\pgfpicture\makeatletter\hbox{\hskip 5.68657pt\lower-5.68657pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{5.48657pt}{0.0pt}\pgfsys@curveto{5.48657pt}{3.03018pt}{3.03018pt}{5.48657pt}{0.0pt}{5.48657pt}\pgfsys@curveto{-3.03018pt}{5.48657pt}{-5.48657pt}{3.03018pt}{-5.48657pt}{0.0pt}\pgfsys@curveto{-5.48657pt}{-3.03018pt}{-3.03018pt}{-5.48657pt}{0.0pt}{-5.48657pt}\pgfsys@curveto{3.03018pt}{-5.48657pt}{5.48657pt}{-3.03018pt}{5.48657pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-2.5pt}{-3.22221pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{2}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}(C)+\leavevmode\hbox
to11.37pt{\vbox to11.37pt{\pgfpicture\makeatletter\hbox{\hskip
5.68657pt\lower-5.68657pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{5.48657pt}{0.0pt}\pgfsys@curveto{5.48657pt}{3.03018pt}{3.03018pt}{5.48657pt}{0.0pt}{5.48657pt}\pgfsys@curveto{-3.03018pt}{5.48657pt}{-5.48657pt}{3.03018pt}{-5.48657pt}{0.0pt}\pgfsys@curveto{-5.48657pt}{-3.03018pt}{-3.03018pt}{-5.48657pt}{0.0pt}{-5.48657pt}\pgfsys@curveto{3.03018pt}{-5.48657pt}{5.48657pt}{-3.03018pt}{5.48657pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-2.5pt}{-3.22221pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{4}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}(C)\geq
1/2+1/(2p(n))$. ∎

We now show that we can construct a super-bit from a super-core for some
length-preserving function:

######  Proposition 6.9.

If $b$ is a super-core of function $f:\\{0,1\\}^{n}\to\\{0,1\\}^{n}$ in
${\mathsf{P}}/\sf{poly}$, then $g(x):=f(x)b(x)$ is a super-bit.

###### Proof.

Suppose, for a contradiction, $g$ is not a super-bit. Then there exist a
distinguisher $D$ in ${\mathsf{NP}}/\sf{poly}$, a polynomial $p$, and
infinitely many $n$’s such that:

$\mathbb{P}\left[{D(U_{n+1})=1}\right]-\mathbb{P}\left[{D(g(U_{n}))=1}\right]\geq
1/p(n).$

We define algorithm $\mathcal{A}_{1}$ in ${\mathsf{NP}}/\sf{poly}$ and
algorithm $\mathcal{A}_{2}$ in ${\mathsf{coNP}}/\sf{poly}$ to predict $b$ as
follows: Assume $Y\in\\{0,1\\}^{n}$ is given as input. $\mathcal{A}_{1}$ runs
$D$ on $Y0$ and accepts when $D$ accepts. $\mathcal{A}_{2}$ runs $D$ on $Y1$
and accepts when $D$ rejects. The definitions of
$\mathcal{A}_{1},\mathcal{A}_{2}$ means that $\mathcal{A}_{1}(Y)=D(Y0)$ and
$\mathcal{A}_{2}(Y)=\overline{D(Y1)}$. Now, we have:

$\displaystyle\leavevmode\hbox to11.37pt{\vbox
to11.37pt{\pgfpicture\makeatletter\hbox{\hskip 5.68657pt\lower-5.68657pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{5.48657pt}{0.0pt}\pgfsys@curveto{5.48657pt}{3.03018pt}{3.03018pt}{5.48657pt}{0.0pt}{5.48657pt}\pgfsys@curveto{-3.03018pt}{5.48657pt}{-5.48657pt}{3.03018pt}{-5.48657pt}{0.0pt}\pgfsys@curveto{-5.48657pt}{-3.03018pt}{-3.03018pt}{-5.48657pt}{0.0pt}{-5.48657pt}\pgfsys@curveto{3.03018pt}{-5.48657pt}{5.48657pt}{-3.03018pt}{5.48657pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-2.5pt}{-3.22221pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{1}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}(\mathcal{A}_{1})+\leavevmode\hbox
to11.37pt{\vbox to11.37pt{\pgfpicture\makeatletter\hbox{\hskip
5.68657pt\lower-5.68657pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{5.48657pt}{0.0pt}\pgfsys@curveto{5.48657pt}{3.03018pt}{3.03018pt}{5.48657pt}{0.0pt}{5.48657pt}\pgfsys@curveto{-3.03018pt}{5.48657pt}{-5.48657pt}{3.03018pt}{-5.48657pt}{0.0pt}\pgfsys@curveto{-5.48657pt}{-3.03018pt}{-3.03018pt}{-5.48657pt}{0.0pt}{-5.48657pt}\pgfsys@curveto{3.03018pt}{-5.48657pt}{5.48657pt}{-3.03018pt}{5.48657pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-2.5pt}{-3.22221pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{2}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}(\mathcal{A}_{2})$
$\displaystyle=\mathbb{P}\left[{\mathcal{A}_{1}(f(U_{n}))=b(U_{n})=0}\right]+\mathbb{P}\left[{\mathcal{A}_{2}(f(U_{n}))=b(U_{n})=1}\right]$
$\displaystyle=\mathbb{P}\left[{D(f(U_{n})0)=0\land
b(U_{n})=0}\right]+\mathbb{P}\left[{D(f(U_{n})1)=0\land b(U_{n})=1}\right]$
$\displaystyle=\mathbb{P}\left[{D(f(U_{n})b(U_{n}))=0\land
b(U_{n})=0}\right]+\mathbb{P}\left[{D(f(U_{n})b(U_{n}))=0\land
b(U_{n})=1}\right]$
$\displaystyle=\mathbb{P}\left[{D(f(U_{n})b(U_{n}))=0}\right]$
$\displaystyle=1-\mathbb{P}\left[{D(g(U_{n}))=1}\right],$

and

$\displaystyle\leavevmode\hbox to11.37pt{\vbox
to11.37pt{\pgfpicture\makeatletter\hbox{\hskip 5.68657pt\lower-5.68657pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{5.48657pt}{0.0pt}\pgfsys@curveto{5.48657pt}{3.03018pt}{3.03018pt}{5.48657pt}{0.0pt}{5.48657pt}\pgfsys@curveto{-3.03018pt}{5.48657pt}{-5.48657pt}{3.03018pt}{-5.48657pt}{0.0pt}\pgfsys@curveto{-5.48657pt}{-3.03018pt}{-3.03018pt}{-5.48657pt}{0.0pt}{-5.48657pt}\pgfsys@curveto{3.03018pt}{-5.48657pt}{5.48657pt}{-3.03018pt}{5.48657pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-2.5pt}{-3.22221pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{3}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}(\mathcal{A}_{1})+\leavevmode\hbox
to11.37pt{\vbox to11.37pt{\pgfpicture\makeatletter\hbox{\hskip
5.68657pt\lower-5.68657pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{5.48657pt}{0.0pt}\pgfsys@curveto{5.48657pt}{3.03018pt}{3.03018pt}{5.48657pt}{0.0pt}{5.48657pt}\pgfsys@curveto{-3.03018pt}{5.48657pt}{-5.48657pt}{3.03018pt}{-5.48657pt}{0.0pt}\pgfsys@curveto{-5.48657pt}{-3.03018pt}{-3.03018pt}{-5.48657pt}{0.0pt}{-5.48657pt}\pgfsys@curveto{3.03018pt}{-5.48657pt}{5.48657pt}{-3.03018pt}{5.48657pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-2.5pt}{-3.22221pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{4}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}(\mathcal{A}_{2})$
$\displaystyle=\frac{1}{2}\mathbb{P}\left[{\mathcal{A}_{1}(U_{n})=1}\right]+\frac{1}{2}\mathbb{P}\left[{\mathcal{A}_{2}(U_{n})=0}\right]$
$\displaystyle=\frac{1}{2}\mathbb{P}\left[{D(U_{n}0)=1}\right]+\frac{1}{2}\mathbb{P}\left[{D(U_{n}1)=1}\right]$
$\displaystyle=\mathbb{P}\left[{D(U_{n+1})=1}\right].$

Therefore, for infinitely many $n$’s,

$\leavevmode\hbox to11.37pt{\vbox
to11.37pt{\pgfpicture\makeatletter\hbox{\hskip 5.68657pt\lower-5.68657pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{5.48657pt}{0.0pt}\pgfsys@curveto{5.48657pt}{3.03018pt}{3.03018pt}{5.48657pt}{0.0pt}{5.48657pt}\pgfsys@curveto{-3.03018pt}{5.48657pt}{-5.48657pt}{3.03018pt}{-5.48657pt}{0.0pt}\pgfsys@curveto{-5.48657pt}{-3.03018pt}{-3.03018pt}{-5.48657pt}{0.0pt}{-5.48657pt}\pgfsys@curveto{3.03018pt}{-5.48657pt}{5.48657pt}{-3.03018pt}{5.48657pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-2.5pt}{-3.22221pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{1}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}(\mathcal{A}_{1})+\leavevmode\hbox
to11.37pt{\vbox to11.37pt{\pgfpicture\makeatletter\hbox{\hskip
5.68657pt\lower-5.68657pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{5.48657pt}{0.0pt}\pgfsys@curveto{5.48657pt}{3.03018pt}{3.03018pt}{5.48657pt}{0.0pt}{5.48657pt}\pgfsys@curveto{-3.03018pt}{5.48657pt}{-5.48657pt}{3.03018pt}{-5.48657pt}{0.0pt}\pgfsys@curveto{-5.48657pt}{-3.03018pt}{-3.03018pt}{-5.48657pt}{0.0pt}{-5.48657pt}\pgfsys@curveto{3.03018pt}{-5.48657pt}{5.48657pt}{-3.03018pt}{5.48657pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-2.5pt}{-3.22221pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{2}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}(\mathcal{A}_{2})+\leavevmode\hbox
to11.37pt{\vbox to11.37pt{\pgfpicture\makeatletter\hbox{\hskip
5.68657pt\lower-5.68657pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{5.48657pt}{0.0pt}\pgfsys@curveto{5.48657pt}{3.03018pt}{3.03018pt}{5.48657pt}{0.0pt}{5.48657pt}\pgfsys@curveto{-3.03018pt}{5.48657pt}{-5.48657pt}{3.03018pt}{-5.48657pt}{0.0pt}\pgfsys@curveto{-5.48657pt}{-3.03018pt}{-3.03018pt}{-5.48657pt}{0.0pt}{-5.48657pt}\pgfsys@curveto{3.03018pt}{-5.48657pt}{5.48657pt}{-3.03018pt}{5.48657pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-2.5pt}{-3.22221pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{3}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}(\mathcal{A}_{1})+\leavevmode\hbox
to11.37pt{\vbox to11.37pt{\pgfpicture\makeatletter\hbox{\hskip
5.68657pt\lower-5.68657pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{5.48657pt}{0.0pt}\pgfsys@curveto{5.48657pt}{3.03018pt}{3.03018pt}{5.48657pt}{0.0pt}{5.48657pt}\pgfsys@curveto{-3.03018pt}{5.48657pt}{-5.48657pt}{3.03018pt}{-5.48657pt}{0.0pt}\pgfsys@curveto{-5.48657pt}{-3.03018pt}{-3.03018pt}{-5.48657pt}{0.0pt}{-5.48657pt}\pgfsys@curveto{3.03018pt}{-5.48657pt}{5.48657pt}{-3.03018pt}{5.48657pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-2.5pt}{-3.22221pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{4}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}(\mathcal{A}_{2})=1+\mathbb{P}\left[{D(U_{n+1})=1}\right]-\mathbb{P}\left[{D(g(U_{n}))=1}\right]\geq
1+1/p(n),$

which implies that either $\leavevmode\hbox to11.37pt{\vbox
to11.37pt{\pgfpicture\makeatletter\hbox{\hskip 5.68657pt\lower-5.68657pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{5.48657pt}{0.0pt}\pgfsys@curveto{5.48657pt}{3.03018pt}{3.03018pt}{5.48657pt}{0.0pt}{5.48657pt}\pgfsys@curveto{-3.03018pt}{5.48657pt}{-5.48657pt}{3.03018pt}{-5.48657pt}{0.0pt}\pgfsys@curveto{-5.48657pt}{-3.03018pt}{-3.03018pt}{-5.48657pt}{0.0pt}{-5.48657pt}\pgfsys@curveto{3.03018pt}{-5.48657pt}{5.48657pt}{-3.03018pt}{5.48657pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-2.5pt}{-3.22221pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{1}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}(\mathcal{A}_{1})+\leavevmode\hbox
to11.37pt{\vbox to11.37pt{\pgfpicture\makeatletter\hbox{\hskip
5.68657pt\lower-5.68657pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{5.48657pt}{0.0pt}\pgfsys@curveto{5.48657pt}{3.03018pt}{3.03018pt}{5.48657pt}{0.0pt}{5.48657pt}\pgfsys@curveto{-3.03018pt}{5.48657pt}{-5.48657pt}{3.03018pt}{-5.48657pt}{0.0pt}\pgfsys@curveto{-5.48657pt}{-3.03018pt}{-3.03018pt}{-5.48657pt}{0.0pt}{-5.48657pt}\pgfsys@curveto{3.03018pt}{-5.48657pt}{5.48657pt}{-3.03018pt}{5.48657pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-2.5pt}{-3.22221pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{3}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}(\mathcal{A}_{1})\geq
1/2+1/(2p(n))$ for infinitely many $n$’s or $\leavevmode\hbox to11.37pt{\vbox
to11.37pt{\pgfpicture\makeatletter\hbox{\hskip 5.68657pt\lower-5.68657pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{5.48657pt}{0.0pt}\pgfsys@curveto{5.48657pt}{3.03018pt}{3.03018pt}{5.48657pt}{0.0pt}{5.48657pt}\pgfsys@curveto{-3.03018pt}{5.48657pt}{-5.48657pt}{3.03018pt}{-5.48657pt}{0.0pt}\pgfsys@curveto{-5.48657pt}{-3.03018pt}{-3.03018pt}{-5.48657pt}{0.0pt}{-5.48657pt}\pgfsys@curveto{3.03018pt}{-5.48657pt}{5.48657pt}{-3.03018pt}{5.48657pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-2.5pt}{-3.22221pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{2}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}(\mathcal{A}_{2})+\leavevmode\hbox
to11.37pt{\vbox to11.37pt{\pgfpicture\makeatletter\hbox{\hskip
5.68657pt\lower-5.68657pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{5.48657pt}{0.0pt}\pgfsys@curveto{5.48657pt}{3.03018pt}{3.03018pt}{5.48657pt}{0.0pt}{5.48657pt}\pgfsys@curveto{-3.03018pt}{5.48657pt}{-5.48657pt}{3.03018pt}{-5.48657pt}{0.0pt}\pgfsys@curveto{-5.48657pt}{-3.03018pt}{-3.03018pt}{-5.48657pt}{0.0pt}{-5.48657pt}\pgfsys@curveto{3.03018pt}{-5.48657pt}{5.48657pt}{-3.03018pt}{5.48657pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-2.5pt}{-3.22221pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{4}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}(\mathcal{A}_{2})\geq
1/2+1/(2p(n))$ for infinitely many $n$’s, contradicting the assumption that
$b$ is a super-core of $f$. ∎

Before we establish Proposition 6.11, which is the converse of Proposition
6.9, we need the following auxiliary lemma:

######  Lemma 6.10.

If $g:\\{0,1\\}^{n}\to\\{0,1\\}^{n+1}$ is a strong PRG and define
$f(x)b(x):=g(x)$, where $b(x)$ is the last bit of $g(x)$, then $b$ is a hard-
core of $f\in P/poly$.

###### Proof.

Suppose for contradiction, $b$ is not a hard-core of $f$. Then there exist
$\mathcal{A}$ in ${\mathsf{P}}/\sf{poly}$, a polynomial $p$, and infinitely
many $n$’s such that

$\mathbb{P}\left[{\mathcal{A}(f(U_{n}))=b(U_{n})}\right]\geq 1/2+1/p(n).$

We construct $D$ to break $g$ as follows: Given $Y\in\\{0,1\\}^{n+1}$ as
input, $D$ outputs $1$ if and only if $\mathcal{A}(Y[1..n])=Y[n+1]$. Let $b$
denote a random bit. Then, for infinitely many $n$’s,

$\displaystyle\mathbb{P}\left[{D(g(U_{n}))=1}\right]-\mathbb{P}\left[{D(U_{n+1})=1}\right]$
$\displaystyle=\mathbb{P}\left[{\mathcal{A}(f(U_{n}))=b(U_{n})}\right]-\mathbb{P}\left[{b=\mathcal{A}(U_{n})}\right]$
$\displaystyle\geq 1/2+1/p(n)-1/2$ $\displaystyle=1/p(n).$

∎

Now, we are able to show:

######  Proposition 6.11.

If $g:\\{0,1\\}^{n}\to\\{0,1\\}^{n+1}$ is a super-bit and define
$f(x)b(x):=g(x)$, where $b(x)$ is the last bit of $g(x)$, then $b$ is a super-
core of $f\in{\mathsf{P}}/{\mathsf{poly}}$.

###### Proof.

Suppose, for a contradiction, $b$ is not a super-core of $f$. We present a
proof for the case in which there exist an
$\mathcal{A}\in{\mathsf{NP}}/{\mathsf{poly}}$, a polynomial $p$, and
infinitely many $n$’s such that $\leavevmode\hbox to11.37pt{\vbox
to11.37pt{\pgfpicture\makeatletter\hbox{\hskip 5.68657pt\lower-5.68657pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{5.48657pt}{0.0pt}\pgfsys@curveto{5.48657pt}{3.03018pt}{3.03018pt}{5.48657pt}{0.0pt}{5.48657pt}\pgfsys@curveto{-3.03018pt}{5.48657pt}{-5.48657pt}{3.03018pt}{-5.48657pt}{0.0pt}\pgfsys@curveto{-5.48657pt}{-3.03018pt}{-3.03018pt}{-5.48657pt}{0.0pt}{-5.48657pt}\pgfsys@curveto{3.03018pt}{-5.48657pt}{5.48657pt}{-3.03018pt}{5.48657pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-2.5pt}{-3.22221pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{1}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}(\mathcal{A})+\leavevmode\hbox
to11.37pt{\vbox to11.37pt{\pgfpicture\makeatletter\hbox{\hskip
5.68657pt\lower-5.68657pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{5.48657pt}{0.0pt}\pgfsys@curveto{5.48657pt}{3.03018pt}{3.03018pt}{5.48657pt}{0.0pt}{5.48657pt}\pgfsys@curveto{-3.03018pt}{5.48657pt}{-5.48657pt}{3.03018pt}{-5.48657pt}{0.0pt}\pgfsys@curveto{-5.48657pt}{-3.03018pt}{-3.03018pt}{-5.48657pt}{0.0pt}{-5.48657pt}\pgfsys@curveto{3.03018pt}{-5.48657pt}{5.48657pt}{-3.03018pt}{5.48657pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-2.5pt}{-3.22221pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{3}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}(\mathcal{A})\geq
1/2+1/p(n)$. The proof for the other case is similar.

We define a distinguisher $D$ to break $g$ as follow: Given
$Y\in\\{0,1\\}^{n+1}$ as input, $D$ runs $\mathcal{A}$ on $Y[1\ldots n]$ to
get one output bit $c$ of $\mathcal{A}$. $D$ then outputs $1$ if and only if
$Y[n+1]=0$ and $c=1$.

Then, for infinitely many $n$’s, we have

$\displaystyle\mathbb{P}\left[{D(U_{n+1})=1}\right]-\mathbb{P}\left[{D(f(U_{n})b(U_{n}))=1}\right]$
$\displaystyle=\mathbb{P}\left[{\mathcal{A}(U_{n})=1\land
U_{1}=0}\right]-\mathbb{P}\left[{\mathcal{A}(f(U_{n}))=1\land
b(U_{n})=0}\right]$
$\displaystyle=1/2\cdot\mathbb{P}\left[{\mathcal{A}(U_{n})=1}\right]-(\mathbb{P}\left[{b(U_{n})=0}\right]-\mathbb{P}\left[{\mathcal{A}(f(U_{n}))=0\land
b(U_{n})=0}\right])$ $\displaystyle=\leavevmode\hbox to11.37pt{\vbox
to11.37pt{\pgfpicture\makeatletter\hbox{\hskip 5.68657pt\lower-5.68657pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{5.48657pt}{0.0pt}\pgfsys@curveto{5.48657pt}{3.03018pt}{3.03018pt}{5.48657pt}{0.0pt}{5.48657pt}\pgfsys@curveto{-3.03018pt}{5.48657pt}{-5.48657pt}{3.03018pt}{-5.48657pt}{0.0pt}\pgfsys@curveto{-5.48657pt}{-3.03018pt}{-3.03018pt}{-5.48657pt}{0.0pt}{-5.48657pt}\pgfsys@curveto{3.03018pt}{-5.48657pt}{5.48657pt}{-3.03018pt}{5.48657pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-2.5pt}{-3.22221pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{1}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}(\mathcal{A})+\leavevmode\hbox
to11.37pt{\vbox to11.37pt{\pgfpicture\makeatletter\hbox{\hskip
5.68657pt\lower-5.68657pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{5.48657pt}{0.0pt}\pgfsys@curveto{5.48657pt}{3.03018pt}{3.03018pt}{5.48657pt}{0.0pt}{5.48657pt}\pgfsys@curveto{-3.03018pt}{5.48657pt}{-5.48657pt}{3.03018pt}{-5.48657pt}{0.0pt}\pgfsys@curveto{-5.48657pt}{-3.03018pt}{-3.03018pt}{-5.48657pt}{0.0pt}{-5.48657pt}\pgfsys@curveto{3.03018pt}{-5.48657pt}{5.48657pt}{-3.03018pt}{5.48657pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-2.5pt}{-3.22221pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{3}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}(\mathcal{A})-\mathbb{P}\left[{b(U_{n})=0}\right]$
$\displaystyle\geq 1/2+1/p(n)-\mathbb{P}\left[{b(U_{n})=0}\right].$

Let $1/s(n)=|\mathbb{P}\left[{b(U_{n})=0}\right]-1/2|$. As $g$ is a strong
PRG, $b$ is a hard-core of $g$ by Lemma 6.10. Thus, for every polynomial $q$
(in particular, for $q(n)=2p(n)$) and every sufficiently large $n$,
$1/s(n)\leq 1/q(n)$. Therefore, for infinitely many $n$’s,

$\displaystyle\mathbb{P}\left[{D(U_{n+1})=1}\right]-\mathbb{P}\left[{D(f(U_{n})b(U_{n}))=1}\right]\geq
1/2+1/p(n)-\mathbb{P}\left[{b(U_{n})=0}\right]\geq 1/2p(n).$

∎

By combining Proposition 6.9 and Proposition 6.11, we establish the following
nondeterministic variant of Theorem 6.6.

######  Theorem 6.12.

There is a super-core $b$ of some length-preserving
$f\in{\mathsf{P}}/{\mathsf{poly}}$ if and only if there is a super-bit $g$.

We say a function $f:\\{0,1\\}^{n}\to\\{0,1\\}^{m(n)}$ is _non-shrinking_ if
$m(n)\geq n$ for every $n$. Because (1) $b$ is a super-core of some length-
preserving function if and only if $b$ is a super-core of some non-shrinking
function, and (2) there exists a super-bit if and only if there exist super-
bits (i.e., we can stretch super-bits by [Rud97], we can alternatively state
Theorem 6.12 as:

######  Theorem 6.13.

There is a super-core of some non-shrinking function in
${\mathsf{P}}/{\mathsf{poly}}$ if and only if there are super-bits.

Although we can relax the condition “length-preserving” to “non-shrinking”,
the requirement “non-shrinking” is not redundant because there is an easy
construction of a super-core $b$ of some function $f$ which shrinks its input,
but whether a super-bit exists is unknown. Define $f(x)=x[1]$ and
$b(x)=x[-1]$, then $b$ is a super-core of $f$ as there are only four functions
from $\\{0,1\\}$ to $\\{0,1\\}$, and none of them can predict $b$ given
$f(x)\in\\{0,1\\}$ in the required sense (indeed, $\leavevmode\hbox
to11.37pt{\vbox to11.37pt{\pgfpicture\makeatletter\hbox{\hskip
5.68657pt\lower-5.68657pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{5.48657pt}{0.0pt}\pgfsys@curveto{5.48657pt}{3.03018pt}{3.03018pt}{5.48657pt}{0.0pt}{5.48657pt}\pgfsys@curveto{-3.03018pt}{5.48657pt}{-5.48657pt}{3.03018pt}{-5.48657pt}{0.0pt}\pgfsys@curveto{-5.48657pt}{-3.03018pt}{-3.03018pt}{-5.48657pt}{0.0pt}{-5.48657pt}\pgfsys@curveto{3.03018pt}{-5.48657pt}{5.48657pt}{-3.03018pt}{5.48657pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-2.5pt}{-3.22221pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{1}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}(c)+\leavevmode\hbox
to11.37pt{\vbox to11.37pt{\pgfpicture\makeatletter\hbox{\hskip
5.68657pt\lower-5.68657pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{5.48657pt}{0.0pt}\pgfsys@curveto{5.48657pt}{3.03018pt}{3.03018pt}{5.48657pt}{0.0pt}{5.48657pt}\pgfsys@curveto{-3.03018pt}{5.48657pt}{-5.48657pt}{3.03018pt}{-5.48657pt}{0.0pt}\pgfsys@curveto{-5.48657pt}{-3.03018pt}{-3.03018pt}{-5.48657pt}{0.0pt}{-5.48657pt}\pgfsys@curveto{3.03018pt}{-5.48657pt}{5.48657pt}{-3.03018pt}{5.48657pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-2.5pt}{-3.22221pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{3}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}(c)=\leavevmode\hbox
to11.37pt{\vbox to11.37pt{\pgfpicture\makeatletter\hbox{\hskip
5.68657pt\lower-5.68657pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{5.48657pt}{0.0pt}\pgfsys@curveto{5.48657pt}{3.03018pt}{3.03018pt}{5.48657pt}{0.0pt}{5.48657pt}\pgfsys@curveto{-3.03018pt}{5.48657pt}{-5.48657pt}{3.03018pt}{-5.48657pt}{0.0pt}\pgfsys@curveto{-5.48657pt}{-3.03018pt}{-3.03018pt}{-5.48657pt}{0.0pt}{-5.48657pt}\pgfsys@curveto{3.03018pt}{-5.48657pt}{5.48657pt}{-3.03018pt}{5.48657pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-2.5pt}{-3.22221pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{2}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}(c)+\leavevmode\hbox
to11.37pt{\vbox to11.37pt{\pgfpicture\makeatletter\hbox{\hskip
5.68657pt\lower-5.68657pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{5.48657pt}{0.0pt}\pgfsys@curveto{5.48657pt}{3.03018pt}{3.03018pt}{5.48657pt}{0.0pt}{5.48657pt}\pgfsys@curveto{-3.03018pt}{5.48657pt}{-5.48657pt}{3.03018pt}{-5.48657pt}{0.0pt}\pgfsys@curveto{-5.48657pt}{-3.03018pt}{-3.03018pt}{-5.48657pt}{0.0pt}{-5.48657pt}\pgfsys@curveto{3.03018pt}{-5.48657pt}{5.48657pt}{-3.03018pt}{5.48657pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-2.5pt}{-3.22221pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{4}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}(c)=1/2$ for any
$c:\\{0,1\\}\to\\{0,1\\}$).

At this point, we may want to understand more about the relation between being
one-way and having a super-core for a function $f$. Let’s recall what we know
in the deterministic setting: (1) if $f$ has a hard-core $b$, $f$ is not
necessarily one-way because the possession of a hard-core can be due to an
information loss of $f$, and (2) if $f$ is one-way, then we can construct a
hard-core $b$ of $f^{\prime}(x,y)=(f(x),y)$.

The first point is the same in the nondeterministic setting. The
aforementioned $f(x)=x[1]$ is clearly not one-way but has a super-core
$b(x)=x[-1]$, which is due to a dramatic loss of information. A more
interesting question is whether the $f$ constructed in Proposition 6.11 from a
super-bit $g$ (we have shown $f$ possesses a super-core $b(x)=g(x)[-1]$) is
one-way or not.

######  Open problem 6.14.

If $g$ is a super-bit, is $f(x):=g(x)[1\ldots n]$ ($n=|x|$) a one-way
function?

As for the second point, however, since being a super-core is stronger
requirement than being a hard-core, it is not necessarily true that there is a
“universal” super-core in the sense that some predicate $b$ (e.g.,
$b(x,y)=\langle x,y\rangle$) is a super-core for every
$f^{\prime}(x,y)=(f(x),y)$, where $f:\\{0,1\\}^{n}\to\\{0,1\\}^{m(n)}$ is a
one-way function. Then, a natural question to ask is:

######  Open problem 6.15.

Suppose $f$ is a one-way function. If we want $\langle x,y\rangle$ to be a
super-core of $f^{\prime}(x,y)=(f(x),y)$, what other properties does $f$ need
to have if any?

Rather, as for the second point, we can show that it is impossible for certain
$f$’s to have a super-core, even if they are possibly one-way. Such $f$’s
include certain functions which are “predominantly 1-1” infinitely often. To
state this more precisely, we say $x$ is of type 1 if $|f^{-1}(f(x))|=1$ and
$x$ is of type 2 otherwise. We define $T_{1}(n)$ to be the set of
$x\in\\{0,1\\}^{n}$ of type 1 and $T_{2}(n)$ to be the set of
$x\in\\{0,1\\}^{n}$ of type 2 . Now, we establish:

######  Theorem 6.16.

Given constant integer $c\geq 0$ and $f:\\{0,1\\}^{n}\to\\{0,1\\}^{n+c}$ in
${\mathsf{P}}/\sf{poly}$, if there exists infinitely many $n$’s and a
polynomial $p$ such that,

$\frac{|T_{1}|}{2^{n}}\geq\frac{2^{1+c}}{2^{1+c}+1}+\frac{1}{p(n)},$

then $f$ does not have a super-core.

In particular, when $f$ is length-preserving (i.e., $c=0$), the inequality
becomes:

$\frac{|T_{1}|}{2^{n}}\geq\frac{2}{3}+\frac{1}{p(n)}.$

###### Proof.

Assume $f$ has the stated property. Suppose, for a contradiction, $b$ is a
super-bit of $f$. We construct as follows two algorithms
$\mathcal{A}_{j}(j=0,1)$, in which $\mathcal{A}_{0}$ is co-nondeterministic
and $\mathcal{A}_{1}$ is nondeterministic, to predict $b$: Given
$y\in\\{0,1\\}^{n}$ as input, $\mathcal{A}_{j}$ guesses $x^{\prime}$ such that
$f(x^{\prime})=y$. If $\mathcal{A}_{j}$ fails to guess such an $x^{\prime}$,
it outputs $1-j$. Otherwise, it outputs $b(x^{\prime})$.

We note that if $y=f(x)$ for some $x\in T_{1}$, then there is always exactly
one correct guess $x^{\prime}$ (i.e., $x$ itself) for $\mathcal{A}_{j}$ such
that $f(x^{\prime})=y=f(x)$, and whenever such an $x^{\prime}$ is guessed,
$b(x^{\prime})=b(x)$. Hence, $\leavevmode\hbox to11.37pt{\vbox
to11.37pt{\pgfpicture\makeatletter\hbox{\hskip 5.68657pt\lower-5.68657pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{5.48657pt}{0.0pt}\pgfsys@curveto{5.48657pt}{3.03018pt}{3.03018pt}{5.48657pt}{0.0pt}{5.48657pt}\pgfsys@curveto{-3.03018pt}{5.48657pt}{-5.48657pt}{3.03018pt}{-5.48657pt}{0.0pt}\pgfsys@curveto{-5.48657pt}{-3.03018pt}{-3.03018pt}{-5.48657pt}{0.0pt}{-5.48657pt}\pgfsys@curveto{3.03018pt}{-5.48657pt}{5.48657pt}{-3.03018pt}{5.48657pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-2.5pt}{-3.22221pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{1}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}(\mathcal{A}_{1})=\mathbb{P}[\mathcal{A}_{1}(f(x))=b(x)=0]\geq\mathbb{P}[\mathcal{A}_{1}(f(x))=b(x)=0\land
x\in T_{1}]=\mathbb{P}[b(x)=0\land x\in T_{1}]$, and $\leavevmode\hbox
to11.37pt{\vbox to11.37pt{\pgfpicture\makeatletter\hbox{\hskip
5.68657pt\lower-5.68657pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{5.48657pt}{0.0pt}\pgfsys@curveto{5.48657pt}{3.03018pt}{3.03018pt}{5.48657pt}{0.0pt}{5.48657pt}\pgfsys@curveto{-3.03018pt}{5.48657pt}{-5.48657pt}{3.03018pt}{-5.48657pt}{0.0pt}\pgfsys@curveto{-5.48657pt}{-3.03018pt}{-3.03018pt}{-5.48657pt}{0.0pt}{-5.48657pt}\pgfsys@curveto{3.03018pt}{-5.48657pt}{5.48657pt}{-3.03018pt}{5.48657pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-2.5pt}{-3.22221pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{3}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}(\mathcal{A}_{1})=\frac{1}{2}\mathbb{P}[\mathcal{A}_{1}(y)=1]\geq\frac{1}{2}\mathbb{P}[y=f(x)\land
b(x)=1\text{ for some }x\in T_{1}]$. Similarly, $\leavevmode\hbox
to11.37pt{\vbox to11.37pt{\pgfpicture\makeatletter\hbox{\hskip
5.68657pt\lower-5.68657pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{5.48657pt}{0.0pt}\pgfsys@curveto{5.48657pt}{3.03018pt}{3.03018pt}{5.48657pt}{0.0pt}{5.48657pt}\pgfsys@curveto{-3.03018pt}{5.48657pt}{-5.48657pt}{3.03018pt}{-5.48657pt}{0.0pt}\pgfsys@curveto{-5.48657pt}{-3.03018pt}{-3.03018pt}{-5.48657pt}{0.0pt}{-5.48657pt}\pgfsys@curveto{3.03018pt}{-5.48657pt}{5.48657pt}{-3.03018pt}{5.48657pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-2.5pt}{-3.22221pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{2}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}(\mathcal{A}_{0})\geq\mathbb{P}[b(x)=1\land
x\in T_{1}]$, and $\leavevmode\hbox to11.37pt{\vbox
to11.37pt{\pgfpicture\makeatletter\hbox{\hskip 5.68657pt\lower-5.68657pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{5.48657pt}{0.0pt}\pgfsys@curveto{5.48657pt}{3.03018pt}{3.03018pt}{5.48657pt}{0.0pt}{5.48657pt}\pgfsys@curveto{-3.03018pt}{5.48657pt}{-5.48657pt}{3.03018pt}{-5.48657pt}{0.0pt}\pgfsys@curveto{-5.48657pt}{-3.03018pt}{-3.03018pt}{-5.48657pt}{0.0pt}{-5.48657pt}\pgfsys@curveto{3.03018pt}{-5.48657pt}{5.48657pt}{-3.03018pt}{5.48657pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-2.5pt}{-3.22221pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{4}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}(\mathcal{A}_{0})\geq\frac{1}{2}\mathbb{P}[y=f(x)\land
b(x)=0\text{ for some }x\in T_{1}]$.

Therefore, $\leavevmode\hbox to11.37pt{\vbox
to11.37pt{\pgfpicture\makeatletter\hbox{\hskip 5.68657pt\lower-5.68657pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{5.48657pt}{0.0pt}\pgfsys@curveto{5.48657pt}{3.03018pt}{3.03018pt}{5.48657pt}{0.0pt}{5.48657pt}\pgfsys@curveto{-3.03018pt}{5.48657pt}{-5.48657pt}{3.03018pt}{-5.48657pt}{0.0pt}\pgfsys@curveto{-5.48657pt}{-3.03018pt}{-3.03018pt}{-5.48657pt}{0.0pt}{-5.48657pt}\pgfsys@curveto{3.03018pt}{-5.48657pt}{5.48657pt}{-3.03018pt}{5.48657pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-2.5pt}{-3.22221pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{1}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}(\mathcal{A}_{1})+\leavevmode\hbox
to11.37pt{\vbox to11.37pt{\pgfpicture\makeatletter\hbox{\hskip
5.68657pt\lower-5.68657pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{5.48657pt}{0.0pt}\pgfsys@curveto{5.48657pt}{3.03018pt}{3.03018pt}{5.48657pt}{0.0pt}{5.48657pt}\pgfsys@curveto{-3.03018pt}{5.48657pt}{-5.48657pt}{3.03018pt}{-5.48657pt}{0.0pt}\pgfsys@curveto{-5.48657pt}{-3.03018pt}{-3.03018pt}{-5.48657pt}{0.0pt}{-5.48657pt}\pgfsys@curveto{3.03018pt}{-5.48657pt}{5.48657pt}{-3.03018pt}{5.48657pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-2.5pt}{-3.22221pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{2}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}(\mathcal{A}_{0})+\leavevmode\hbox
to11.37pt{\vbox to11.37pt{\pgfpicture\makeatletter\hbox{\hskip
5.68657pt\lower-5.68657pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{5.48657pt}{0.0pt}\pgfsys@curveto{5.48657pt}{3.03018pt}{3.03018pt}{5.48657pt}{0.0pt}{5.48657pt}\pgfsys@curveto{-3.03018pt}{5.48657pt}{-5.48657pt}{3.03018pt}{-5.48657pt}{0.0pt}\pgfsys@curveto{-5.48657pt}{-3.03018pt}{-3.03018pt}{-5.48657pt}{0.0pt}{-5.48657pt}\pgfsys@curveto{3.03018pt}{-5.48657pt}{5.48657pt}{-3.03018pt}{5.48657pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-2.5pt}{-3.22221pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{3}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}(\mathcal{A}_{1})+\leavevmode\hbox
to11.37pt{\vbox to11.37pt{\pgfpicture\makeatletter\hbox{\hskip
5.68657pt\lower-5.68657pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{5.48657pt}{0.0pt}\pgfsys@curveto{5.48657pt}{3.03018pt}{3.03018pt}{5.48657pt}{0.0pt}{5.48657pt}\pgfsys@curveto{-3.03018pt}{5.48657pt}{-5.48657pt}{3.03018pt}{-5.48657pt}{0.0pt}\pgfsys@curveto{-5.48657pt}{-3.03018pt}{-3.03018pt}{-5.48657pt}{0.0pt}{-5.48657pt}\pgfsys@curveto{3.03018pt}{-5.48657pt}{5.48657pt}{-3.03018pt}{5.48657pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-2.5pt}{-3.22221pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{4}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}(\mathcal{A}_{0})=\mathbb{P}\left[{x\in
T_{1}}\right]+\frac{1}{2}\mathbb{P}\left[{y\in
f(T_{1})}\right]=\frac{|T_{1}|}{2^{n}}+\frac{1}{2}\cdot\frac{|T_{1}|}{2^{n+c}}=\frac{2^{1+c}+1}{2^{1+c}}\cdot\frac{|T_{1}|}{2^{n}}\geq
1+\frac{1}{p(n)}$ for infinitely many $n$’s, but this implies that either
$\leavevmode\hbox to11.37pt{\vbox
to11.37pt{\pgfpicture\makeatletter\hbox{\hskip 5.68657pt\lower-5.68657pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{5.48657pt}{0.0pt}\pgfsys@curveto{5.48657pt}{3.03018pt}{3.03018pt}{5.48657pt}{0.0pt}{5.48657pt}\pgfsys@curveto{-3.03018pt}{5.48657pt}{-5.48657pt}{3.03018pt}{-5.48657pt}{0.0pt}\pgfsys@curveto{-5.48657pt}{-3.03018pt}{-3.03018pt}{-5.48657pt}{0.0pt}{-5.48657pt}\pgfsys@curveto{3.03018pt}{-5.48657pt}{5.48657pt}{-3.03018pt}{5.48657pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-2.5pt}{-3.22221pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{1}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}(\mathcal{A}_{1})+\leavevmode\hbox
to11.37pt{\vbox to11.37pt{\pgfpicture\makeatletter\hbox{\hskip
5.68657pt\lower-5.68657pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{5.48657pt}{0.0pt}\pgfsys@curveto{5.48657pt}{3.03018pt}{3.03018pt}{5.48657pt}{0.0pt}{5.48657pt}\pgfsys@curveto{-3.03018pt}{5.48657pt}{-5.48657pt}{3.03018pt}{-5.48657pt}{0.0pt}\pgfsys@curveto{-5.48657pt}{-3.03018pt}{-3.03018pt}{-5.48657pt}{0.0pt}{-5.48657pt}\pgfsys@curveto{3.03018pt}{-5.48657pt}{5.48657pt}{-3.03018pt}{5.48657pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-2.5pt}{-3.22221pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{3}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}(\mathcal{A}_{1})\geq\frac{1}{2}+\frac{1}{2p(n)}$
or $\leavevmode\hbox to11.37pt{\vbox
to11.37pt{\pgfpicture\makeatletter\hbox{\hskip 5.68657pt\lower-5.68657pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{5.48657pt}{0.0pt}\pgfsys@curveto{5.48657pt}{3.03018pt}{3.03018pt}{5.48657pt}{0.0pt}{5.48657pt}\pgfsys@curveto{-3.03018pt}{5.48657pt}{-5.48657pt}{3.03018pt}{-5.48657pt}{0.0pt}\pgfsys@curveto{-5.48657pt}{-3.03018pt}{-3.03018pt}{-5.48657pt}{0.0pt}{-5.48657pt}\pgfsys@curveto{3.03018pt}{-5.48657pt}{5.48657pt}{-3.03018pt}{5.48657pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-2.5pt}{-3.22221pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{2}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}(\mathcal{A}_{0})+\leavevmode\hbox
to11.37pt{\vbox to11.37pt{\pgfpicture\makeatletter\hbox{\hskip
5.68657pt\lower-5.68657pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{5.48657pt}{0.0pt}\pgfsys@curveto{5.48657pt}{3.03018pt}{3.03018pt}{5.48657pt}{0.0pt}{5.48657pt}\pgfsys@curveto{-3.03018pt}{5.48657pt}{-5.48657pt}{3.03018pt}{-5.48657pt}{0.0pt}\pgfsys@curveto{-5.48657pt}{-3.03018pt}{-3.03018pt}{-5.48657pt}{0.0pt}{-5.48657pt}\pgfsys@curveto{3.03018pt}{-5.48657pt}{5.48657pt}{-3.03018pt}{5.48657pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-2.5pt}{-3.22221pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{4}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}(\mathcal{A}_{0})\geq\frac{1}{2}+\frac{1}{2p(n)}$.
∎

The intuitive reason that such $f$’s do not have a super-core is: such an $f$
preserves most of the information (thus, a unique pre-image can be guessed).In
the theorem, we cannot trivially relax $c$ to an arbitrary polynomial in $n$,
as if we do so, the right-hand side of the inequality in the statement may
exceed $1$. This result can alternatively be proved, when $f$ is length-
preserving, by making use of other results mentioned before, as follows.
Suppose, for a contradiction, $b$ is a super-core of $f$, then
$g(x):=f(x)b(x)$ is a super-bit by Proposition 6.9. However, we can then
easily break $g$ as follows: we witness the randomness of a given
$y\in\\{0,1\\}^{n+1}$ by guessing an $x\in\\{0,1\\}^{n}$ such that
$f(x)=y[1\ldots n]$ and test if $b(x)=y[n+1]$; if $b(x)\neq y[n+1]$, $y$ is
random.

We state a weaker but more concise corollary of Theorem 6.16:

######  Corollary 6.17.

If $f\in{\mathsf{P}}/{\mathsf{poly}}$ is length-preserving and 1-1 (or at
least 1-1 for infinitely many $n$’s), then $f$ does not have a super-core.

This corollary contrasts the result that a length-preserving and 1-1 $f\in
P/poly$ could have a hard-core (in fact, if $b$ is a hard-core of a length-
preserving and 1-1 $f\in P/poly$, then $g(x):=f(x)b(x)$ is a strong PRG
[Gol08]). Thus, the corollary suggests there might be strong PRGs which are
not super-bits.

Besides the above investigation on which functions can or cannot have a super-
core and the relation between being a one-way function and having a super-
core, another central question is:

######  Open problem.

What is a sensible definition of “nondeterministic one-way functions” if any?

Satisfactory answers to 6.14 and 6.15 will shed light on this question. A
possible candidate is “a one-way function that has a super-core”, but this
question needs further exploration.

##  7 Conclusion and future directions

The current work is the first systematic investigation into nondeterministic
pseudorandomness (in the cryptographic regime), building on the primitives
proposed by Rudich [Rud97]. Our investigation reveals a fruitful area of
potential directions. Here, we propose or summarise some intriguing future
directions and open problems that we deem worth pursuing.

  * •

We have provided an algorithm that achieves a sublinear-stretch for any given
demi-bit. If we are greedier, we may wonder if we can stretch more.
Specifically, if we can stretch one demi-bit to linearly many demi-bits, or to
polynomially many demi-bits, or even to a pseudorandom function generator
(PRFG) with exponential demi-hardness. Even if assuming we do have some
$n$-demi-bits $b:\\{0,1\\}^{n}\to\\{0,1\\}^{2n}$, it is still unclear whether
we can construct a PRFG with exponential demi-hardness by any standard
algorithm for constructing PRFGs or a novel one.

  * •

Can we further refine or classify the inequalities in 5.9? Can we also
characterise demi-hardness in terms of unpredictability (i.e., where is the
correct place of demi-hardness in that lattice)?

  * •

One-way functions are one of the most central cryptographic primitives. Then,
a natural question to ask is, what is a sensible definition of
nondeterministic-secure one-way functions? (A first attempt may be “a one-way
function which has a super-core”, but this proposal demands further
verification.)

  * •

If $g$ is a super-bit, is $f(x):=g(x)[1...n]$ ($n=|x|$) a one-way function?

  * •

Suppose $f$ is a one-way function. If we want $\langle x,y\rangle$ to be a
super-core of $f^{\prime}(x,y)=(f(x),y)$, what other properties does $f$ need
to have, if any?

Better answers to the questions listed above would help us to better
understand the hardness of generators in the nondeterministic setting and shed
light on the open problem “whether the existence of demi-bits implies the
existence of super-bits”.

##  Appendix A Demi-bits exist unless PAC-learning of small circuits is
feasible

In this section, we provide a full exposition of Pich’s results from [Pic20],
who developed PAC-learning algorithms from breaking PRGs. These results are
important for the foundations of pseudorandomness against nondeterministic
adversaries since they provide justification for the existence of demi-bits.

###  A.1 PAC-learning

We formulate the following nonuniform version of PAC-learning:

######  Definition A.1 (PAC-learning, nonuniform).

A circuit class $\mathcal{C}$ is learnable (over the uniform distribution) by
a circuit class $\mathcal{D}$ up to error $\varepsilon$ with confidence
$\delta$ if there is a randomized oracle family $L=\\{D_{n}\\}\in\mathcal{D}$
such that for every family $f:\\{0,1\\}^{n}\to\\{0,1\\}$ computable by
$\mathcal{C}$ and every large enough $n$, we have:

  1. 1.

$\underset{w}{\mathbb{P}}[{L^{f}(1^{n},w)\ (1-\varepsilon)\\!-\\!approximates\
f}]\geq\delta$, where $w$ is the random input bits to $L^{f}$ and the output
$L^{f}(1^{n},w)$ of $L^{f}$ is a string representation of an approximator
$f^{\prime}$ of $f$. $L^{f}(1^{n},w)$ can be a description of a uniform or
nonuniform algorithm of the following types: deterministic, nondeterministic,
co-nondeterministic, and randomized.

  2. 2.

For every $f$ and $w$, $L^{f}(1^{n},w)$ is $\mathcal{D}$-evaluable: there is
another circuit family $E\in\mathcal{D}$ such that for every possible output
$L^{f}(1^{n},w)$ of $L$ and every $x\in\\{0,1\\}^{n}$ given as the input to
$E$, $E$ computes $L^{f}(1^{n},w)$ on $x$. When $L^{f}(1^{n},w)$ is
(co-)nondeterministic or randomized, $E$ is allowed to be
(co-)nondeterministic or randomized respectively.

For such a learner $L$, we also say $\mathcal{C}$ is learnable by $L$ or every
$C\in\mathcal{C}$ is learnable by $L$.

Remarks.

  1. 1.

We say $L^{f}$ uses membership query if it somehow selects the set of queries
made to the oracle gates. We say $L^{f}$ uses uniformly distributed random
examples if the set of queries made is sampled uniformly at random. The above
learning model is general enough to admit both kinds of learners and also any
kind of mixture. In this work, we will only consider learners using uniformly
distributed random examples. Thus by “learning”, we always mean learning using
uniformly distributed random examples.

  2. 2.

The defined learning model is also general enough to admit learning over other
distributions (i.e. we change the distribution of $w$ in condition (1)). When
$\mathcal{D}$ contains ${\mathsf{P}}/\sf{poly}$, learning over any
polynomially generated distribution is equivalent to learning over the uniform
distribution.

  3. 3.

A possible source of confusion is to leave out Condition (2). However,
Condition (2) is indispensable here. The reason is that without this
restriction, ${\mathsf{P}}/\sf{poly}$ can be efficiently learned, which is
widely believed not to be the case (e.g., cf. [RS21]). It is an easy exercise
to prove the learnability of ${\mathsf{P}}/\sf{poly}$ without the second
condition by applying the Occam’s Razor theorem established in [BEHW87].
Intuitively, a learner can learn ${\mathsf{P}}/\sf{poly}$ efficiently by
remembering the samples and postponing all the “learning” to the hypothesis
evaluation stage.

  4. 4.

The confidence $\delta$ and accuracy $1-\varepsilon$ of a learner in
$\mathcal{D}$ can be efficiently boosted to constants less than $1$ in
standard ways (cf. [KV94]) when they are not negligible with respect to
$\mathcal{D}$. For example, when $\mathcal{D}=P/poly$, it is sufficient for
$\delta$ and $1-\varepsilon$ to achieve $p(n)$ and $1/2+q(n)$ respectively for
any polynomials $p$ and $q$. Beyond the remark here, boosting will be a
digression from the theme of this work.

###  A.2 Learning based on nonexistence assumptions

We recall a construction from [BFKL94]: for a positive integer $m$ and a
circuit $C:\\{0,1\\}^{n}\to\\{0,1\\}$, define generator
$G_{m,C}:\\{0,1\\}^{mn}\to\\{0,1\\}^{mn+m}$, which maps $m$ $n$-bit strings
$x_{1},...,x_{m}$ to $x_{1},C(x_{1}),...,x_{m},C(x_{m})$.

We reformulate Theorem 7 on average-case learning in [BFKL94] into our PAC-
learning framework as the following lemma:

######  Lemma A.2.

Given a circuit class $\mathcal{C}$, if there is an $m$ and an $s(n)$-size
circuit $D$ such that for every $C\in\mathcal{C}$

$\mathbb{P}\left[{D(y)=1}\right]-\mathbb{P}\left[{D(G_{C}(x))=1}\right]\geq
1/s\text{, where }G_{C}=G_{m,C}\text{,}$

then there is a randomized polynomial time (in $n$ and $|\langle D\rangle|$,
where $\langle D\rangle$ is a given string representation of $D$) algorithm
$L$ that learns $\mathcal{C}$ with confidence $1/2m^{2}s$ up to error
$1/2-1/2ms$.

In particular, if D is a nondeterministic or co-nondeterministic circuit, the
output of L is allowed to be a nondeterministic or co-nondeterministic
algorithm.

###### Proof.

Given any $C\in\mathcal{C}$, $L$ randomly chooses an $i\in[m]$, bits
$r_{1},...,r_{m}$, and n-bit strings $x_{1},...,x_{m}$ except $x_{i}$, queries
$C$ on $x_{1},...,x_{i-1}$ to get $C(x_{1}),...,C(x_{i-1})$, and outputs
$C^{\prime}$, which predicts $C$ as follows: given any $n$-bit input $x_{i}$,
$C^{\prime}$ emulates $D$ on
$(x_{1},C(x_{1}),...,x_{i-1},C(x_{i-1}),x_{i},r_{i},...,x_{m},r_{m})$ to get
an output bit $p_{i}$. If $p_{i}=1$, C’ outputs $\bar{r_{i}}$; if $p_{i}=0$,
C’ outputs $r_{i}$.

We next want to prove that $L$ indeed learns $C$ in the desired sense. Given
random bits $r_{1},...,r_{m}$ and random $n$-bit strings $x_{1},...,x_{m}$, we
define
$p_{i}:=D(x_{1},C(x_{1}),...,x_{i-1},C(x_{i-1}),x_{i},r_{i},...,x_{m},r_{m})$.
Then (note: here we are applying a hybrid argument),

$\displaystyle 1/s$
$\displaystyle\leq\mathbb{P}\left[{D(x)=1}\right]-\mathbb{P}\left[{D(G_{C}(x))=1}\right]$
$\displaystyle=\mathbb{P}\left[{p_{1}=1}\right]-\mathbb{P}\left[{p_{m}=1}\right]$
$\displaystyle=\sum_{i=1}^{m-1}(\mathbb{P}\left[{p_{i}=1}\right]-\mathbb{P}\left[{p_{i+1}=1}\right])$

Hence, there exist i such that
$\mathbb{P}\left[{p_{i}=1}\right]-\mathbb{P}\left[{p_{i+1}=1}\right]\geq
1/ms$, and therefore the $i$ $L$ chooses satisfies
$\mathbb{P}\left[{p_{i}=1}\right]-\mathbb{P}\left[{p_{i+1}=1}\right]\geq 1/ms$
with probability $\geq 1/m$. When $L$ has successfully chosen such an $i$,

$\displaystyle\ \underset{\begin{subarray}{c}r_{1},...,r_{m}\\\
x_{1},...,x_{m}\end{subarray}}{\mathbb{P}}[C^{\prime}(x_{i})=C(x_{i})]$
$\displaystyle=\mathbb{P}\left[{p_{i}=1,r_{i}\neq
C(x_{i})}\right]+\mathbb{P}\left[{p_{i}=0,r_{i}=C(x_{i})}\right]$
$\displaystyle=\frac{1}{2}\mathbb{P}\left[{p_{i}=1|r_{i}\neq
C(x_{i})}\right]+\frac{1}{2}\mathbb{P}\left[{p_{i}=0|r_{i}=C(x_{i})}\right]$
$\displaystyle=\frac{1}{2}\mathbb{P}\left[{p_{i}=1|r_{i}\neq
C(x_{i})}\right]+\frac{1}{2}(1-\mathbb{P}\left[{p_{i}=1|r_{i}=C(x_{i})}\right])$
$\displaystyle=\frac{1}{2}+\frac{1}{2}\mathbb{P}\left[{p_{i}=1|r_{i}\neq
C(x_{i})}\right]-\frac{1}{2}\mathbb{P}\left[{p_{i}=1|r_{i}=C(x_{i})}\right]$
$\displaystyle=\frac{1}{2}+\frac{1}{2}\mathbb{P}\left[{p_{i}=1|r_{i}\neq
C(x_{i})}\right]+(\frac{1}{2}\mathbb{P}\left[{p_{i}=1|r_{i}=C(x_{i})}\right]-\mathbb{P}\left[{p_{i}=1|r_{i}=C(x_{i})}\right])$
$\displaystyle=\frac{1}{2}+(\mathbb{P}\left[{p_{i}=1,r_{i}\neq
C(x_{i})}\right]+\mathbb{P}\left[{p_{i}=1,r_{i}=C(x_{i})}\right])-\mathbb{P}\left[{p_{i}=1|r_{i}=C(x_{i})}\right]$
$\displaystyle=\frac{1}{2}+\mathbb{P}\left[{p_{i}=1}\right]-\mathbb{P}\left[{p_{i+1}=1}\right]$
$\displaystyle\geq\frac{1}{2}+\frac{1}{ms}$

Let $p=\underset{\begin{subarray}{c}r_{1},...,r_{m}\\\
x_{1},...,x_{m}\,except\,x_{i}\end{subarray}}{\mathbb{P}}[\underset{x_{i}}{\mathbb{P}}[C^{\prime}(x_{i})=C(x_{i})]>=1/2+1/2ms]$.
As there exist $0\leq a<1/2$ such that $1/2+1/2ms+a$ represents the average
accuracy of the predictor $C^{\prime}$ when
$r_{1},...,r_{m},x_{1},...,x_{i-1},x_{i+1},...,x_{m}$ satisfy
$\underset{x_{i}}{\mathbb{P}}[C^{\prime}(x_{i})=C(x_{i})]>=1/2+1/2ms$, we have

$p\left(\frac{1}{2}+\frac{1}{2ms}+a\right)+(1-p)\left(\frac{1}{2}+\frac{1}{2ms}\right)\geq\underset{\begin{subarray}{c}r_{1},...,r_{m}\\\
x_{1},...,x_{m}\end{subarray}}{\mathbb{P}}[C^{\prime}(x_{i})=C(x_{i})]\geq\frac{1}{2}+\frac{1}{ms},$

and thus

$p\geq\frac{1}{2ms}\cdot\frac{1}{a}\geq\frac{1}{ms}.$

Therefore, $L$ outputs a $(1/2+1/2ms)$-accurate $C^{\prime}$ with confidence
$1/m^{2}s$. ∎

######  Comment.

When $D$ is nondeterministic: (1) if $r_{i}=0$, then the $C^{\prime}$ learned
by $L^{C}$ is also nondeterministic; (2) if $r_{i}=0$, then the $C^{\prime}$
learned by $L^{C}$ is co-nondeterministic.

In the remaining of this section, we are going to derive learning algorithms
based on the assumptions of the nonexistence of i.o. demi-bits and demi-bits
respectively. It is obvious that the non-existence of i.o. demi-bits is a
stronger assumption than the non-existence of demi-bits. We will also see
that, given our proof strategy, the stronger assumption yields a better
learning result, in a sense that will be clear later.

A proof of the following theorem was sketch in [Pic20]:

######  Theorem A.3.

Assume the nonexistence of i.o. demi-bits. Then for every $c\in\mathbb{N}$,
$Circuit[n^{c}]$ is learnable by $Circuit[2^{n^{o(1)}}]$ (by taking random
examples) with confidence $1/2^{n^{o(1)}}$ up to error $1/2-1/2^{n^{o(1)}}$,
where the learner is allowed to generate a nondeterministic or co-
nondeterministic algorithm approximating the target function.

###### Proof.

Assume the nonexistence of i.o. demi-bits and $c\in\mathbb{N}$. There is an
encoding scheme for $Circuit[n^{c}]$ such that every $C\in Circuit[n^{c}]$
with $n$-bit input can be encoded as a string $\langle C\rangle$ of length
$\leq d=d(n)$, where $d(n)$ is a polynomial. Set $m=n^{d}+1$ and consider a
generator $G:\\{0,1\\}^{mn+n^{d}}\to\\{0,1\\}^{mn+m}$, which interprets the
last $n^{d}$ input bits as a description of some $C\in Circuit[n^{c}]$ and
then computes on the remaining $mn$ bits of input as $G_{m,C}$. We note that
$G$ is in ${\mathsf{P}}/\sf{poly}$(whenever the encoding scheme for
$Circuit[n^{c}]$ is reasonable). Because $G$ is not an i.o. demi-bit, there is
nondeterministic circuit $D$ of sub-exponential size such that for all
sufficiently large $n$’s

$\mathbb{P}\left[{D(y)=1}\right]\geq 1/|D|\ \text{ and }\
\mathbb{P}\left[{D(G(x))=1}\right]=0.$

In particular, for every $C\in Circuit[n^{c}]$, $\mathbb{P}\left[{D(G(\langle
C\rangle,x)=1}\right]=0$. That is $\mathbb{P}\left[{D(G_{m,C}(x))=1}\right]=0$
for every $C\in Circuit[n^{c}]$. Therefore,

$\mathbb{P}\left[{D(y)=1}\right]-\mathbb{P}\left[{D(G_{m,C}(x))=1}\right]\geq
1/|D|.$

Because $m=n^{d}+1$ is polynomial in $n$ and $|D|$ is sub-exponential, by
Lemma A.2, $\mathcal{C}$ can be learned by a randomized circuit family of size
$2^{n^{o(1)}}$ with confidence $1/2^{n^{o(1)}}$ up to error
$1/2-1/2^{n^{o(1)}}$. ∎

If we weaken the assumption to the non-existence of demi-bits, with the same
proof, we are able to learn $Circuit[n^{c}]$ in a weaker sense formulated as
below:

######  Theorem A.4.

Assume the nonexistence of demi-bits. Then for every $c\in\mathbb{N}$, there
is an infinite monotone sequence $\\{n_{i}\\}\subseteq\mathbb{N}$ such that
$Circuit[n^{c}]$ is learnable by $Circuit[2^{n^{o(1)}}]$ (by taking random
examples) with confidence $1/2^{n^{o(1)}}$ up to error $1/2-1/2^{n^{o(1)}}$
for every $n\in\\{n_{i}\\}$, where the learner is allowed to generate a
nondeterministic or co-nondeterministic algorithm approximating the target
function.

Because the existence of $N\tilde{P}/qpoly$-natural proofs (a weaker
assumption than the existence assumption of ${\mathsf{NP}}/\sf{poly}$-natural
proofs) rules out the existence of i.o. super-bits [Rud97], by Theorem A.3, we
have:

######  Corollary A.5.

Assume the existence of i.o. demi-bits implies the existence of i.o. super-
bits. If there exists an $N\tilde{P}/qpoly$-natural property useful against
${\mathsf{P}}/\sf{poly}$, then for every $c\in\mathbb{N}$, $Circuit[n^{c}]$ is
learnable by $Circuit[2^{n^{o(1)}}]$ (by taking random examples) with
confidence $1/2^{n^{o(1)}}$ up to error $1/2-1/2^{n^{o(1)}}$, where the
learner is allowed to generate a nondeterministic or co-nondeterministic
algorithm approximating the target function.

## Acknowledgments

We are indebted to Jan Pich who suggested looking at demi-bits and provided
many clarifications regarding his work [Pic20]. We are grateful to Rahul
Santhanam for very useful discussions and specifically mentioning the
potential application appearing in Theorem 4.5. Finally, we wish to thank
Hanlin Ren for very useful comments on the manuscript as well as Oliver Korten
and Yufeng Li for further discussions.

## References

  * [ABK+06] Eric Allender, Harry Buhrman, Michal Koucký, Dieter van Melkebeek, and Detlef Ronneburger.  Power from random strings.  SIAM J. Comput., 35(6):1467–1493, 2006.
  * [ABRW04] Michael Alekhnovich, Eli Ben-Sasson, Alexander A. Razborov, and Avi Wigderson.  Pseudorandom generators in propositional proof complexity.  SIAM J. Comput., 34(1):67–88, 2004.  (A preliminary version appeared in Proceedings of the 41st Annual Symposium on Foundations of Computer Science (Redondo Beach, CA, 2000)).
  * [ACGS88] W. Alexi, B. Chor, O. Goldreich, and C. P. Schnorr.  Rsa and rabin functions: Certain parts are as hard as the whole.  SIAM Journal on Computing, 17(2):194–209, 1988.
  * [BEHW87] A. Blumer, A. Ehrenfeucht, D. Haussler, and M. K. Warmuth.  Occam’s razor.  Inf. Process. Lett., 24(6):377–380, apr 1987.
  * [BFKL94] A. Blum, M. Furst, M. Kearns, and R. J. Lipton.  Cryptographic primitives based on hard learning problems.  In Douglas R. Stinson, editor, Advances in Cryptology — CRYPTO’ 93, pages 278–291, Berlin, Heidelberg, 1994. Springer Berlin Heidelberg.
  * [BM84] M. Blum and S. Micali.  How to generate cryptographically strong sequences of pseudo-random bits.  SIAM J. Comput., 13(4):850–864, nov 1984.
  * [BOV07] Boaz Barak, Shien Jin Ong, and Salil P. Vadhan.  Derandomization in cryptography.  SIAM J. Comput., 37(2):380–400, 2007.
  * [DVV16] Akshay Degwekar, Vinod Vaikuntanathan, and Prashant Nalini Vasudevan.  Fine-grained cryptography.  Cryptology ePrint Archive, Paper 2016/580, 2016.  https://eprint.iacr.org/2016/580.
  * [GGM86] O. Goldreich, S. Goldwasser, and S. Micali.  How to construct random functions.  J. ACM, 33(4):792–807, aug 1986.
  * [GL89] O. Goldreich and L. A. Levin.  A hard-core predicate for all one-way functions.  In 21st Annual ACM Symposium on Theory of Computing, STOC ’89, page 25–32, New York, NY, USA, 1989. Association for Computing Machinery.
  * [GM84] S. Goldwasser and S. Micali.  Probabilistic encryption.  Journal of Computer and System Sciences, 28(2):270–299, 1984.
  * [Gol01] Oded Goldreich.  Foundations of cryptography I: Basic Tools.  Cambridge: Cambridge University Press, 2001.
  * [Gol08] O. Goldreich.  Computational Complexity: A Conceptual Perspective.  Cambridge University Press, 2008.
  * [HILL99] J. Håstad, R. Impagliazzo, L. A. Levin, and M. Luby.  A pseudorandom generator from any one-way function.  SIAM Journal on Computing, 28(4):1364–1396, 1999.
  * [IN89] R. Impagliazzo and M. Naor.  Efficient cryptographic schemes provably as secure as subset sum.  In 30th Annual Symposium on Foundations of Computer Science, pages 236–241, 1989.
  * [Kal05] B. S. Kaliski.  Elliptic curves and cryptography : a pseudorandom bit generator and other tools.  Phd Thesis Mit, 2005.
  * [Kra04] Jan Krajíček.  Dual weak pigeonhole principle, pseudo-surjective functions, and provability of circuit lower bounds.  The Journal of Symbolic Logic, 69(1):265–286, 2004.
  * [Kra10] Jan Krajíček.  Forcing with random variables and proof complexity, volume 382 of London Mathematical Society Lecture Notes Series.  Cambridge Press, 2010.
  * [KV94] M. J. Kearns and U. V. Vazirani.  An Introduction to Computational Learning Theory.  MIT Press, Cambridge, MA, USA, 1994.
  * [KvM02] Adam R. Klivans and Dieter van Melkebeek.  Graph nonisomorphism has subexponential size proofs unless the polynomial-time hierarchy collapses.  SIAM J. Comput., 31(5):1501–1526, 2002.
  * [LP20] Yanyi Liu and Rafael Pass.  On one-way functions and kolmogorov complexity.  In Sandy Irani, editor, 61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020, Durham, NC, USA, November 16-19, 2020, pages 1243–1254. IEEE, 2020.
  * [Lub96] M. Luby.  Pseudorandomness and Cryptographic Applications, volume 1.  Princeton University Press, 1996.
  * [NW94] N. Nisan and A. Wigderson.  Hardness vs randomness.  Journal of Computer and System Sciences, 49(2):149–167, 1994.
  * [OS17] I. C. Oliveira and R. Santhanam.  Conspiracies between learning algorithms, circuit lower bounds, and pseudorandomness.  In Proceedings of the 32nd Computational Complexity Conference, CCC ’17, Dagstuhl, DEU, 2017. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik.
  * [Pic20] J. Pich.  Learning algorithms from circuit lower bounds.  CoRR, abs/2012.14095, 2020.
  * [PS19] Jan Pich and Rahul Santhanam.  Why are proof complexity lower bounds hard?  In 60th Annual IEEE Symposium on Foundations of Computer Science FOCS 2019, November 9-12, 2019, Baltimore, Maryland USA, 2019.
  * [Raz15] Alexander A. Razborov.  Pseudorandom generators hard for $k$-DNF resolution and polynomial calculus resolution.  Annals of Mathematics, 181:415–472, 2015.
  * [RR97] A. A. Razborov and S. Rudich.  Natural proofs.  Journal of Computer and System Sciences, 55(1):24–35, 1997.
  * [RS21] N. Rajgopal and R. Santhanam.  On the Structure of Learnability Beyond P/Poly.  In Mary Wootters and Laura Sanità, editors, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021), volume 207 of Leibniz International Proceedings in Informatics (LIPIcs), pages 46:1–46:23, Dagstuhl, Germany, 2021. Schloss Dagstuhl – Leibniz-Zentrum für Informatik.
  * [Rud97] S. Rudich.  Super-bits, demi-bits, and NP/qpoly-natural proofs.  Journal of Computer and System Sciences, 55:204–213, 1997.
  * [San20] Rahul Santhanam.  Pseudorandomness and the minimum circuit size problem.  In Thomas Vidick, editor, 11th Innovations in Theoretical Computer Science Conference, ITCS 2020, January 12-14, 2020, Seattle, Washington, USA, volume 151 of LIPIcs, pages 68:1–68:26. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020.
  * [San22] Rahul Santhanam.  Personal communication, 2022.
  * [SU05] Ronen Shaltiel and Christopher Umans.  Simple extractors for all min-entropies and a new pseudorandom generator.  J. ACM, 52(2):172–216, 2005.
  * [SvM23] Nicollas Sdroievski and Dieter van Melkebeek.  Instance-wise hardness versus randomness tradeoffs for arthur-merlin protocols.  The Electronic Colloquium on Computational Complexity (ECCC), 2023\.
  * [Val84] L. G. Valiant.  A theory of the learnable.  Commun. ACM, 27(11):1134–1142, nov 1984.
  * [Val85] L. G. Valiant.  Learning disjunction of conjunctions.  In Proceedings of the 9th International Joint Conference on Artificial Intelligence - Volume 1, IJCAI’85, page 560–566, San Francisco, CA, USA, 1985. Morgan Kaufmann Publishers Inc.
  * [VS84] L. G. Valiant and J. C. Shepherdson.  Deductive learning [and discussion].  Philosophical Transactions of the Royal Society of London. Series A, Mathematical and Physical Sciences, 312(1522):441–446, 1984.
  * [Yao82] A. C. Yao.  Theory and application of trapdoor functions.  In 23rd Annual Symposium on Foundations of Computer Science, FOCS ’82, pages 80–91, 1982.