Encrypted Queries to Multiple Oracles (Extended Abstract).

Abadi, Feigenbaum, and Kilian have considered encrypted oracle queries [J. Comput. System Science, in press; preliminary version in STOC87]. Their main result was negative: if f is an NP-hard function, then a polynomial-time machine cannot compute f by querying an f-oracle B while hiding from B all but the size of the cleartext instance x, assuming that the polynomial hierarchy does not collapse. This paper considers the case in which a polynomial-time machine is allowed to ask encrypted queries of multiple "oracles' B sub 1 through B sub m. We obtain positive results in two models. 1) Oracles B sub 1 through B sub m may collude before the execution of the protocol with A, but they are kept physically separate during the execution. In this model, m =|x| oracles suffice for any Boolean function f; 2) Oracles B sub 1 through B sub m may not collude at all, either before or during the execution. In this model, m = 2 oracles suffice for any Boolean function f. Conversely, there are boolean functions f for which two oracles are necessary.