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!