= Prover in an interactive proof
{title2=$P$}
A \b[prover in an interactive proof] is the participant that sends messages intended to convince a <verifier in an interactive proof> of a public statement. Formally it is a strategy: its next response can depend on the public input, the preceding conversation and any private information or randomness it has. The basic <interactive proof system> model does not impose the verifier's <polynomial time> bound on this strategy.<Probabilistic Proof Systems: A Primer by Oded Goldreich>[Sections1.1.2–1.2 and1.5, prover strategies and computational resources]{ref}
An honest prover follows a designated strategy supporting <completeness of an interactive proof>. A cheating prover may depart from it; <soundness of an interactive proof> must still hold for every allowed cheating strategy. Calling a participant a prover therefore does not mean that its assertions are trusted.
A <cryptographic witness> can make an otherwise difficult response easy to produce. For an original composition example, let $\phi:G_0\to G_1$ be a known <graph isomorphism>. If the prover sends $H=\pi(G_0)$ for a chosen <permutation> $\pi$, it can supply $\pi$ as an isomorphism from $G_0$ to $H$, or $\pi\circ\phi^{-1}$ as an isomorphism from $G_1$ to $H$. Neither response requires solving a new isomorphism search problem from scratch.
Thus a theoretical allowance of unlimited prover computation is different from a claim about implementation cost. Some protocols have efficient honest provers when the witness is supplied; others are studied primarily for the verification power they demonstrate.
Back to article page
