Paper 2017/270

Rational Proofs against Rational Verifiers

Keita Inasawa and Kenji Yasunaga

Abstract

Rational proofs, introduced by Azar and Micali (STOC 2012), are a variant of interactive proofs in which the prover is rational, and may deviate from the protocol for increasing his reward. Guo et al.\ (ITCS 2014) demonstrated that rational proofs are relevant to delegation of computation. By restricting the prover to be computationally bounded, they presented a one-round delegation scheme with sublinear verification for functions computable by log-space uniform circuits with logarithmic depth. In this work, we study rational proofs in which the verifier is also rational, and may deviate from the protocol for decreasing the prover's reward. We construct a three-message delegation scheme with sublinear verification for functions computable by log-space uniform circuits with polylogarithmic depth in the random oracle model.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Preprint. MINOR revision.
Keywords
rational proofdelegation of computationgame theoryrandom oracle model
Contact author(s)
yasunaga @ se kanazawa-u ac jp
History
2017-03-25: received
Short URL
https://ia.cr/2017/270
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2017/270,
      author = {Keita Inasawa and Kenji Yasunaga},
      title = {Rational Proofs against Rational Verifiers},
      howpublished = {Cryptology ePrint Archive, Paper 2017/270},
      year = {2017},
      note = {\url{https://eprint.iacr.org/2017/270}},
      url = {https://eprint.iacr.org/2017/270}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.