Boolean Circuit in a Black Box?

Question

Just had this random idea... but unfortunately I'm not quite versed in complexity theory, so I thought it would be a good idea to ask it here.

Let's equip a normal Turing machine with a "black box oracle" that contains a boolean circuit of unknown size, and call this Turing machine a "black box machine". The black box oracle pretty much works the same way as an ordinary oracle machine, whose input and output (which are just the input/output of the circuit) are both polynomially bounded by the input size of our black box machine. As in the usual oracle machine's case, the evaluation of the black box circuit takes $O(1)$ time.

Now we define the boolean black box (BBB) problem:

(BBB) Given a circuit $C$ which size is polynomially bounded by $n$ and a black box $B$ which input and output are both polynomially bounded by $n$, determine whether $C$ will always behave identically as $B$ (in other words, for any possible input, whether $C$ and $B$ always produce the same result).

And the corresponding function problem:

(BBB-F) Given a black box $B$ which input and output are both polynomially bounded by $n$, compute a circuit $C$ that always behaves identically as $B$.

It seems to me that BBB is unlikely to be in $P$, or even $NP$, because generally one needs to check all $2^n$ possible input/output pairs, which would take more than polynomial time. However, what happens if we restrict the size of the black-box circuit to be polynomially bounded by $n$? (Notice that this does change something: if we restrict the size to be some constant $c$, then the problem can be solved in linear time. But what happens when the bound is polynomial?) Of course, we would also like to know if BBB-F will fall into $FP/FNP$ with this restriction.

A variant of this problem is that we only require the machine to be correct with a probability that is significantly higher than $1/2$. In other words, does $BBB \in PP$?

Third question: $PSPACE$. Can this possibly be solved in polynomial space?

Also, I can see some vague connections between this problem and some craptographic problems. For instance, I would guess that a CCA2-secure cryptosystem exists if and only if BBB-F is not in FP. To see the left-to-right part, simply put the decrypting procedure along with the secret key into a black box. An attacker with access to this black box has essentially the power to perform CCA2 attack. Now if BBB-F is indeed in FP, then we can construct a valid circuit $C$ within polynomial time that behaves the same as the black box circuit, which is the decryptor, and that would break the security of the system. As for the other way around, I don't have a good idea yet.

I googled quite a bit but couldn't find useful info about work done along this direction, so I would really appreciate it if someone can point me to some relevant literature. Any further thoughts on this problem would also be much appreciated. Thanks for your time!

Answer 1

Actually, the problems BBB and BBB-F above are not currently specified as languages or decision problems (the black box is not explicitly given to us as a binary string of some kind, is it?), so these problem cannot be in NP, PP, PSPACE, or even decidable/undecidable. A fundamental property of languages in the computability/complexity sense is that no bit of the initial input is "hidden" from you.

As suggested by M. Alaggan, the problems BBB and BBB-F are probably closest to the "learning with membership queries" framework, where one can only access a target function by querying it at various points and tries to infer the function. Nevertheless, both problems require superpolynomially many queries to the black box in the worst case, so they are both "intractable" in that sense. For BBB and BBB-F, your intuition is correct: it requires $\Omega(2^n)$ queries just to check that $B$ is not the "all-zeroes" function.

Even if you assume that the black box in these problems can be indeed modeled by some polynomial size circuit, it is highly unlikely that this helps. For example, if pseudorandom functions exist (a common cryptographic assumption) then for all $n$ there are polynomial size circuits $C_n$ with $n$ bits of input that cannot be distinguished from a completely random $n$-bit function, by any probabilistic subexponential time algorithm with black-box access to $C_n$. It follows that no subexponential time algorithm can efficiently reconstruct $C_n$ just from queries to $C_n$.

Answer 2

Googling "learning boolean function problem" from M. Alaggan says that BBB and BBB-F is at most NP-Hard and you can optimize the problem for certain inputs.