On the Knowledge Complexity of Arthur-Merlin Games

Toshiya ITOH, Tatsuhiko KAKIMOTO

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
• Type of Manuscript: Special Section PAPER (Special Section on Cryptography and Information Security)

Authors

Toshiya ITOH
Tatsuhiko KAKIMOTO

Keyword

interactive proof systems,  knowledge complexity,  hint,  strict oracle,  round complexity