衝突困難ハッシュ関数を用いない電子署名に関する研究

松田 隆宏

アイテムタイプ

学位論文 / Thesis or Dissertation

言語

日本語

キーワード

電子署名, ハッシュ関数, 証明可能安全性, 強偽造不可能性, 衝突困難性, ターゲット衝突困難性, 強化ターゲット衝突困難性

その他のタイトル

A Study on Digital Signatures without Collision Resistant Hash Functions

著者

松田隆宏

著者所属

大学院情報理工学系研究科電子情報学専攻
Graduate School of Information Science and Technology Department of Information and Communication Engineering The University of Tokyo

Abstract

電子署名の安全性とハッシュ関数の安全性とは非常に関係が深い。電子署名では、その用途にも依るが、様々なサイズのデータの署名を可能にするためには、データを一度ハッシュ関数に通し、一度固定長の空間に写すということが必要である。そして同時に、ハッシュ関数の安全性自体が電子署名の安全性証明の際の仮定の一つとしても用いられる。特によく用いられる安全性であるハッシュ関数の衝突困難性は、ハッシュ値が等しくなる任意の入力のペアを見つけることが困難であるという性質で、任意長の長さのメッセージをハッシュ関数をによって固定長に写し、そのハッシュ値に対して署名を付けるという“Hash-and-Sign” パラダイムを用いる方式などで用いられる。衝突困難性をある種の困難性の仮定の下に証明可能なハッシュ関数も存在するが、署名作成や検証の計算コストを考慮し、現実的には、実装の際はSHA-1 やMD5 などの実用的ハッシュ関数を用いることになる。しかし近年、Wang らのSHA-1 への攻撃に代表されるこれら実用的ハッシュ関数に対して、従来考えられていたより遥かに少ない計算回数で衝突を見つける、衝突困難性を破る攻撃についての報告は、衝突困難性を持つ実用的ハッシュ関数を構成することは簡単ではないということを示している。そこで本研究では、電子署名の中で使われるハッシュ関数は実用的ハッシュ関数に対する仮定までも考慮に入れ、衝突困難性を用いずに証明可能安全性を持ち、かつ効率のよい電子署名方式を目指した。そして、具体的に強偽造不可能性という電子署名における最強の安全性を持つ電子署名方式を2 種類提案し、その安全性証明を示した。いずれの方式もスタンダードモデルでのCDH 仮定に基づいており、両方式は、スタンダードモデルでCDH 仮定に基づく強偽造不可能性を持つ電子署名方式で、最も効率が良い方式であるBSW 署名と同程度に効率がよい。しかも安全性の証明の仮定としてハッシュ関数の衝突困難性を用いていないため、衝突発見攻撃によって内部で使用されているハッシュ関数の衝突困難性が破られても、電子署名としての安全性は揺るがない。

発行年

2008-03

日本十進分類法

548

学位名

修士(情報理工学)

学位

master

研究科・専攻

情報理工学系研究科電子情報学専攻

学位授与年月日

2008-03-24

UTokyo Repository

Language

インデックスツリー