Theorem 5.3 The sets with multiprover interactive proof systems are exactly those recognizable in nondeterministic exponential time. Furthermore, all of these sets have multiprover systems that are zero-knowledge.

In the instance-hiding scheme for the discrete logarithm function that is given in §5.2.2, player A queries only one box B. This is an example of a one-oracle instance-hiding scheme. The scheme for the multivariate polynomial is an example of a multi-oracle instance-hiding scheme.

The first basic question here is to determine exactly which sets have instance-hiding schemes that leak no information about x to the oracles. Actually, it impossible to find schemes that leak absolutely no information—A must leak to B at least the length of x if the function computed by B is nontrivial. (This is stated and proven precisely in Abadi et al., 1989.) Thus, the real question is which sets have instance-hiding schemes that leak at most the length of x.

For one-oracle schemes, Abadi et al. (1989) obtained the following conditional negative result:

Theorem 5.4 No NP-hard set has a one-oracle instance-hiding scheme that leaks at most the length of x, unless the polynomial-time hierarchy collapses at the third level.¹

Beaver and Feigenbaum (1990) used the low-degree polynomial trick given in §5.2.2 to obtain a universal construction of multi-oracle instance-hiding schemes:

Theorem 5.5 Every Boolean function of n bits has an (n + 1)-oracle instance-hiding scheme that leaks at most the length of x to each oracle.

Interestingly, this low-degree polynomial trick, which was devised in order to construct instance-hiding schemes, became a crucial ingredient in the characterization of the set-recognition power of interactive proof systems, both one-prover and multiprover. A thorough explanation of this connection appears in Brassard (1990).