On the Knowledge Complexity of Arthur-Merlin Games (Special Section on Cryptography and Information Security)

スポンサーリンク

概要

• 論文の詳細を見る

• 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 = MA. 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.

• 一般社団法人電子情報通信学会の論文
• 1994-01-25

著者

• Itoh Toshiya

  Interdisciplinary Graduate School Of Science And Engineering Tokyo Institute Of Technology

• Kakimoto Tatsuhiko

  Interdisciplinary Graduate School Of Science And Engineering Tokyo Institute Of Technology : Ibm Jap

関連論文

• Checkers for Adaptive Programs
• Alternative Necessary and Sufficient Conditions for Collision Intractable Hashing
• A Note on AM Languages Outside NP ⋃ co-NP (Special Section on Cryptography and Information Security)
• Demonstrating Possession without Revealing Factors (Special Section on Cryptography and Information Security)
• On the Power of Self-Testers and Self-Correctors (Special Section on Cryptography and Information Security)
• On the Knowledge Tightness of Zero-Knowledge Proofs (Special Section on Cryptography and Information Security)
• Efficient Private Information Retrieval (Special Section on Cryptography and Information Security)
• On the Oracle Entropy and the Average Case Oracle Measure of Knowledge Complexity (Special Section on Cryptography and Information Security)
• On the Knowledge Complexity of Arthur-Merlin Games (Special Section on Cryptography and Information Security)

スポンサーリンク