Interactive Proofs with Space Bounded Provers

Recent results in interactive proof systems [12][13][1] seem to indicate that it is easier for a prover in a single prover interactive proof system to cheat the verifier than it is for a prover in a multiple prover interactive proof system. We show that this is not the case for a single prover in which all but a fixed polynomial of the prover’s space is erased between each round. One consequence of this is that any multiple prover interactive protocol in which the provers need only a polynomial amount of space can be easily transformed into a single prover interactive protocol where the prover has only a fixed polynomial amount of space. This result also shows that one can easily transform checkers [5] into adaptive checkers [7] under the assumption that the program being checked has space bounded by a fixed polynomial.