Constant Round Perfect ZKIP of Computational Ability

スポンサーリンク

概要

• 論文の詳細を見る

• In this paper, we show that without any unproven assumption, there exists a "four" move blackbox simulation perfect zero-knowledge interactive proof system of computational ability for any random self-reducible relation R whose domain is in BPP, and that without any unproven assumption, there exists a "four" move blackbox simulation perfect zero-knowledge interactive proof system of knowledge on the prime factorization. These results are optimal in the light of the round complexity, because it is shown that if a relation R has a three move blackbox simulation (perfect) zero-knowledge interactive proof system of computational ability (or 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.

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

著者

• Itoh Toshiya

  The Interdisciplinary Graduate School Of Science And Engineering

• Sakurai Kouichi

  the Computer & Information Systems Laboratory, Mitsubishi Electric Corporation

• 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)

スポンサーリンク