| 講演名 | 1995/11/16 プロミス問題に対するゼロ知識対話証明の通信ビット数に関する考察 満保 雅浩, 岡本 栄司, |
|---|---|
| PDFダウンロードページ | PDFダウンロードページへ |
| 抄録(和) | 通信に要するコストは時として計算に要するコストよりも大きくなる。また、ゼロ知識対話証明によりユーザ認証を行なっている場合に、同じ通信設備を利用しつつユーザ数を増加させる為にはプロトコル自体を効率的に構成し直す必要が出てくる。このように、通信効率を減少させることは重要な課題といえる。本稿では、プロミス問題に対するゼロ知識対話証明を取り上げて、従来知られている構成法と同様の完全性誤り、及び、同様の健全性誤りを達成する繰り返し回数において、送信される平均総ビット数をより少なくする方式について考察する。平方剰余問題に関して、新しい構成法により通信ビット総数を一般的な方式の約5/6に減少させることが可能となる。 |
| 抄録(英) | The communication cost is sometimes much more expensive than the computation cost. On the other hand, a credit card company, which uses a zero-knowledge interactive proof system, ZKIP, for user authentication, might want to increase the number of users it can dealt with in one day without newly investing into communication equipments. Then the company has to reconstruct a more efficient ZKIP in terms of the number of communicated bits. In this paper an efficient ZKIP for the quadratic residuosity, which is a ZKIP for a promise problem, is presented. It decreases the communication complexity about 5/6 of that of the standard ZKIP. |
| キーワード(和) | 通信の複雑さ / プロミス問題 / ゼロ知識対話証明 / 平方剰余性 / 完全ゼロ知識 |
| キーワード(英) | Communication complexity / Promise problem / ZKIP / Quadratic residuosity / Perfect ZK |
| 資料番号 | ISEC95-26 |
| 発行日 |
| 研究会情報 | |
| 研究会 | ISEC |
|---|---|
| 開催期間 | 1995/11/16(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Information Security (ISEC) |
|---|---|
| 本文の言語 | ENG |
| タイトル（和） | プロミス問題に対するゼロ知識対話証明の通信ビット数に関する考察 |
| サブタイトル（和） | |
| タイトル（英） | A Note on Communication Complexity of a Zeroknowledge Interactive Proof System for a Promise Problem |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 通信の複雑さ / Communication complexity |
| キーワード(2)（和/英） | プロミス問題 / Promise problem |
| キーワード(3)（和/英） | ゼロ知識対話証明 / ZKIP |
| キーワード(4)（和/英） | 平方剰余性 / Quadratic residuosity |
| キーワード(5)（和/英） | 完全ゼロ知識 / Perfect ZK |
| 第 1 著者 氏名（和/英） | 満保 雅浩 / Masahiro MAMBO |
| 第 1 著者 所属（和/英） | 北陸先端科学技術大学院大学 情報科学研究科 School of Information Science Japan Advanced Institute of Science and Technology |
| 第 2 著者 氏名（和/英） | 岡本 栄司 / Eiji OKAMOTO |
| 第 2 著者 所属（和/英） | 北陸先端科学技術大学院大学 情報科学研究科 School of Information Science Japan Advanced Institute of Science and Technology |
| 発表年月日 | 1995/11/16 |
| 資料番号 | ISEC95-26 |
| 巻番号（vol） | vol.95 |
| 号番号（no） | 353 |
| ページ範囲 | pp.- |
| ページ数 | 10 |
| 発行日 | |