A multi-prover interactive proof protocol, as described here, consists of computationally unbound provers $P_1,P_2,\ldots$ which together convince a polynomial-time verifier $V$ of some proposition, under the assumption that the provers can't communicate after some initial setup. Are there practical scenarios in which such a protocol would be useful?

The linked paper gives an example of a user inserting two bank cards into an ATM to prove their identity. I'm skeptical of this use case because:

  1. It would be difficult to physically ensure fraudulent cards are unable to communicate.
  2. Single-prover protocols (possibly relying on cryptographic assumptions) have been sufficient for this use case so far.
  3. The bank cards are not computationally unbounded; presumably the ATM has at least as much computational power as the cards, and could just run the honest verifier algorithm itself.

Note: Point 3 would not apply if, rather than computationally unbound provers, we considered polynomial-time provers with access to a secret. Has that class of protocols been studied?

Note: The study of this class of decision problems may have theoretical value (example) but I'm not asking about that.


Your Answer

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

Browse other questions tagged or ask your own question.