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!


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.

  • $\begingroup$ For prover running time and this particular language of verifying computations that takes some time and space, I guess, one better read the whole paper, and it could be "SNARKS for C". It was a reminder that verifier is supposed to run fast (in poly time), as required by interactive proof definition. Nobody cares for prover resources, and exponential space of prover renders the whole idea impractical. For "every computation", please read Goldreich, Micali, Wigderson "Proofs that Yield Nothing But Their Validity for All Languages in NP Have Zero-Knowledge Proof Systems". $\endgroup$ Jan 16, 2018 at 23:27

2 Answers 2


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.

  • $\begingroup$ Your last statement isn't strictly true: in the foundations of mathematics it's necessary to prove some very simple statements from the axioms. EG proving that 2+2=4 from ZFC takes 27,426 steps. us.metamath.org/mpeuni/mmset.html#trivia $\endgroup$ Dec 17, 2017 at 6:52
  • $\begingroup$ Also a minor nitpick: a prover may require more than exponential time, eg for problems in NEXPTIME. There may be even more complexity classes beyond NEXPTIME and NEXPSPACE, just as there are fast-growing functions that dwarf exponentiation. Computational complexity theory isn't my field, so i can't give examples of such classes. $\endgroup$ Dec 17, 2017 at 6:56

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.


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.