0
$\begingroup$

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.

$\endgroup$
4
  • 1
    $\begingroup$ I can confirm that this is not a homework question, in case anyone wonders. :-D $\endgroup$
    – Joe Z
    Commented Feb 18 at 8:30
  • 1
    $\begingroup$ The proof would also need to show that $|F(x)| < |x|$, otherwise the existence of such an $F$ is trivial... $\endgroup$
    – poncho
    Commented Feb 18 at 10:33
  • $\begingroup$ @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. $\endgroup$
    – johnwbyrd
    Commented Mar 15 at 22:07
  • $\begingroup$ @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. $\endgroup$
    – johnwbyrd
    Commented Mar 15 at 22:14

1 Answer 1

2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.