On the Complexity of Constant Round ZKIP of Possession of Knowledge (Special Section on Cryptography and Information Security)

スポンサーリンク

概要

• 論文の詳細を見る

• In this paper, we investigate the round complexity of zero-knowledge interactive proof systems of possession of knowledge, and mainly show that if a relation R has a three move blackbox simulation zero-knowledge interactive proof system of possession of knowledge, then there exists a probabilistic polynomial time algorithm that on input x⋳{0, 1}^*, outputs y such that (x,y)⋳R with overwhelming probability if x⋳ dom R, and outputs "⊥" with probability 1 if x∉ dom R. The result above can not be generalized to zero-knowledge interactive proof systems of possession of knowledge with more than four moves, because it is known that there exists a "four" move blackbox simulation perfect zero-knowledge interactive proof system of possession of knowledge for a nontrivial relation R.

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

著者

• Itoh Toshiya

  The Interdisciplinary Graduate School Of Science And Engineering

• Sakurai Kouichi

  the Computer & Information Systems Laboratory, Mitsubishi Electric Corporation

関連論文

• Practical Consequences of the Discrepancy between Zero-Knowledge Protocols and Their Parallel Execution (Special Section on Cryptography and Information Security)
• Constant Round Perfect ZKIP of Computational Ability
• On the Complexity of Composite Numbers (Special Section on Cryptography and Information Security)
• A Characterization of Languages in Constant Round Perfect Zero-Knowledge Interactive Proofs (Special Section on Discrete Mathematics and Its Applications)
• On the Complexity of Constant Round ZKIP of Possession of Knowledge (Special Section on Cryptography and Information Security)

スポンサーリンク