Rational Proofs against Rational Verifiers
Summary :
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.
- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E100-A No.11 pp.2392-2397
- Publication Date
- 2017/11/01
- Publicized
- Online ISSN
- 1745-1337
- DOI
- 10.1587/transfun.E100.A.2392
- Type of Manuscript
- PAPER
- Category
- Cryptography and Information Security
Authors
Keita INASAWA
Kanazawa University
Kenji YASUNAGA
Kanazawa University
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Keita INASAWA, Kenji YASUNAGA, "Rational Proofs against Rational Verifiers" in IEICE TRANSACTIONS on Fundamentals,
vol. E100-A, no. 11, pp. 2392-2397, November 2017, doi: 10.1587/transfun.E100.A.2392.
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.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.E100.A.2392/_p
Copy
@ARTICLE{e100-a_11_2392,
author={Keita INASAWA, Kenji YASUNAGA, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Rational Proofs against Rational Verifiers},
year={2017},
volume={E100-A},
number={11},
pages={2392-2397},
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.},
keywords={},
doi={10.1587/transfun.E100.A.2392},
ISSN={1745-1337},
month={November},}
Copy
TY - JOUR
TI - Rational Proofs against Rational Verifiers
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 2392
EP - 2397
AU - Keita INASAWA
AU - Kenji YASUNAGA
PY - 2017
DO - 10.1587/transfun.E100.A.2392
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E100-A
IS - 11
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - November 2017
AB - 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.
ER -
English
