| 講演名 | 2007-05-18 Paillierの観点から見たディジタル署名の安全性の再考 川合 豊, 太田 和夫, 國廣 昇, |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | 公開鍵暗号研究の黎明期(1980年代),「ある攻撃に対して安全(その攻撃者から計算量的困難な問題への帰着が存在する)な方式は,その帰着を用いることにより別の攻撃に対して完全解読可能なアルゴリズムが構成できる(両立不可能性)」と信じられていた.これに対し,Paillierらは,単一鍵素因数分解に基づく暗号系について,この事実が成立すること(両立不可能性Iとよぶ)を「メタ帰着技法」を用いて示した.さらに,この技法を活用して,分析精度を上げた安全性解析も可能となること(両立不可能性IIとよぶ)も示した.本論文では,Paillierら手法を用いて,単一鍵素因数分解問題に基づくの署名の両立不可能性I,IIを証明する.加えて,既存研究では厳密に議論されていなかったSelectiveForgery(SF)を再定義し,Rabin署名の安全性を詳細に分析する.そして,「メタ帰着」を利用すると,既知のゴールに対応する攻撃シナリオを新たに導入できること(その逆も可能)を示す.また,具体的にSFに対応するシナリオ,種々のCMAシナリオに対応するゴールを新たに定義する.本研究により,今まで独立に考えられていた攻撃のゴールとシナリオをメタ帰着を用いることで関連性(ある種の双対性)を持たせることができ,署名系についても分析精度を高めた安全性解析が可能となる. |
| 抄録(英) | In the dawn of the research on public key cryptosystem, 「There is a certain scheme such that if the scheme proven secure that is under certain attack scenario A (there is a reduction algorithm which solves computationally hard problem using an attacker), we can construct an algorithm that can totally break the scheme under another attack scenario B using the reduction.」is believed. Paillier proved that this fact was satisfied using meta reduction technique for single key factoring-based encryption (call it "Impossible proof I"). In addition, they utilized this technique to enable the more detail security analysis (call it "Impossible proof II"). In this paper, "Impossible proof I, Impossible proof II" of single key factoring based signature is proved using technique of Paillier. In addition, we define the concept of Selective Forgery which was not defined in previous research and analyze the security of Rabin signature in detail. We show that a new attack scenario (attack goal) is introduced using meta reduction technique and define the concrete attack scenario corresponding to SF, and attack goal corresponding to various kinds of CMA scenarios. We show that attack scenarios and attack goals have a certain relationship (a certain duality) by using meta reduction technique, and the security analysis of digital signature with analysis is enabled. |
| キーワード(和) | 両立不可能性 / Rabin署名 / メタ帰着 / KPBB帰着 / 攻撃のゴール / 攻撃のシナリオ |
| キーワード(英) | Impossible proof / Rabin signature / meta reduction / KPBB reduction / attack scenario / attack goal |
| 資料番号 | ISEC2007-9 |
| 発行日 |
| 研究会情報 | |
| 研究会 | ISEC |
|---|---|
| 開催期間 | 2007/5/11(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Information Security (ISEC) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | Paillierの観点から見たディジタル署名の安全性の再考 |
| サブタイトル（和） | |
| タイトル（英） | Consideration on security of digital signatures from the view point of Paillier's framework |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 両立不可能性 / Impossible proof |
| キーワード(2)（和/英） | Rabin署名 / Rabin signature |
| キーワード(3)（和/英） | メタ帰着 / meta reduction |
| キーワード(4)（和/英） | KPBB帰着 / KPBB reduction |
| キーワード(5)（和/英） | 攻撃のゴール / attack scenario |
| キーワード(6)（和/英） | 攻撃のシナリオ / attack goal |
| 第 1 著者 氏名（和/英） | 川合 豊 / Yutaka KAWAI |
| 第 1 著者 所属（和/英） | 電気通信大学情報通信工学科 The University of Electro-Communications |
| 第 2 著者 氏名（和/英） | 太田 和夫 / Kazuo OHTA |
| 第 2 著者 所属（和/英） | 電気通信大学情報通信工学科 The University of Electro-Communications |
| 第 3 著者 氏名（和/英） | 國廣 昇 / Noboru KUNIHIRO |
| 第 3 著者 所属（和/英） | 電気通信大学情報通信工学科 The University of Electro-Communications |
| 発表年月日 | 2007-05-18 |
| 資料番号 | ISEC2007-9 |
| 巻番号（vol） | vol.107 |
| 号番号（no） | 44 |
| ページ範囲 | pp.- |
| ページ数 | 8 |
| 発行日 | |