Can a random oracle change which TFNP problems are strongly hard-on-average? I've been thinking about the following question at

various times 
since I saw this question on Cryptography.


Question

Let $R$ be a TFNP relation. ​ Can a random oracle help P/poly

to break $R$ with non-negligible probability? ​ More formally,
$
\newcommand{\Pr}{\operatorname{Pr}}
\newcommand{\E}{\operatorname{\mathbb{E}}}
\newcommand{\O}{\mathcal{O}}
\newcommand{\Good}{\mathsf{Good}}
$

Does


  for all P/poly algorithms $A$, 
  $\Pr_x [R(x, A(x))]$ is negligible


necessarily imply that 


  for almost all oracles $\O$, ​ 
  for all P/poly oracle-algorithms $A$, 
  ​$\Pr_x [R(x, A^\O(x))]$​ is negligible


?



Alternative formulation

The relevant set of oracles is $G_{\delta\sigma}$ (thus measurable), so by taking contrapositive and applying Kolmogorov's zero-one law,
the following formulation is equivalent to the original one.

Does


  for almost all oracles $\O$,
  there exists a P/poly oracle-algorithm $A$ such that 
  $\Pr_x [R(x,A^\O(x))]$ is not negligible


necessarily imply that


  there exists a P/poly algorithm $A$ such that
  $\Pr_x [R(x,A(x))]$ is not negligible


?



The uniform case

Here's a proof for the uniform version:

There are only countably-many PPT oracle-algorithms, 
so by countable additivity of the null [ideal][8], 
there is a PPT algorithm $A$ such that 
for a non-null set of oracles $\O$,

$\Pr_x [R(x,A^\O(x))]$ is non-negligible. 
Let $B$ be such an oracle-algorithm.

Similarly, let $c$ be a positive integer such that 
for a non-null set of oracles $\O$,

$\Pr_x[R(x,B^\O(x))]$
is infinitely-often at least $n^{-c}$,
where $n$ is the length of the input.

By the contrapositive of Borel-Cantelli, 
$\sum_{n=0}^{\infty} \Pr_{\O} \left[
n^{-c} \leq \Pr_{x\in\{0,1\}^n}[R(x,B^\O(x))] 
\right]$ is infinite. 

By the comparison test, infinitely often
$\Pr_{\O} \left[
n^{-c} \leq \Pr_{x\in \{0,1\}^n}[R(x,B^\O(x))
\right] \geq n^{-2}$.

Let $S$ be the PPT algorithm which [simulates the oracle][12] and 
runs $B$ with that simulated-oracle.

Fix $n$ and 
let $\Good$ be the set of oracles $\O$ such that 
$n^{-c} \leq \Pr_{x\in\{0,1\}^n} [R(x,B^\O(x))]$.

If $\Good$ is not null then
$$\begin{matrix}
\Pr_{\O} [\O\in \Good] \cdot n^{-c}
\\ = \\
\Pr_{\O} [\O\in \Good] \cdot \E_{\O}[n^{-c}]
\\ \leq \\
\Pr_{\O} [\O\in \Good] \cdot \E_{\O} \left[
\Pr_{x\in \{0,1\}^n} [R(x,B^\O(x))] \mid \O \in \Good 
\right]
\\ = \\
\E_{\O}\left[
\Pr_{x\in \{0,1\}^n} [\O \in \Good \text{ and } R(x,B^\O(x))]
\right]
\\ \leq \\
\E_{\O}\left[
\Pr_{x\in \{0,1\}^n} [R(x,B^\O(x))]
\right]
\\ = \\
\Pr_{\O, x\in\{0,1\}^n} [R(x,B^\O(x))]
\\ = \\
\Pr_{x\in \{0,1\}^n, \O} [R(x,B^\O(x))]
\\ = \\
\E_{x\in \{0,1\}^n} \left[ \Pr_{\O}[R(x,B^\O(x))] \right]
\\ = \\
\E_{x\in \{0,1\}^n} \left[ \Pr[R(x,S(x))] \right]
\\ = \\
\Pr_{x\in \{0,1\}^n} [R(x,S(x))]
\end{matrix}$$
.

Since $\Pr_{\O} [\O\in \Good] \geq n^{-2}$ infinitely often,
$\Pr_x[R(x,S(x))]$ is not negligible.

Therefore the uniform version holds. ​ The proof critically uses the fact that 
there

are only countably many PPT oracle-algorithms. ​ This idea does not work in the

non-uniform case, since as 
there are continuum-many P/poly oracle-algorithms.
No to my title, and Yes to my question's body. ​ This in fact generalizes immediately
  
  to every polynomial-length game that does not use the adversaries' code.



Note that I will be using $C$ for the adversaries, rather than $A$,

so as to match up with Theorem 2's notation.

Assume that for almost all oracles $\mathcal{O}$, there exists a P/poly

oracle-algorithm $C$ such that $\operatorname{Pr}_x\hspace{-0.06 in}\left[\hspace{.02 in}R\hspace{-0.04 in}\left(x,\hspace{-0.04 in}C^{\mathcal{O}\hspace{-0.02 in}}(x)\hspace{-0.03 in}\right)\hspace{-0.02 in}\right]$ is non-negligible.



For almost all oracles $\mathcal{O}$, there exists a positive integer d such that

there exists a sequence of circuits of size at most d+nd such that

$\operatorname{Pr}_{x\in \{0,1\}^n}\hspace{-0.06 in}\left[\hspace{.02 in}R\hspace{-0.04 in}\left(x,\hspace{-0.04 in}C^{\mathcal{O}\hspace{-0.02 in}}(x)\hspace{-0.03 in}\right)\hspace{-0.02 in}\right]$ is infinitely-often greater than $1\hspace{-0.04 in}\big/\hspace{-0.07 in}\left(\hspace{-0.02 in}n^d\hspace{-0.02 in}\right)$.

By countable additivity, there exists a positive integer d such that for a non-null set of oracles $\mathcal{O}$, there exists a sequence of circuits of size at most d+nd such that

$\operatorname{Pr}_{x\in \{0,1\}^n}\hspace{-0.06 in}\left[\hspace{.02 in}R\hspace{-0.04 in}\left(x,\hspace{-0.04 in}C^{\mathcal{O}\hspace{-0.02 in}}(x)\hspace{-0.03 in}\right)\hspace{-0.02 in}\right]$ is infinitely-often greater than $1\hspace{-0.04 in}\big/\hspace{-0.07 in}\left(\hspace{-0.02 in}n^d\hspace{-0.02 in}\right)$.

Let j be such a d, and let z be the (not-necessarily-efficient) oracle-algorithm which

takes n as input and outputs the lexicographically least oracle-circuit of size at most j+n$^{\hspace{.03 in}j}$

that maximizes $\operatorname{Pr}_{x\in \{0,1\}^n}\hspace{-0.06 in}\left[\hspace{.02 in}R\hspace{-0.04 in}\left(x,\hspace{-0.04 in}C^{\mathcal{O}\hspace{-0.02 in}}(x)\hspace{-0.03 in}\right)\hspace{-0.02 in}\right]$. ​ ​ ​ By the contrapositive of Borel-Cantelli, $1\hspace{-0.04 in}\big/\hspace{-0.07 in}\left(\hspace{-0.02 in}n^2\hspace{-0.02 in}\right) \: &lt; \: \operatorname{Prob}_{\mathcal{O}}\hspace{-0.05 in}\bigg[\hspace{-0.02 in}1\hspace{-0.04 in}\big/\hspace{-0.07 in}\left(\hspace{-0.03 in}n^{\hspace{.04 in}j}\hspace{-0.02 in}\right) &lt; \operatorname{Pr}_{x\in \{0,1\}^n}\hspace{-0.06 in}\left[\hspace{.02 in}R\hspace{-0.04 in}\left(\hspace{-0.04 in}x,\hspace{-0.04 in}\left(z^{\mathcal{O}}\right)^{\hspace{-0.04 in}\mathcal{O}\hspace{-0.02 in}}(x)\hspace{-0.05 in}\right)\hspace{-0.02 in}\right]\hspace{-0.06 in}\bigg] \;\;\;$ for infinitely many n.

For such n,

$1\hspace{-0.04 in}\big/\hspace{-0.07 in}\left(\hspace{-0.02 in}n^{2+j}\hspace{-0.02 in}\right) \; = \; 1\hspace{-0.04 in}\big/\hspace{-0.07 in}\left(\hspace{-0.04 in}\left(\hspace{-0.02 in}n^2\hspace{-0.02 in}\right)\hspace{-0.06 in}\cdot \hspace{-0.06 in}\left(\hspace{-0.02 in}n^{\hspace{.04 in}j}\hspace{-0.02 in}\right)\hspace{-0.04 in}\right) \; = \; \left(\hspace{-0.02 in}1\hspace{-0.04 in}\big/\hspace{-0.07 in}\left(\hspace{-0.02 in}n^2\hspace{-0.02 in}\right)\hspace{-0.03 in}\right) \cdot \left(\hspace{-0.02 in}1\hspace{-0.04 in}\big/\hspace{-0.07 in}\left(\hspace{-0.02 in}n^{\hspace{.04 in}j}\hspace{-0.02 in}\right)\hspace{-0.03 in}\right) \; &lt; \; \operatorname{Prob}_{\mathcal{O}\hspace{.02 in},\hspace{.04 in}x\in \{0,1\}^n}\hspace{-0.06 in}\left[R\hspace{-0.04 in}\left(\hspace{-0.04 in}x,\hspace{-0.04 in}\left(z^{\mathcal{O}}\right)^{\hspace{-0.04 in}\mathcal{O}\hspace{-0.02 in}}(x)\hspace{-0.05 in}\right)\hspace{-0.02 in}\right]$

.
Let $A$ be the oracle-algorithm that takes 2 inputs, one of which is $n$, and does as follows:

Choose a random n-bit string $x$. ​ Attempt to

[parse the other input as an oracle-circuit and run that oracle-circuit on the n-bit string].

If that succeeds and the oracle-circuit's output $y$ satisfies R(x,y), then output 1, else output 0.

(Note that $A$ is not just the adversary.)

For infinitely many n, $\;\;\; 1\hspace{-0.04 in}\big/\hspace{-0.07 in}\left(\hspace{-0.02 in}n^{2+j}\hspace{-0.02 in}\right) \; &lt; \; \operatorname{Prob}_{\mathcal{O}}\left[A^{\mathcal{O}}(n,z^{\mathcal{O}}(n))\right] \:\:\:\:$.

Let p be as in Theorem 2, and set $\;\;\; f \: = \: 2\hspace{-0.04 in}\cdot \hspace{-0.04 in}p\hspace{-0.04 in}\cdot \hspace{-0.04 in}\left(\hspace{.02 in}j\hspace{-0.04 in}+\hspace{-0.04 in}n^{\hspace{.04 in}j}\hspace{-0.02 in}\right)\hspace{-0.04 in}\cdot \hspace{-0.04 in}n^{(2+j)\cdot 2} \:\:\:\:$.

By Theorem 2, there exists an oracle-function $\mathcal{S}$ such that with $\mathcal{P}$ as in that theorem,

if $\;\;\; 1\hspace{-0.04 in}\big/\hspace{-0.07 in}\left(\hspace{-0.02 in}n^{2+j}\hspace{-0.02 in}\right) \; &lt; \; \operatorname{Prob}_{\mathcal{O}}\left[A^{\mathcal{O}}(n,z^{\mathcal{O}}(n))\right] \;\;\;$ then

$1\hspace{-0.04 in}\big/\hspace{-0.07 in}\left(2\hspace{-0.06 in}\cdot \hspace{-0.06 in}\left(\hspace{-0.02 in}n^{2+j}\right)\hspace{-0.04 in}\right) \; = \; \left(\hspace{-0.02 in}1\hspace{-0.04 in}\big/\hspace{-0.07 in}\left(\hspace{-0.02 in}n^{2+j}\hspace{-0.02 in}\right)\hspace{-0.03 in}\right)-\left(\hspace{-0.04 in}1\hspace{-0.04 in}\big/\hspace{-0.07 in}\left(2\hspace{-0.06 in}\cdot \hspace{-0.06 in}\left(\hspace{-0.02 in}n^{2+j}\right)\hspace{-0.04 in}\right)\hspace{-0.04 in}\right) \; = \; \left(\hspace{-0.02 in}1\hspace{-0.04 in}\big/\hspace{-0.07 in}\left(\hspace{-0.02 in}n^{2+j}\hspace{-0.02 in}\right)\hspace{-0.03 in}\right)\hspace{-0.04 in}-\hspace{-0.04 in}\sqrt{1\hspace{-0.04 in}\big/\hspace{-0.07 in}\left(2\hspace{-0.06 in}\cdot \hspace{-0.06 in}2\hspace{-0.06 in}\cdot \hspace{-0.06 in}\left(\hspace{-0.02 in}n^{(2+j)\cdot 2}\right)\hspace{-0.04 in}\right)}$

$= \; \left(\hspace{-0.02 in}1\hspace{-0.04 in}\big/\hspace{-0.07 in}\left(\hspace{-0.02 in}n^{2+j}\hspace{-0.02 in}\right)\hspace{-0.03 in}\right)\hspace{-0.04 in}-\hspace{-0.04 in}\sqrt{\left(p\hspace{-0.04 in}\cdot \hspace{-0.06 in}\left(\hspace{.02 in}j\hspace{-0.04 in}+\hspace{-0.04 in}n^{\hspace{.04 in}j}\hspace{-0.02 in}\right)\hspace{-0.04 in}\right)\hspace{-0.06 in}\big/\hspace{-0.07 in}\left(2\hspace{-0.06 in}\cdot \hspace{-0.06 in}2\hspace{-0.06 in}\cdot \hspace{-0.04 in}p\hspace{-0.04 in}\cdot \hspace{-0.06 in}\left(\hspace{.02 in}j\hspace{-0.04 in}+\hspace{-0.04 in}n^{\hspace{.04 in}j}\hspace{-0.02 in}\right)\hspace{-0.06 in} \cdot \hspace{-0.06 in}\left(\hspace{-0.02 in}n^{(2+j)\cdot 2}\right)\hspace{-0.04 in}\right)} \; = \; \left(\hspace{-0.02 in}1\hspace{-0.04 in}\big/\hspace{-0.07 in}\left(\hspace{-0.02 in}n^{2+j}\hspace{-0.02 in}\right)\hspace{-0.03 in}\right)\hspace{-0.04 in}-\hspace{-0.04 in}\sqrt{\left(p\hspace{-0.04 in}\cdot \hspace{-0.06 in}\left(\hspace{.02 in}j\hspace{-0.04 in}+\hspace{-0.04 in}n^{\hspace{.04 in}j}\hspace{-0.02 in}\right)\hspace{-0.04 in}\right)\hspace{-0.06 in}\big/\hspace{-0.07 in}\left(2\hspace{-0.06 in}\cdot \hspace{-0.04 in}f\right)}$

$&lt; \; \operatorname{Prob}_{\mathcal{O}}\left[A^{\mathcal{O}}(n,z^{\mathcal{O}}(n))\right]-\hspace{-0.04 in}\sqrt{\left(p\hspace{-0.04 in}\cdot \hspace{-0.06 in}\left(\hspace{.02 in}j\hspace{-0.04 in}+\hspace{-0.04 in}n^{\hspace{.04 in}j}\hspace{-0.02 in}\right)\hspace{-0.04 in}\right)\hspace{-0.06 in}\big/\hspace{-0.07 in}\left(2\hspace{-0.06 in}\cdot \hspace{-0.04 in}f\right)} \; \leq \; \operatorname{Prob}_{\mathcal{O}}\left[A^{\mathcal{P}}(n,z^{\mathcal{O}}(n))\right] \;\;\;$.

For n such that $\;\;\; 1\hspace{-0.04 in}\big/\hspace{-0.07 in}\left(\hspace{-0.02 in}n^{2+j}\hspace{-0.02 in}\right) \; &lt; \; \operatorname{Prob}_{\mathcal{O}}\left[A^{\mathcal{O}}(n,z^{\mathcal{O}}(n))\right] \;\;\;$:

In particular, there exists $\big[$an oracle-circuit $C$ of size at most j+n$^{\hspace{.03 in}j}\big]$ and

$\big[$an assignment of length at most f$\big]$ such that with that input and presampling,

$A$'s probability of outputting $1$ is greater than $1\hspace{-0.04 in}\big/\hspace{-0.07 in}\left(2\hspace{-0.06 in}\cdot \hspace{-0.06 in}\left(\hspace{-0.02 in}n^{2+j}\right)\hspace{-0.04 in}\right)$.

Oracle-circuits of size at most j+n$^{\hspace{.03 in}j}$ can be represented with poly(n) bits, so for p is bounded

above by a polynomial in n, which means f is also bounded above by a polynomial in n.

By construction of $A$, that means there are oracle-circuits of size at most j+n$^{\hspace{.03 in}j}$ and a

polynomial-length assignment such that when run with that presampling, the circuits' probability of finding a solution is greater than $1\hspace{-0.04 in}\big/\hspace{-0.07 in}\left(2\hspace{-0.06 in}\cdot \hspace{-0.06 in}\left(\hspace{-0.02 in}n^{2+j}\right)\hspace{-0.04 in}\right)$. ​ Since such circuits cannot make queries longer than j+n$^{\hspace{.03 in}j}$ bits, presampled inputs longer than that can be ignored, so such presampling can be efficiently-and-perfectly simulated with a random oracle and poly(n) hard-coded bits. ​ That means there are polynomial-size oracle circuits such that with a standard random oracle, the circuits' probability of finding a solution is greater than $1\hspace{-0.04 in}\big/\hspace{-0.07 in}\left(2\hspace{-0.06 in}\cdot \hspace{-0.06 in}\left(\hspace{-0.02 in}n^{2+j}\right)\hspace{-0.04 in}\right)$. ​ Such a random oracle can in turn be efficiently-and-perfectly simulated with just ordinary random bits, so there are polynomial-size probabilistic non-oracle circuits whose probability of finding a solution is greater than $1\hspace{-0.04 in}\big/\hspace{-0.07 in}\left(2\hspace{-0.06 in}\cdot \hspace{-0.06 in}\left(\hspace{-0.02 in}n^{2+j}\right)\hspace{-0.04 in}\right)$. ​ In turn, by hard-coding optical randomness, there are polynomial-size deterministic (non-oracle) circuits whose probability (over the choice of x) of finding a solution is greater than $1\hspace{-0.04 in}\big/\hspace{-0.07 in}\left(2\hspace{-0.06 in}\cdot \hspace{-0.06 in}\left(\hspace{-0.02 in}n^{2+j}\right)\hspace{-0.04 in}\right)$.

As shown earlier in this answer, there are infinitely many n such that $1\hspace{-0.04 in}\big/\hspace{-0.07 in}\left(\hspace{-0.02 in}n^{2+j}\hspace{-0.02 in}\right) \; &lt; \; \operatorname{Prob}_{\mathcal{O}}\left[A^{\mathcal{O}}(n,z^{\mathcal{O}}(n))\right] \;\;\;$, $\;\;\;$ so there is a polynomial such that

the sequence whose n-th entry is the lexicographically least

[circuit C of size bounded above by that polynomial] which maximizes $\operatorname{Pr}_{x\in \{0,1\}^n}\hspace{-0.04 in}\left[\hspace{.02 in}R\hspace{-0.04 in}\left(x,\hspace{-0.04 in}C(x)\hspace{-0.03 in}\right)\hspace{-0.02 in}\right]$

is a P/poly algorithm whose probability (over the choice of x) of finding a solution is non-negligible.



Therefore the implication's in my question's body always hold.

To get the same implication for other polynomial-length games, just

change this proof's $A$ to make it have the input oracle-circuits play the game.