1
$\begingroup$

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.

$\endgroup$

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.