Why does the prover in an interactive proof run in exponential time with the space of the computation?

Question

I'm currently trying to gain an understanding of verifiable computation and the strengths and weaknesses of past approaches.

In particular, I've been watching the following YouTube video which talks about interactive proofs as a way of verifying knowledge of a computation. On the slide appearing during time 11:55, it mentions that the prover requires exponential time in the space of the computation. Could anyone explain how this is the case?

I'm also confused as to the statement which says that every deterministic computation has an interactive proof.

I've tried reading the papers below but can't seem to find a clear explanation of these results. Any help would be much appreciated!

References:

Lund, Carsten, et al. "Algebraic methods for interactive proof systems." Journal of the ACM (JACM) 39.4 (1992): 859-868.

Shamir, Adi. "Ip= pspace." Journal of the ACM (JACM) 39.4 (1992): 869-877.

Answer 1

The whole point of verifiable computation is to allow the verifier to verify that the computation was performed correctly without performing the computation himself. Since as usual we associate "polynomial-time" with "efficiently computable", if the computation takes poly time there is no point in using verifiable computation, since the verifier can just as well perform the computation himself.

In proof systems in general, if the verifier can determine by himself the truth of the statement in question, there is no need for a prover at all.

Answer 2

The following is an answer to your first question.

This is one thing that I find is hard to graps with the usual presentation of interactive proofs, so I think this is a good question.

There are two overall goals with an interactive proof.

• First, the verifier should only have to do a cheap computation (efficient, that is, polynomial-time) to be convinced that a statement is true.
• Second, the prover should not be able to convince the verifier consistently to accept a non-truth regardless of how much computational effort he is willing to expend. (This is what gives us a "proof".)

The thing most students do not expect is that while the verifier must be efficient, there's no requirement that the prover should be efficient. Hence, in examples, non-efficient provers tend to show up every now and then.

Why do we not require the prover to be efficient? I am no expert on this, but I believe it gives us a richer, more general theory. Which is a perfectly valid point from a theory point of view.

However, when the theory of interactive proofs collides with cryptography, this becomes awkward for the student, since in cryptography, a non-efficient prover doesn't seem to make sense. Clearly, allowing a cheating prover to be non-efficient is of some value (similar to information-theoretic security), but in cryptography, we actually intend (at least in theory) to run a non-cheating prover, which means it must be efficient. Hence, the usual definition of interactive proof does not make intuitive sense in cryptography.

To summarise: The theory of interactive proofs is not cryptography. The theory is not entirely tailored for use in cryptography. However, it is vital for cryptography.