On the Knowledge Tightness of Zero-Knowledge Proofs (Special Section on Cryptography and Information Security)

スポンサーリンク

概要

• 論文の詳細を見る

• In this paper, we study the knowledge tightness of zero-knowledge proofs. To this end, we present a new measure for the knowledge tightness of zero-knowledge proofs and show that if a language L has a bounded round zero-knowledge proof with knowledge tightness t(|x|) ≦ 2-|x|^<-c> for some c>0, then L ∈ BPP and that any language L ∈ AM has a bounded round zero-knowledge proof with knowledge tightness t(|x|) ≦ 2-2^<-O>(|x|) under the assumption that collision intractable hash functions exist. This implies that in the case of a bounded round zero-knowledge proof for a language L ∉ BPP, the optimal knowledge tightness is "2" unless AM = BPP. In addition, we show that any language L ∈ IP has an unbounded round zero-knowledge proof with knowledge tightness t(|x|) ≦ 1.5 under the assumption that nonuniformly secure probabilistic encryptions exist.

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

著者

• Itoh Toshiya

  Interdisciplinary Graduate School Of Science And Engineering Tokyo Institute Of Technology

• Kawakubo Atsushi

  Interdisciplinary Graduate School Of Science And Engineering Tokyo Institute Of Technology : Toyota

関連論文

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

スポンサーリンク