Rational proofs with multiple provers

DOI10.1145/2840728.2840744zbMATH Open1334.68080arXiv1504.08361OpenAlexW765055999MaRDI QIDQ2800569FDOQ2800569

Authors: Jing Chen, Samuel McCauley, Shikha Singh 

Publication date: 15 April 2016

Published in: Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science (Search for Journal in Brave)

Abstract: Interactive proofs (IP) model a world where a verifier delegates computation to an untrustworthy prover, verifying the prover's claims before accepting them. IP protocols have applications in areas such as verifiable computation outsourcing, computation delegation, cloud computing. In these applications, the verifier may pay the prover based on the quality of his work. Rational interactive proofs (RIP), introduced by Azar and Micali (2012), are an interactive-proof system with payments, in which the prover is rational rather than untrustworthy---he may lie, but only to increase his payment. Rational proofs leverage the provers' rationality to obtain simple and efficient protocols. Azar and Micali show that RIP=IP(=PSAPCE). They leave the question of whether multiple provers are more powerful than a single prover for rational and classical proofs as an open problem. In this paper, we introduce multi-prover rational interactive proofs (MRIP). Here, a verifier cross-checks the provers' answers with each other and pays them according to the messages exchanged. The provers are cooperative and maximize their total expected payment if and only if the verifier learns the correct answer to the problem. We further refine the model of MRIP to incorporate utility gap, which is the loss in payment suffered by provers who mislead the verifier to the wrong answer. We define the class of MRIP protocols with constant, noticeable and negligible utility gaps. We give tight characterization for all three MRIP classes. We show that under standard complexity-theoretic assumptions, MRIP is more powerful than both RIP and MIP ; and this is true even the utility gap is required to be constant. Furthermore the full power of each MRIP class can be achieved using only two provers and three rounds. (A preliminary version of this paper appeared at ITCS 2016. This is the full version that contains new results.)

Full work available at URL: https://arxiv.org/abs/1504.08361

Recommendations

• Efficient rational proofs with strong utility-gap guarantees
• Rational proofs
• Rational sumchecks
• Sequentially composable rational proofs
• Rational arguments: single round delegation with sublinear verification

zbMATH Keywords

complexity theoryscoring rulesinteractive proofsdc uniform circuit familiesmulti-prover rational interactive proofs

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Cryptography (94A60) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Cited In (8)

• Title not available (Why is that?)
• Structural complexity of rational interactive proofs
• Efficient rational proofs with strong utility-gap guarantees
• Rationality Proofs by Curve Counting
• Verifiable crowd computing: coping with bounded rationality
• Rational proofs
• Sumcheck-based delegation of quantum computing to rational server
• Verifiable crowd computing: coping with bounded rationality

This page was built for publication: Rational proofs with multiple provers

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2800569)