Rational Proofs against Rational Verifiers

• INASAWA Keita

  Institute of Science and Engineering, Kanazawa University

• YASUNAGA Kenji

  Institute of Science and Engineering, Kanazawa University

抄録

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.

収録刊行物

• IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences

  IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences E100.A (11), 2392-2397, 2017

  一般社団法人 電子情報通信学会

キーワード

• rational proof
• delegation of computation
• game theory
• random oracle model

詳細情報

• CRID: 1390001206311779328
• NII論文ID: 130006191407
• DOI: 10.1587/transfun.e100.a.2392
• ISSN: 17451337
• ISSN: 09168508
• Web Site: https://www.jstage.jst.go.jp/article/transfun/E100.A/11/E100.A_2392/_pdf
• 本文言語コード: en
• データソース種別:
  • JaLC
  • Crossref
  • CiNii Articles
  • KAKEN
• 抄録ライセンスフラグ: 使用不可