このページをはてなブックマークに追加このページを含むはてなブックマーク このページをlivedoor クリップに追加このページを含むlivedoor クリップ
*目次 [#p02e811f]

#contents


*ランダムオラクルモデル [#o7f3e9ff]

 ''ランダムオラクル(Random Oracle:RO)モデル''は、ハッシュ関数の実行をランダムオラクルへの問い合わせに置き換えるモデルである。


*ランダムオラクル [#ye4a3d49]

 まずスキームが開始されたら、セットアップとしてランダムオラクルはハッシュ関数族Hからランダムにハッシュ関数h(∈H)を選択する。そして、メッセージmの問い合せが来たら、h(m)を計算し、これを返答する。

 ハッシュ関数なので入力が決まれば出力も決定される。これは次のように考えることができる。クエリーが送られてきたら、List(最初は空)にそのクエリーがあるかどうか検索する。
初めて来たクエリーならば、ランダム値を作り、送り返す。その際にListにそのクエリーとランダム値のペアを書き込む。
またListにクエリーが存在していたら、対応する値を送り返す。

#img(http://security2600.sakura.ne.jp/main2/image1/RO.jpg)
#img(,clear)

 もちろんこのListはスキームの実行の度に内容を消去するとする。


*ランダムオラクルモデルが嬉しい理由 [#ef13480d]

 ランダムオラクルモデルを採用すれば、アドバーサリーがハッシュの計算をするときに必ずランダムオラクルに問い合わせすることになる。そのためシミュレーターがランダムオラクルのふりをすることによって、シミュレーターが有利になる。この有利さをうまく利用することで、安全性証明が付くことがある。

 例えば、[[RSA-OAEP暗号]]はランダムオラクルモデルの下でIND-CCA2安全、[[RSA-FDH署名]]はランダムオラクルモデルの下でEUF-CMA安全であることが証明されている。


*ランダムオラクルモデルの妥当性 [#v39fb653]

 ランダムオラクルの動きを考えると、ある種ハッシュ関数の理想化されたものといえる。しかし、現実に完全なハッシュ関数は見つかっていない。

 Listの方のイメージで捉えると、問い合わせの度に過去のListとの照合をすることになる。Listの数が膨大になってくるとアクセスすることも、Listを保存することも不可能といえるだろう。


**ランダムオラクルモデル vs スタンダードモデル [#t5d8db6f]

 ランダムオラクルモデルの妥当性に疑問があるため、最近ではランダムオラクルモデルを用いないスタンダードモデルでの証明なども盛んである。

 例えば、[[Cramer-Shoup署名]]はスタンダードモデルの下でEUF-CMA安全であることがわかっている。