0
$\begingroup$

I’m looking for the existence (or the proof of non-existance) of a method to prove (with arbitrary certainty) that a particular output is the result of a particular algorithm applied on a particular input. $$ f(x) = y $$ How can I prove the above equation holds by knowing all of its constituents but without actually applying the function?

This would be akin to a zero knowledge proof but could be easily used in blockchains to embed AI algorithms.

Given some constraints on the inputs (correlated) or the algorithms (linear) do you know of any such method?

$\endgroup$
8
  • $\begingroup$ Would it be allowed that besides f(x) = y, it also holds that g(x) = y for any g different from f? $\endgroup$ Jan 6, 2021 at 15:28
  • 1
    $\begingroup$ @gurghet: If f(x) = x + 2, g(x) = x * 2, and h(x) = x ^ 2, then f(2) = g(2) = h(2) = 4. If 2 and 4 are all you know, you can't tell which of the three functions was used. $\endgroup$
    – Crowman
    Jan 6, 2021 at 16:29
  • 1
    $\begingroup$ How is this irrelevant? It's important to know whether you want to know if f(x) = y holds true without evaluating f independently of whether there exists some g for which g(x) = y OR if you want to prove that if you put x into a blackbox and y comes out, that blackbox must be made up of f. The latter is clearly impossible, as you could always construct a g which coincides with f for any specific inputs. $\endgroup$ Jan 6, 2021 at 18:05
  • 1
    $\begingroup$ @gurghet: "I can conclude that it was not g or h" - how can you conclude this? If by observing that the second element of your result is 0, and that neither g nor h produce such a result, then you've concluded this by - at least partially - applying the functions g and h, which is exactly what you say you want to avoid doing. If you really could approach the problem by simply declaring that f will yield a second element of zero and that all other possible functions won't, then the solution would be trivial, but I suspect such a solution would not satisfy you. $\endgroup$
    – Crowman
    Jan 6, 2021 at 19:42
  • 1
    $\begingroup$ @gurghet: In the general case, if you're looking for a solution which will cover literally any possible algorithm, then the general problem of deciding whether an arbitrary algorithm even halts on a given input is formally undecidable, let alone whether it yields a specific output, so you'd have to narrow your scope a little. $\endgroup$
    – Crowman
    Jan 6, 2021 at 19:51

2 Answers 2

1
$\begingroup$

I’m looking for the existence (or the proof of non-existance) of a method to prove (with arbitrary certainty) that a particular output is the result of a particular algorithm applied on a particular input.

If by "a particular algorithm" you mean "any algorithm whatsoever", then definitely no such method exists, because before you could establish if an algorithm gave a particular output for a particular input, you'd first have to establish whether the algorithm even halts on that particular input, and the halting problem is well-known to be undecidable. Note that even removing the restriction on not actually running the algorithm wouldn't let you escape from this.

If by "a particular algorithm" you mean "a specific algorithm that I'm thinking of right now" then in general, as was discussed in the comments, if you have a single input and a single output, an infinite number of different algorithms which produce that specific output from that specific input can be constructed, so it's impossible to distinguish between them solely by inspecting those two values.

If, on the other hand, you just want to test whether a given algorithm would have given a particular output for a given input, regardless of whether some different function might also have given the same output, then there are at least some relevant cases where it's not - or shouldn't be - possible. For example, any block cipher should output ciphertext that doesn't leak any usable information about either the key or the plaintext. Even if you have the key and the plaintext, if you can tell a given ciphertext would be produced by them without actually running the encryption (or decryption) function then that function is broken.

In general, if you have all the inputs, all the outputs, and full knowledge of the algorithm, then it's not clear what "zero knowledge proof" would mean here, since you evidently possess all the knowledge you'd need to run the algorithm yourself. There is the concept of a certificate value which can be a proof of an expensive algorithm - for example, you can prove you solved a given discrete logarithm by simply supplying the right exponent, so anybody can easily verify it without going to the trouble of solving it themselves - but this is completely dependent on the algorithm in question.

$\endgroup$
4
  • $\begingroup$ So, by your answer, given f, x and y, it's impossible in "at least some relevant cases" to determine whether f(x) = y without actually executing f. I agree. But I wonder in which cases it would be possible? Let's forget about the halting problem and go to a simplified version. Let's say you know that f is a polynomial. How would you know whether the polynomical function f produces y when fed with x without doing the actual calculation of evaluating f(x)? $\endgroup$ Jan 6, 2021 at 21:59
  • 1
    $\begingroup$ @programonkey: the final paragraph contains an example - if the algorithm is to compute and output a discrete logarithm, we can verify the algorithm would give that output by simply verifying that output y does indeed satisfy the given equation, without actually running the algorithm and going to the trouble of computing it again. Of course, this does require you to assume that the algorithm is correct, so there's a philosophical question here about whether "the algorithm" is any correct discrete log solver, or some particular implementation of one which may be faulty. $\endgroup$
    – Crowman
    Jan 6, 2021 at 22:15
  • $\begingroup$ Oh, now I see your point. If f is supposed to produce the log of x and you check that $e^y$ = x, then you can know that f(x) = y holds, under the assumption that f is indeed a correct log solver for input x (that is you picked x from a class of inputs for which you've previously verified the correctness of f). $\endgroup$ Jan 6, 2021 at 22:28
  • 1
    $\begingroup$ @programonkey: Yes, exactly. $\endgroup$
    – Crowman
    Jan 6, 2021 at 22:35
1
$\begingroup$

If you allow interaction between the prover of such a statement and a verifier, then this is starting to look like the setting of verifiable computing. See e.g. this Wikipedia entry or this paper by Goldwasser, Kalai and Rothblum. The goal is for the prover to convince a much computationally weaker verifier that it did apply $f(\cdot)$ to $x$ and obtained $y$ through an interactive proof. The soundness of such a proof requires the prover to actually carry out the computation to be able to convince the verifier. If you want to make the whole thing non-interactive, you could use the Fiat-Shamir heuristic.

Coming back to your question,

How can I prove the above equation holds by knowing all of its constituents but without actually applying the function?

the verifier will be convinced that the equation holds without applying the function (but the prover needs to apply the function).

I'm assuming that $f(\cdot)$ is efficiently computable (i.e. is in $\mathsf P$), since if it is the case, then the PCP Theorem should ensure that an interactive proof exists for any such $f$.

$\endgroup$
1
  • $\begingroup$ ill study your bibliography and come back $\endgroup$
    – gurghet
    Jan 8, 2021 at 22:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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