9
$\begingroup$

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.

Improve this question
$\endgroup$
5
  • $\begingroup$ I don't think this is really a question about oracles. Since $\mathcal{O}$ is independent of $R$, you may as well just give $A$ access to a random string. The question is then: does randomness increase the power of poly-size circuits. The answer to that is "no", since if $A$ did well given access to a random string then, by an averaging argument, there would exists a particular setting of the random string with which $A$ could do well and then we might as well just hardwire that string into $A$'s circuit. $\endgroup$
    – Adam Smith
    May 7, 2016 at 14:51
  • $\begingroup$ @AdamSmith : ​ "Since $\mathcal{O}$ is independent of $R$, you may as well just give $A$ access to a random string" is the intuition, but I don't see any way of turning it into a proof. ​ ​ ​ ​ $\endgroup$
    – user6973
    May 7, 2016 at 19:59
  • 1
    $\begingroup$ @Adam, there is another quantifier that is important. I think it is easier to look at the negation: is it possible that for almost every oracle there exists a nonuniform adversary that can use the oracle to break the search problem? $\endgroup$
    – Kaveh
    May 8, 2016 at 17:36
  • $\begingroup$ I see. I was answering a different question. Sorry for the confusion. $\endgroup$
    – Adam Smith
    May 9, 2016 at 3:06
  • $\begingroup$ @domotorp : ​ ​ ​ They should be fixed now. ​ (My best guess for why that happened is the $\hspace{1.05 in}$ use of numbered links rather than in-line links.) ​ ​ ​ ​ ​ ​ ​ ​ $\endgroup$
    – user6973
    Jun 12, 2016 at 7:02

1 Answer 1

Reset to default
0
$\begingroup$

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) \: < \: \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) < \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) \; < \; \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) \; < \; \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) \; < \; \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)}$
$< \; \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) \; < \; \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) \; < \; \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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.