On the Knowledge Complexity of Arthur-Merlin Games

Toshiya ITOH; Tatsuhiko KAKIMOTO

On the Knowledge Complexity of Arthur-Merlin Games

Toshiya ITOH, Tatsuhiko KAKIMOTO

Full Text Views

0

Cite this

Summary :

In this paper, we investigate the knowledge complexity of interactive proof systems and show that (1) under the blackbox simulation, if a language L has a bounded move public coin interactive proof system with polynomially bounded knowledge complexity in the hint sense, then the language L itself has a one move interactive proof system; and (2) under the blackbox simulation, if a language L has a three move private coin interactive proof system with polynomially bounded knowledge complexity in the hint sense, then the language L itself has a one move interactive proof system. These results imply that as long as the blackbox simulation is concerned, any language L AM＼MA is not allowed to have a bounded move public coin (or three move private coin) interactive proof system with polynomially bounded knowledge complexity in the hint sense unless AM = AM. In addition, we present a definite distinction between knowledge complexity in the hint sense and in the strict oracle sense, i.e., any language in AM (resp. IP) has a two (resp. unbounded) move public coin interactive proof system with polynomially bounded knowledge complexity in the strict oracle sense.

Publication: IEICE TRANSACTIONS on Fundamentals Vol.E77-A No.1 pp.56-64

Publication Date: 1994/01/25

Publicized

Online ISSN

DOI

Type of Manuscript: Special Section PAPER (Special Section on Cryptography and Information Security)

Category

Cite this

Copy

Toshiya ITOH, Tatsuhiko KAKIMOTO, "On the Knowledge Complexity of Arthur-Merlin Games" in IEICE TRANSACTIONS on Fundamentals, vol. E77-A, no. 1, pp. 56-64, January 1994, doi: .
Abstract: In this paper, we investigate the knowledge complexity of interactive proof systems and show that (1) under the blackbox simulation, if a language L has a bounded move public coin interactive proof system with polynomially bounded knowledge complexity in the hint sense, then the language L itself has a one move interactive proof system; and (2) under the blackbox simulation, if a language L has a three move private coin interactive proof system with polynomially bounded knowledge complexity in the hint sense, then the language L itself has a one move interactive proof system. These results imply that as long as the blackbox simulation is concerned, any language L AM＼MA is not allowed to have a bounded move public coin (or three move private coin) interactive proof system with polynomially bounded knowledge complexity in the hint sense unless AM = AM. In addition, we present a definite distinction between knowledge complexity in the hint sense and in the strict oracle sense, i.e., any language in AM (resp. IP) has a two (resp. unbounded) move public coin interactive proof system with polynomially bounded knowledge complexity in the strict oracle sense.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/e77-a_1_56/_p

Copy

@ARTICLE{e77-a_1_56,
author={Toshiya ITOH, Tatsuhiko KAKIMOTO, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={On the Knowledge Complexity of Arthur-Merlin Games},
year={1994},
volume={E77-A},
number={1},
pages={56-64},
abstract={In this paper, we investigate the knowledge complexity of interactive proof systems and show that (1) under the blackbox simulation, if a language L has a bounded move public coin interactive proof system with polynomially bounded knowledge complexity in the hint sense, then the language L itself has a one move interactive proof system; and (2) under the blackbox simulation, if a language L has a three move private coin interactive proof system with polynomially bounded knowledge complexity in the hint sense, then the language L itself has a one move interactive proof system. These results imply that as long as the blackbox simulation is concerned, any language L AM＼MA is not allowed to have a bounded move public coin (or three move private coin) interactive proof system with polynomially bounded knowledge complexity in the hint sense unless AM = AM. In addition, we present a definite distinction between knowledge complexity in the hint sense and in the strict oracle sense, i.e., any language in AM (resp. IP) has a two (resp. unbounded) move public coin interactive proof system with polynomially bounded knowledge complexity in the strict oracle sense.},
keywords={},
doi={},
ISSN={},
month={January},}

Copy

TY - JOUR
TI - On the Knowledge Complexity of Arthur-Merlin Games
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 56
EP - 64
AU - Toshiya ITOH
AU - Tatsuhiko KAKIMOTO
PY - 1994
DO -
JO - IEICE TRANSACTIONS on Fundamentals
SN -
VL - E77-A
IS - 1
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - January 1994
AB - In this paper, we investigate the knowledge complexity of interactive proof systems and show that (1) under the blackbox simulation, if a language L has a bounded move public coin interactive proof system with polynomially bounded knowledge complexity in the hint sense, then the language L itself has a one move interactive proof system; and (2) under the blackbox simulation, if a language L has a three move private coin interactive proof system with polynomially bounded knowledge complexity in the hint sense, then the language L itself has a one move interactive proof system. These results imply that as long as the blackbox simulation is concerned, any language L AM＼MA is not allowed to have a bounded move public coin (or three move private coin) interactive proof system with polynomially bounded knowledge complexity in the hint sense unless AM = AM. In addition, we present a definite distinction between knowledge complexity in the hint sense and in the strict oracle sense, i.e., any language in AM (resp. IP) has a two (resp. unbounded) move public coin interactive proof system with polynomially bounded knowledge complexity in the strict oracle sense.
ER -