Protocol for verifying novel compression algorithm?

By the pigeonhole principle, we can demonstrate that arbitrary lengths of random data are uncompressible in the general case.

But let us imagine that I claim that I have created an oracle that can compress arbitrary random data by a certain ratio.

In such a case, I don't want to show you the internal details of my oracle, because you will steal its awesome secrets. But I am willing to generate hashes for you. I am also willing to use my oracle to compress and/or decompress any file that you give me, or do any other reasonable thing that does not disclose the internal details of the oracle.

Design a protocol that lets me prove that my oracle works as I claim, without actually revealing the algorithm it uses.

If that can't be done, then design a protocol that requires me to trust a disinterested third party, as little as I possibly can.

A little more formally: I want to demonstrate, to an arbitrary likelihood, that I possess an invertible bijective function $$F$$, in which $$F(x) = y$$, $$F^{-1}(y) = x$$, and $$F^{-1}(F(x)) = x$$, without revealing $$F$$ or $$F^{-1}$$. Can a protocol be designed that permits me to prove the existence of $$F$$ and $$F^{-1}$$ without revealing them? If not, what is the least extent to which a third party would need to know $$F$$ or $$F^{-1}$$?

This isn't a homework question, just a possibly interesting thought experiment to people who understand crypto better than I do.

• I can confirm that this is not a homework question, in case anyone wonders. :-D Commented Feb 18 at 8:30
• The proof would also need to show that $|F(x)| < |x|$, otherwise the existence of such an $F$ is trivial... Commented Feb 18 at 10:33
• @poncho well yes, but I didn't necessarily require that as part of the protocol, because I imagined that proof of a particular algorithm's existence might lend itself to other situations besides compressibility. Commented Mar 15 at 22:07
• @poncho For example, imagine that I might claim that I can crack any one-time pad. I don't want to teach you how I do that, though. In that case, the length condition might or might not hold. Commented Mar 15 at 22:14

Well, the only solution that occurs to me is:

• The verifier (V), that is, the guy who is skeptical about the existence of such an algorithm, selects an FHE (Fully Homomorphic Encryption) algorithm and public/private key; he publishes the algorithm and public key (but keeps the private key secret)

• The prover (P), that is, the guy with the secret algorithm, implements his algorithm (both $$F$$ and $$F^{-1}$$) using the FHE algorithm and public key

• V selects a value $$x$$ and a direction bit $$d$$. He encrypts $$x$$ with his public key and gives both $$E(x)$$ and $$d$$ to P

• If $$d=0$$, $$P$$ computes (using his FHE implementation) the value $$E(F(x))$$; if $$d=1$$, $$P$$ computes the value $$E(F^{-1}(x))$$. In either case, he sends that value back to V

• V decrypts the value, recovering either $$F(x)$$ or $$F^{-1}(x)$$

With Oracle access to $$F, F^{-1}$$, $$V$$ can easily verify the claims; for example, he can pick a random sequence $$X_0, X_1, ..., X_{n-1}$$ and ask for $$Y_i=F(X_i)$$; he can then make sure that $$|Y_i| < |X_i|$$ and then ask for (in a random order) $$F^{-1}(Y_i)$$ and verify that is, in fact, $$X_i$$. And, because everything P has access to is encrypted, his best cheating strategy succeeds with probability $$1/n!$$ if $$P$$ selects a random sequence of length $$n$$.

Issues:

• This gives V Oracle access to the actual inputs/outputs of $$F, F^{-1}$$

• The FHE encryption system has the further requirement that someone with the private key can't, by looking at a ciphertext, determine what computations lead to that ciphertext. I don't believe this is hard to achieve, but is a nonstandard assumption.