On the Oracle Entropy and the Average Case Oracle Measure of Knowledge Complexity (Special Section on Cryptography and Information Security)

スポンサーリンク

概要

• 論文の詳細を見る

• In this paper, we investigate statistical and perfect Knowledge Complexity (KC) with respect to oracle entropy and average case oracle measures. As main results, we show the following: (1) for any k(n) ≧1/poly(n), if a language L has perfect KC k(n) + n^<-ω(1)> with respect to oracle entropy measure, then L has perfect KC k(n) with respect to oracle entropy measure (Theorem 3.1); (2) for any k(n) ≧1/poly(n), if a language L has perfect KC k(n) + n^<-ω(1)> with respect to average case oracle measure, then L has perfect KC k(n) with respect to average case oracle measure (Theorem 3.2); (3) if a language L has statistical KC k(n) ∈ o(1) with respect to oracle entropy measure, then for any ε> 0, L has statistical KC k(n) + 1 +ε with respect to average case oracle measure (Theorem 4.1); and (4) if a language L has perfect KC k(n) ∈ o(1) with respect to oracle entropy measure, then for any ε > 0, L has perfect KC k(n) + 2 + ε with respect to average case oracle measure (Theorem 4.2).

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

著者

• Itoh Toshiya

  Interdisciplinary Graduate School Of Science And Engineering Tokyo Institute Of Technology

関連論文

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

スポンサーリンク