このページをはてなブックマークに追加このページを含むはてなブックマーク このページをlivedoor クリップに追加このページを含むlivedoor クリップ

目次

宣伝

 当サイトにおける暗号に関するページでは、説明が足りなかったり、誤った記述をしていたりするところがあります。今後、少しずつ修正する予定です。

 暗号理論の『暗号技術のすべて』が発売されています。初心者向けの暗号本です。これまで暗号本に何度か挑戦しつつも挫折してしまった方、学校の課題で悩んでいる方、資格試験にて暗号の問題が苦手な方などにお勧めです。

『暗号技術のすべて』宣伝サイト

 興味がある方は宣伝サイトを参照してください。Amazonでも発売中です。

ランダムオラクルモデル

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

ランダムオラクル

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

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

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

ランダムオラクルモデルが嬉しい理由

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

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

ランダムオラクルモデルの妥当性

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

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

ランダムオラクルモデル vs スタンダードモデル

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

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