| 講演名 | 2006-05-19 NP完全問題に基づく新しい公開鍵認証方式 林 俊一, 多田 充, |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | 本稿ではNP完全問題に基づく2つの公開鍵認証方式を提案する.1つは格子に関連した問題であるNELVPに基づく認証方式,もう1つは部分和問題に基づく認証方式である.これらの方式の安全性に関しては,ゼロ知識性の代わりに証拠秘匿性と呼ばれる性質を有していることを示す.証拠秘匿性は認証方式の安全性を保障するためには十分であると考えられているため,我々の提案方式も安全であると考えられる.また,我々の方式と様々な既存方式の効率を比較した結果,我々の方式は安全性を保障するために必要な繰り返しの回数,または,プロトコル1回の実行における計算量の点で優れていることが分かった. |
| 抄録(英) | In this paper, we present two public-key identification schemes based on NP-complete problems. The one is constructed based on a problem related to lattices, named NELVP, and the other is constructed based on the Subset Sum problem. It is not shown that these schemes have the zero-knowledge property, but we show that these ones have the witness hiding property. It is considered that the witness hiding property is sufficient to assure the security of identification schemes, and therefore, our schemes are also proved to be secure. Moreover, from the result of the comparison of efficiency between our schemes and others, our schemes outperform the other ones in terms of the number of repetitions for a required security level or the running time of one execution of identification protocols. |
| キーワード(和) | 公開鍵認証方式 / NP完全問題 / 格子 / 部分和問題 |
| キーワード(英) | public-key identification scheme / NP-complete problem / lattice / Subset Sum problem |
| 資料番号 | ISEC2006-6 |
| 発行日 |
| 研究会情報 | |
| 研究会 | ISEC |
|---|---|
| 開催期間 | 2006/5/12(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Information Security (ISEC) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | NP完全問題に基づく新しい公開鍵認証方式 |
| サブタイトル（和） | |
| タイトル（英） | New public-key identification schemes based on NP-complete problems |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 公開鍵認証方式 / public-key identification scheme |
| キーワード(2)（和/英） | NP完全問題 / NP-complete problem |
| キーワード(3)（和/英） | 格子 / lattice |
| キーワード(4)（和/英） | 部分和問題 / Subset Sum problem |
| 第 1 著者 氏名（和/英） | 林 俊一 / Shunichi HAYASHI |
| 第 1 著者 所属（和/英） | 千葉大学大学院 自然科学研究科 Graduate School of Science and Technology, Chiba University |
| 第 2 著者 氏名（和/英） | 多田 充 / Mitsuru TADA |
| 第 2 著者 所属（和/英） | 千葉大学 総合メディア基盤センター Institute of Media and Information Technology, Chiba University |
| 発表年月日 | 2006-05-19 |
| 資料番号 | ISEC2006-6 |
| 巻番号（vol） | vol.106 |
| 号番号（no） | 51 |
| ページ範囲 | pp.- |
| ページ数 | 7 |
| 発行日 | |