| 講演名 | 1995/7/21 統計的及び完全な知識の複雑さについて 伊東 利哉, |
|---|---|
| PDFダウンロードページ | PDFダウンロードページへ |
| 抄録(和) | 本稿では,対話型証明及び暗号プロトコルの安全性を議論する上で,重要な意味を持つ知識の複雑さ(Knowledge Complexity: KC)の尺度-Oracle Entropy及びAverage Case Oracle-について考察を行なう.そして主要結果として-(1)k(n)≥1/poly(n)であるとき,Oracle Entropyの尺度のもとで完全な知識の複雑さk(n)+n^<-w(1)>を持つ言語は,Oracle Entropyの尺度のもとで完全な知識の複雑さk(n)を持つこと;(2)k(n)≥poly(n)であるとき,Average Case Oracleの尺度のもとで完全な知識の複雑さk(n)^<-w(1)>を持つ言語は,Average Case Oracleの尺度のもとで完全な知識の複雑さk(n)を持つこと;(3)Oracle Entropyの尺度のもとで統計的な知識の複雑さk(n)∈o(1)を持つ言語は,任意のε>0に対しAverage Case Oracleの尺度のもとで統計的な知識の複雑さk(n)+1+εを持つこと,(4)Oracle Entropyの尺度のもとで完全な知識の複雑さk(n)∈o(1)を持つ言語は,任意のε>0に対しAverage CaseOracleの尺度のもとで完全な知識の複雑さk(n)+2+εを持つこと-を示す. |
| 抄録(英) | 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^<-w(1)> with respect to oracle entropy measure, then L has perfect KC k(n) with respect to average case oracle measure (Theorem 3.1) ; (2)for any k(n)≥1/poly(n), if a language L has perfect KC k(n)+n^<-w(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 c>0, L has perfect KC k(n)+2+∈ with respect to average case oracle measure (Theorem 4.2). |
| キーワード(和) | 統計的な知識の複雑さ / 完全な知識の複雑さ / オラクル(平均)情報量 / 平均オラクル |
| キーワード(英) | Statistical KC / Perfect KC / Oracle Entropy Measure / Average Case Oracle Measure |
| 資料番号 | |
| 発行日 |
| 研究会情報 | |
| 研究会 | ISEC |
|---|---|
| 開催期間 | 1995/7/21(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Information Security (ISEC) |
|---|---|
| 本文の言語 | ENG |
| タイトル（和） | 統計的及び完全な知識の複雑さについて |
| サブタイトル（和） | |
| タイトル（英） | On the Oracle Entropy and the Average Case Oracle Measure of Knowledge Complexity |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 統計的な知識の複雑さ / Statistical KC |
| キーワード(2)（和/英） | 完全な知識の複雑さ / Perfect KC |
| キーワード(3)（和/英） | オラクル(平均)情報量 / Oracle Entropy Measure |
| キーワード(4)（和/英） | 平均オラクル / / Average Case Oracle Measure |
| 第 1 著者 氏名（和/英） | 伊東 利哉 / Toshiya Itoh |
| 第 1 著者 所属（和/英） | 東京工業大学大学院総合理工学研究科物理情報工学専攻 Department of Information Processing, Tokyo Institute of Technology |
| 発表年月日 | 1995/7/21 |
| 資料番号 | |
| 巻番号（vol） | vol.95 |
| 号番号（no） | 172 |
| ページ範囲 | pp.- |
| ページ数 | 17 |
| 発行日 | |