ランダムオラクル

ランダムオラクル︵英: Random oracle︶は、暗号理論における一種の神託機械︵理論的ブラックボックス︶であり、あらゆる問合せに対して値域に一様に分布するような︵真の︶ランダムな応答を返すが、同じ問合せに対しては毎回同じ応答をするものである。言い換えれば、ランダムオラクルは全ての入力を値域内のランダムな出力にマッピングする関数である。

ランダムオラクルは暗号理論の証明で使われる数学的な抽象観念である。典型的には、何らかの暗号方式の安全性を証明する上で、その暗号方式に現れる暗号学的ハッシュ関数が適当な数学的性質を持つことを証明できない場合に、そのようなハッシュ関数の理想的な代替物として利用される。このように、安全性を証明する際にハッシュ関数をランダムオラクルで置き換えている場合、その暗号方式は﹁ランダムオラクルモデルにおいて安全﹂あるいは﹁ランダムオラクル仮定のもとで安全﹂と言われる。反対語は﹁スタンダードモデルにおいて安全﹂あるいは﹁標準モデルにおいて安全﹂である。

応用

ランダムオラクルの典型的な用途としては、何らかの暗号方式に現れる暗号学的ハッシュ関数の出力について強いランダム性を仮定したい場合に、そのようなハッシュ関数の理想的なモデルとして使われる。一般にそのような証明は、所与のシステムやプロトコルを攻撃するには、ランダムオラクルの︵理想的であるが故に実在しない︶脆弱性を利用するか、または解くことが困難とされている数学的問題を解かねばならないことを示し、以てその暗号方式が安全であるとする。 なお、暗号学的ハッシュ関数をランダムオラクルで置き換えずに済む場合もある。標準モデル上で定義されている性質︵例えば衝突耐性、第一原像攻撃耐性、第二原像攻撃耐性など︶だけを要請する暗号方式であれば、標準モデルで安全性を証明できる場合も少なくない︵例えばCramer-Shoup暗号︶。

ランダムオラクルは計算複雑性理論において長年に渡って研究されており︵例えば Bennett & Gill︶、 OAEPやPSSなど多くの暗号方式がランダムオラクルモデルで安全性を証明されている。 Fiat & Shamir (1986)はランダムオラクルの重要な応用例を示した︵電子署名作成プロトコルからの対話の除去︶。Impagliazzo & Rudich (1989)はランダムオラクルの限界を示した︵特に、秘密鍵交換においては単にランダムオラクルがあるだけでは不十分︶。Bellare & Rogaway (1993)は暗号設計にランダムオラクルを利用することを主張した。この定義においては、ランダムオラクルは無限長のビット列を生成し、利用者はそれを必要な長さに切り詰めることができる。

安全性の証明に用いる場合、ランダムオラクルは暗号を守る側も破る側も使えるものとする。1つのランダムオラクルは、問合せの先頭に固定ビット列を追加することで複数のランダムオラクルとして扱える︵例えば、"1|x" と "0|x" というように問合せの前に1か 0 を付けるようにすれば、2台のランダムオラクルに対する呼出しだと看做すことが出来る。同様に、"00|x"、"01|x"、"10|x"、"11|x" とすれば4台のランダムオラクルに対する呼出しと看做せる︶。

制約

有限のステップ数から成るアルゴリズムで計算可能な関数では、真のランダムオラクルを実装することは出来ない︵何故なら、定義により無限のステップ数が必要だからである︶。

実際、ある種の電子署名や暗号方式は、ランダムオラクルモデルで安全性を証明されているが、ランダムオラクルを実在する関数に置き換えようとすると、どのような関数に置き換えても明らかに安全ではなくなることが知られている。それでもなお、その他の暗号方式に関しては、ランダムオラクルを仮定して暗号の安全性が証明されれば、その暗号方式が安全であるという非常に強い証拠となる。

一般に、ある暗号方式が安全であると証明されたなら、その暗号方式に対する攻撃は、証明された範囲外の性質を利用するか、または証明に用いられた何らかの仮定を覆す必要がある。例えば、暗号方式が素因数分解の困難性を利用しているのなら、この仮定を覆すには高速な素因数分解アルゴリズムを発見しなければならない。ランダムオラクルで言えば、これを覆すには、実際に適用されているハッシュ関数について何かしら未知の脆弱性を発見しなければならない。そのような脆弱性がありそうに無い良いハッシュ関数を前提にすれば、所与の暗号方式は安全だと考えて良いことになる。

関連項目

• 神託機械
• 電子署名
• 暗号理論

外部リンク

• The Random Oracle Model — Helger Lipmaa によるリンク集